山东中医药大学理工学院

课 程 设 计 报 告

课程名称： 高级语言课程设计 课程代码： 07300561 设计内容： 汉诺塔演示系统

二0一二 年 12 月21日

- 1 -

目 录

1.课程设计目的 ................................................ 3

1.1了解汉诺塔的基本原理 ....................................... 3

2.课程设计题目描述和要求 ...................................... 3

2.1课程设计题目 .............................................. 3

2.2课程设计要求 .............................................. 3

3.课程设计报告内容 ............................................ 4

3.1程序原理 .................................................. 4

3.2程序内容 .................................................. 5

3.3算法设计 .................................................. 7

3.4程序调试 ........................................................... 7

4.总结 ........................................................ 8 2

一、课程设计目的

1.1了解汉诺塔基本原理

1、通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。

2、通过本实验，学习和了解mfc环境的应用。

3、通过本实验，对递归算法及进栈出栈操作进一步了解和应用。

4、通过本实验，将课堂学习的理论与实践结合在一起。

5、学会编制结构清晰、风格良好、数据结构适当的Ｃ++语言程序，从而具备解决综合性实际问题的能力。

2.课程设计题目描述和要求

2.1 课程设计描述

1、在mfc界面中插入盘子，确定其初始状态以及背景图片。

2、选择盘子的数量，以自动搬移的方式移动。

3、自动搬移可以通过定时器的方法，每一次移动的时间间隔可以通过修改程序中的代码自定。

4、定义塔的描述类和碟子的描述类。

5、选定盘子数量点击开始运行，点击结束后退出程序。

2.2 课程设计要求

通过对高级程序语言设计学习，以及对mfc的自学过程，掌握对mfc可视化程序的设计，熟练运用老师所讲的高级程序语言设计的知识，通过综合运用先修课的知识，培养独立分析和解决实际问题的能力。培养学生使用高级语言开发系统的能力，提高学生分析、设计系 3

统的能力。

3.课程设计报告内容

3.1程序原理

当在一个函数A的定义中出现调用函数A的情况时，或在A函数的定义过程中调用B函数，而在B函数的定义过程中又调用了A函数 ，这种调用关系称为递归调用。在设计递归程序函数时，通常是先判断递归结束条件，再进行递归调用。其执行过程比较复杂，都存在连续递归调用（参数入栈）和回推过程。在使用递归的方法设计程序时，在递归程序中一定要有递归结束条件；否则，在执行程序时，会产生无穷无尽的递归调用。

3.2程序内容

算法设计思想：

(1)将塔A上的n-1个碟子借助塔C先移到塔B上。

(2)把塔A上剩下的一个碟子移到塔C上。

(3)将n-1个碟子从塔B借助于塔A移到塔C上。

实验步骤：

1. 用c++ 或c语言设计实现汉诺塔游戏；

2. 让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数；

3. 画出盘子数n和运行时间t 、递归调用次数m的关系然后对程序进行分析

4

3.3 算法设计

（1）移动盘子在CMyDlg中建立成员函数： MoveDisk：

int CMyDlg::MoveDish(int n, int a, int b) {

if(1 == n){

// 移动盘子

int i = 1;

for(; i <= number ; i++){

if(a == dish[number - i]){

break;

}

}

if(i > number){

5

} return 0; } dish[number - i] = b; return 0; // 完成 } else{ // 将要进行的操作进栈 opt[pn][0] = n-1; opt[pn][1] = 3-a-b; opt[pn][2] = b; pn ++; opt[pn][0] = 1; opt[pn][1] = a; opt[pn][2] = b; pn ++; opt[pn][0] = n-1; opt[pn][1] = a; opt[pn][2] = 3-a-b; pn ++; return 1; }

（2）建立选择盘子以及盘子移动速度的成员函数： OnButton1()

void CMyDlg::OnButton1() {

// 开始演示

if(0 == number){

MessageBox("请选择盘子数！");

return ;

}

SetDishNumber(number); // 数据重置

MoveDish(number, 0, 2);

SetTimer(1015, 400, NULL); // 开始计时，每400毫秒一步 }

（3）对盘子进行设置：

void CMyDlg::OnR3() {

// 设置三个盘子

SetDishNumber(3);

}

6

void CMyDlg::OnR4() {

// 设置四个盘子

SetDishNumber(4);

}

void CMyDlg::OnR5() {

// 设置五个盘子

SetDishNumber(5);

}

void CMyDlg::OnR6() {

// 设置六个盘子

SetDishNumber(6);

}

void CMyDlg::OnR7() {

// 设置七个盘子

SetDishNumber(7);

}

// 设置盘子个数

void CMyDlg::SetDishNumber(int n){

KillTimer(1015); // 停止计时

pn = 0; // 清空栈

number = n;

for(int i = 0; i < n ; i++){

dish[i] = 0; // 初始化每个盘子都在第一根柱子上

}

Invalidate(FALSE);//重绘

}

（4）显示背景

void CMyDlg::ShowBg(CDC * dc){

//显示背景

CDC pdc, ddc;

pdc.CreateCompatibleDC(dc); // 创建一个临时显示设备

ddc.CreateCompatibleDC(dc); // 创建一个加载盘子的临时显示设备 CBitmap bmp, * obmp;

bmp.LoadBitmap(IDB_BG); // 加载背景图片

obmp = pdc.SelectObject(&bmp); // 将图片显示在设备pdc上。 //显示盘子

int n[] = {0, 0, 0}; // 用于存放每个柱子已显示多少盘子 7

for(int i = 0; i < number ; i++){

CBitmap dbmp, * odbmp;

dbmp.LoadBitmap(IDB_B7 - i); // 加载从大到小第i个盘子图片 odbmp = ddc.SelectObject(&dbmp); // 将盘子显示在设备ddc上。

pdc.BitBlt(10 + 150*dish[i], 225 - n[dish[i]]*20, 140, 15, &ddc, 0, 0, SRCCOPY); // 将ddc拷贝到临时显示设备pdc对应位置上

n[dish[i]] ++;

ddc.SelectObject(odbmp); // 显示完毕，还原设备

}

dc->BitBlt(10, 10, 460, 260, &pdc, 0, 0, SRCCOPY); // 将pdc拷贝到程序显示设备dc上

pdc.SelectObject(obmp); // 显示完毕，还原设备

}

4.总结

对于这次对汉诺塔程序演示的设计，因为是第一次接触mfc可视化程序设计，多少有点棘手，在网上找了挺多关于这方面的演示程序进行参考，通过对他们的程序进行分析理解，学习一些以前自己没有学到的知识，最终将其变成自己的东西。

在实际操作过程中出现了不少的错误，虽然犯了一些错误但是还会有意外的收获感觉也挺有意思。毕竟这些错误在自己的各种寻找方法，网上查找资料，询问老师同学等等，最终将问题解决，先不说结果怎样，其中的过程就挺让人回味的。当然，在具体操作中对这学期所学的数据结构的理论知识得到巩固对高级程序语言设计的mfc可视化程序设计也有了进一步的认识和提高，达到设计的基本目的也发现自己的不足之处在以后的上机中应更加注意。 通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响也让我明白掌握了算法将会有助于提高软件的开发。

8

参考文献：

1辛长安，王颜国. Visual.C.权威剖析--MFC的原理、机制与开发实例.北京：

清华大学出版社2008.5

2候俊杰.深入浅出MFC.湖北：华中科技大学出版社

9

 

第二篇：汉诺塔 C++课程设计报告

淮阴工学院

C++程序设计课程设计报告 选题名称: 汉 诺 塔 系（院）: 计 算 机 工 程 系 专 业: 通 信 工 程 班 级: 通信XXXXX 姓 名: XXXXXX 学 号: XXXXXXXXXX 指导教师: 赵建洋 于长辉 学年学期: 200XX ~ 20XX 学年 第 XX 学期

设计任务书

指导教师（签章）：

年月

摘要：

关于汉诺塔，在印度有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针，印度教的主神梵天在创造世界的时候，在其中一根针上从上到下地穿好了64个金盘。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那跟针上移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。故传说中的汉诺塔问题也被称谓“世界末日问题。” 后来，这个传说就演变为汉诺塔游戏:1.有三根杆子A,B,C;A杆上有若干圆盘。2.每次移动一块圆盘,小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。我们所要求的关于汉诺塔的课程设计，详细讨论了解决此问题的方案，分析解决问题的算法设计，得出了具体的算法，最后输入所需圆盘数，运用递归与非递归算法得出结果。在程序设计中，为了处理重复性的计算，最常采用的办法是组织迭代循环。除此之外，往往还可采用递归计算的方法，特别是在非数值领域中更是如此。除了可调用的其他程序外，还可以直接或间接调用自身的程序称为递归程序。实质上，递归也是一种循环结构，他把“较复杂”情形的计算归结 为“较简单”情形的计算，一直归结到“最简单”情形的计算，并得到计算结果为止。就某种意义而言，递归是一种比迭代循环更强的循环结构。可以证明每个迭代程序原则上总可以转换成与他等价的迭代程序。但就效率而言，递归程序的实现往往要比 迭代程序耗费更多的时间与存储空间。所以在具体实现是，又希望尽可能把递归程序转化成等价的迭代程序，从而提高程序的时空效率。

关键词：每次仅能移动一块；小的在上，大的在下；递归；非递归；迭代循环；递归循环；效率

目 录

1 课题综述： ........................................................................................................................ 1

1.1 课题来源： ........................................................................................................................................ 1

1.2 课题意义： ........................................................................................................................................ 1

1.3 预期目标： ........................................................................................................................................ 1

1.4 当前问题： ........................................................................................................................................ 2

2 系统分析： ........................................................................................................................... 2

2.1 知识基础： ........................................................................................................................................ 2

2.2 基本思路： ........................................................................................................................................ 3

2.3 总体方案： ........................................................................................................................................ 4

3算法设计： ............................................................................................................................ 5

3.1 递归方法： ........................................................................................................................................ 5

3.2 非递归法： ........................................................................................................................................ 5

3.3 详细流程： ........................................................................................................................................ 5

4 程序调试： ........................................................................................................................... 7

4.1 调试过程： ........................................................................................................................................ 7

4.2 发现问题： ........................................................................................................................................ 8

4.3 解决办法： ........................................................................................................................................ 9

总 结 ................................................................................................................................. 10

致 谢 ................................................................................................................................. 11

参考文献 ................................................................................................................................. 12

《C++程序设计课程设计报告》

1 课题综述

1．1 课题来源

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必在大片上面，当所有的金片都从梵天穿好的那根针上移动到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。故汉诺塔问题又被称为“世界末日问题。”而这个古老的问题正好可以运用我们这学期所学的C语言中的递归问题来解决。

这是一个典型的问题。由于问题中给出的圆盘移动条件是：一次仅能移动一个盘，且不允许大盘放在小盘上面，这样64个盘子的移动次数为：

18，446，744，073，709，511，615（次）

这是一个天文数字，若每一微秒可以计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但目前计算机的速度还不能解决64层的汉诺塔。

1．2 课题意义

这次课程设计，可以培养我们独立自主的学习能力，实事求是的学习态度，严谨治学的学习作风，通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时课程设计还可以弥补我们自身在实践时所缺少的经验。这次对于汉诺塔这个问题的研究是我在C语言课程学习中递归函数的一次实际运用，对我的递归函数的理解会有更多的帮助。

1．3 预期目标

在一周的时间内，通过自己和同学的编写与调试，并在多与老师交流经验和编程心得，咨询辅导老师的意见的情况下编写出汉诺塔递归与非递归两种方法并存的C++ 1

《C++程序设计课程设计报告》

程序。

1．4 当前问题

这是一个典型的问题。由于问题中给出的圆盘移动条件是：一次仅能移动一个盘，且不允许大盘放在小盘上面，这样64个盘子的移动次数为：

18，446，744，073，709，511，615（次）

这是一个天文数字，若每一微秒可以计算（并不输出）一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但目前计算机的速度还不能解决64层的汉诺塔。

2 系统分析

2．1 知识基础

递归：当在一个函数A的定义中出现调用函数A的情况时，或在A函数的定义过程中调用B函数，而在B函数的定义过程中又调用了A函数 ，这种调用关系称为递归调用。

在设计递归程序函数时，通常是先判断递归结束条件，再进行递归调用。其执行过程比较复杂，都存在连续递归调用（参数入栈）和回推过程。在使用递归的方法设计程序时，在递归程序中一定要有递归结束条件；否则，在执行程序时，会产生无穷无尽的递归调用。

2．2 基本思路

递归思想

汉诺塔是典型的递归程序设计题，设要解决的的汉诺塔共有Ｎ个圆盘，对Ａ杆上的全部Ｎ个圆盘从小到大顺序编号，最小的圆盘为１号，次之为２号，依次类推，则最下面的圆盘的编号为Ｎ。

第一步：先将问题简化。假设Ａ杆上只有一个圆盘，即汉诺塔只有一层Ｎ=１，则只要将１号盘从Ａ杆上移到Ｂ杆上即可。

第二步：对于一个有Ｎ（Ｎ＞１）个圆盘的汉诺塔，将Ｎ个圆盘分成两部分：上面的Ｎ－１个圆盘和最下面的Ｎ号圆盘。

第三步：将“上面的Ｎ－１个圆盘”看成一个整体，为了解决Ｎ个圆盘的汉诺塔，可以按下面图示的方式进行操作：

2

《C++程序设计课程设计报告》

图2-1 移动N-1个盘移到C上

图2-2 移动第N个盘到B上

图2-3 将C上N-1个盘移到B上

非递归思想

对于汉诺塔问题的解决，一般采用递归的方法解决，比较容易分析和实现。现在我们采用非递归的思想对其进行分析。首先测试递归程序，分析移动的盘子的号数和盘子每一次移动的方向。

1．分析盘子移动的基本规律：通过对递归程序的测试，我们不难得出n个盘子的移动序列（可以叫H数列，用H（n）表示）：1，2，1，3，1，2，1，4，1，2，1，3，1，2，1，5，1，2，1，3，1，2，1，4，……，对移动序列进行分析和归纳发现，1占据所有的奇数位，2占据所有序号可被2整除而不能被4整除的位，3占据所有序号可被4整除而不能被8整除的位……，m占了能被2^(m-1)整除而不能被2^m整除的所有的位置……，由此可得重要推论，对m=（（p*2^k） + 2^（k-1））= 2^(k-1)*(p*2+1)，

3

《C++程序设计课程设计报告》

H(m)=k，其中p=0，1，2……(n-1)/2，k代表第K个盘子，m能被2^(k-1)整除，但不能被2^k整除。对于n个盘子，总共需要移动2^n-1。对于推论我们可以很容易通过数学归纳法进行证明（证明过程略）。通过刚才的分析我们可以随机得到某一步所移动的盘子。

2．分析盘子的移动方向：对递归程序的测试可以发现，在盘子总数为n的情况下，1号盘子的移动方向总是一定的，也就是说，总是按照1->2->3->1或者1->3->2->1的方向移动，从而想到是否所有的盘子的移动方向也总是一定的。再次进行测试，又可以发现，奇数号盘子的移动方向都相同，同样偶数号盘子的移动方向也相同，而奇数号和偶数号盘子的移动方向正好相反。进一步发现盘子的移动方向是由盘子总数n决定的，n为偶数时奇数号的盘子向右移动，偶数号的向左移动；n为奇数时奇数号的盘子向左移动，偶数号的向右移动。例如最大号的盘子，它总是只移动一次，并且是从1号柱子移到3号柱子。也可以用数学归纳法进行证明。

3．通过上面的分析，我们已经得到了盘子移动序列和每个盘子的移动方向，而每个盘子的起始状态都是相同的，都在1号柱子上，这样就可以随机取得某一步移动的具体情况了。对第m ( m=((p*2^k) + 2^(k-1))= 2^(k-1)*(p*2+1) ) 次移动盘子，移动的盘子是第k号，而且这是序列中第p+1个k号盘子，也就是说此前k号盘子已经移动了p次，那么k号盘子现在就在 (1+p*(-1)^(n+k+1))%3号柱子上，他将被移动到(1+(p+1)*(-1)^(n+k+1))%3号柱子上，其中(-1)^(n+k+1)表示向左或是向右移，这取决于n和k的奇偶性。于是，我们就可以随机得到第m步的情况：k号盘子从第(1+p*(-1)^(n+k+1))%3号柱子移动到第(1+(p+1)* (-1)^(n+k+1))%3号柱子上。

2．3 总体方案

先输出一个登录选择界面，如下

图2-4 登陆界面

4

《C++程序设计课程设计报告》

3 算法设计

3．1 递归方法

首先我先把我所编写的递归程序给出：

void move(char X,char Y)

{

cout<<"移动"<<X<<"柱———>"<<Y<<"柱"<<'\n'; }

void DG(int n,char A,char B, char C)

{

if(n==1) move(A,C);

else{

DG(n-1,A,C,B);

move(A,C);

DG(n-1,B,A,C);

}

}

3．2 非递归法

首先我先把我所编写的非递归程序给出： void FDG()

{

cout<<"请输入盘子的个数（1~64）：";

cin>>N;

int **t=new int*[3];

t[1]=new int[N+1];

t[0]=new int[N+1];

t[2]=new int[N+1];

t[0][0]=MaxN;

t[1][0]=MaxN;

t[2][0]=MaxN;

for(int count=1;count<=N;count++)

{

t[0][count]=N-count+1;

t[1][count]=0;

t[2][count]=0;

}

if(N%2!=0)

{

jishu=2;oushu=1;

}

5

《C++程序设计课程设计报告》

else

{

jishu=1;oushu=2;

}

int F,G;

F=0;

G=jishu+F;

t[0]=&t[0][N];

while(*(t[0])!=*(t[1]))

{

cout<<"移动"<<F+1<<"柱 ———>"<<G+1<<"柱"<<endl; *(++t[G])=*(t[F]);

*(t[F]--)=0;

switch(G)

{

case 2:

if(*(t[0]) < *(t[1])) F=0;

else F=1;

break;

case 1:

if(*(t[0]) < *(t[2])) F=0;

else F=2;

break;

case 0:

if(*(t[2]) < *(t[1])) F=2;

else F=1;

break;

}

if(*(t[F])%2!=0)G=fmod(F+jishu,3);

else G=fmod(F+oushu,3);

}

char c;

cin>>c;

}

6

《C++程序设计课程设计报告》

3．3 详细流程

图3-1 流程图

4 程序调试

4．1 调试过程

先输出一个登录选择界面，如下

7

《C++程序设计课程设计报告》

图4-1 登陆界面

输入1后发现只能进行一次运算，不能在同一界面内进行多次运算

4．2 发现问题

由于代码分别保存在不同的头文件中，如何协调各个头文件之间代码的通讯是个很难解决的问题，曾经一度想放弃使用头文件，但如此一来会造成代码全部堆在一起，很难阅读和编写。

系统过于复杂，函数之间的调用变得非常频繁和复杂，要时刻跟踪程序执行到哪个位置，下一步会调用哪个函数，这些关系都要在头脑中非常清晰才可能完成编写代码，而不被搞糊涂。经常要在大堆的代码中找到程序执行到哪一行的困难可想而知，特别是当出现内存地址错误时，还要跟踪地址或变量是否被赋值。

如图：

图4-2 登陆界面

8

《C++程序设计课程设计报告》

4．3 解决办法

我在主函数中加了两个main()函数，使程序可以持续进行计算

图4-3 登陆界面

9

《C++程序设计课程设计报告》

总 结

这次对于汉诺塔的课程设计我有很多心得和体会，编写了很多行的代码最后写出一个程序觉得很有成就感。自己对C语言的掌握提高到了一个新的水平，能够应用C语言编写出一个实用的程序，很大程度上提高了程序综合设计能力、分析能力和编程能力。掌握了很多新的编程技巧，积累了一些编程经验这些技巧和经验对于以后的课程都是很重要的。因此我觉得这次课程设计虽然困难不小，但收获很大。编写类似图书借阅管理的程序其中最重要的一个方面就是要认真，认真编写代码可。以大大减少错误的出现；其次是要有耐心，勇于克服困难，不断解决问题，面对困难要永不退缩，迎难而上；再次是要有清晰的思维，能够理清各个函数之间的关系，明确各个函数的职能；最后还要和同学多交流合作，多参考书籍。

10

《C++程序设计课程设计报告》

致 谢

同学的帮忙，在他们的帮助下我才能完成这次课程设计。在这次课程设计中我遇到了很多困难，在遇到这些困难的时候，我觉得很烦，有点想放弃。但我们宿舍的人安慰我说：“加油，努力就一定能完成的。”在他们的鼓励下，我又重新鼓起勇气，继续做下去，所以我要感谢我们宿舍的舍友。在完成程序的过程中难免会出现好多问题，俗话说：“当局者迷，旁观者清”。我总是发现不了自己的错误，然后我就会让同学帮我看看。最后在同学的帮助下终于把程序做出来了。我对他们深表感谢。我要感谢我们指导老师，他给我提出了许多宝贵的意见。在他的帮助下我可以把它搞得更加完美。在这里我感谢每一个帮助过我的人，感谢他们对我的帮助。同时我还要感谢指导我们上机做实验的老师们，他们真得好辛苦，在炎炎酷暑之中还要给我们指导的老师们。

11

《C++程序设计课程设计报告》

参考文献

1． 覃征,王志敏.程序设计方法与优化.西安:西安交通大学出版社,2004

2． 彭四伟,赵彤洲,高巍.C语言程序设计.北京:清华大学出版社,2002

3． 网冠科技.C语言时尚编程百例.北京:机械工业出版社,2004

4． 胡正国,吴健,邓正宏.程序设计方法学.北京:国防工业出版社,2003

5． 于永彦，刘作军，于长辉编著.C++程序设计，2006

6． 求是科技.C&C++实效编程百例.北京:人民邮电出版社,2004

7． Stevens.A.C++大学自学教程.北京:电子工业出版社,2004

12

指导教师评语

1