算法设计技能训练网络1121胡伟

1、算法设计技能训练实习报告题目 ： 汉诺威塔系 （院） : 计算机工程学院专业 ：班级 ：网络 1121学号 ：姓名 ：指导教师 ：学年学期 : 2013 2014 学年 第 1 学期2013年 12 月 6 日算法设计技能训练任务书课题 名称设计 目的1、 通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握 算法设计的知识。2、 能够针对某一具体问题，设计算法进行解决。3、 锻炼实践动手能力，提高解决问题的能力。实验 环境硬件： 1、PC机，奔腾以上 CPU， 512MB 以上内存， 80G以上硬盘；软件： Visual C+编程工具任务 要求1）界面友好，函数功能要划分好2）总

2、体设计应画流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的 程序是没有价值的。工作进度计划序号起止日期工作内容12013.12.2任务下达，查阅文献资料22013.12.22013.12.4总体设计、素材搜集、课题详细设计、调试32013.12.52013.12.6完善设计、撰写报告42013.12.6答辩指导教师（签章）：年 月 日摘要汉诺威塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天 创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着 64 片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大

3、小顺序重新摆放在另一 根柱子上。 并且规定，在小圆盘上不能放大圆盘， 在三根柱子之间一次只能移动 一个圆盘。 所以，设计的目的是运用方法来移动盘子， 使原有上小底大的一个柱 子上的盘子，每次移动一个， 且小盘子要放在大盘子的上面， 移动到另一个柱子 上，其中只能借助低三根柱子。 通过 C+语言来编写程序来实现至少 5 层的调整 过程。功能：显示汉诺威塔的调整过程。实施：搭好框架，确定人机对话界面， 确定函数个数，实行调整。（ 1）课题概述（课题的来源，预期目标，面对要解 决的问题和需要去解决的问题所用的方法） （2）需求分析（设计的思路，方案， 以及功能）（ 3）设计思路与算法（ 4）运行结果

4、（ 5）附录关键词 汉诺威塔 调整 C+ 益智 递归 选择 数据结构33目录引言 51 汉诺威塔的概述 52 需求分析 72.1 分支结构IF 语句 72.2 分支结构SWITCH语句 82.4 问题概述 102.5 三层的汉诺威塔演示 103 算法与代码 123.1 分析 123.2 代码与注释 143.2.1Hanoi 函数关于递归调整的代码 ： 143.2.2 自动移动的汉诺威塔函数可以根据输入的层数进行处理 154 运行结果 20总结 22附录 ： 23参考文献 33指导教师评语 34引言汉诺威塔是一款集娱乐与运算的智力游戏，他不仅可以在闲时帮助我们度过美好的时 光，还可以在玩的过程中

5、锻炼我们的思维，开发你的思维。本课题的设计是为了解决 n 层汉诺威塔调整的解决方案， 通过循环， 选择， 递归等算法 来来构造不同的函数， 主要的是调整， 因此最主要的函数 hanoi 通过递归的方法来实现每层 的调整，同时每层的移动也涉及了数组和 if 的选择， swith 的选择。通过使用者输入汉诺 威塔的层数，根据不同层数进行处理。来源：法国数学家爱德华卢卡斯曾编写过一个印度的古老传说： 在世界中心贝拿勒斯 (在印 度北部)的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候， 在其中一根针上从下到上地穿好了由大到小的 64 片金片，这就是所谓的汉诺塔。不论白天 黑夜，

6、总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上， 小片必须在大片上面。 僧侣们预言， 当所有的金片都从梵天穿好的那根针上移到另外一根针 上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 1 不管这个传说的可信度有多大，如果考虑一下把 64 片金片，由一根针上移到另一根针上， 并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有 n 片，移动次数是 f(n). 显然 f(1)=1,f(2)=3,f(3)=7 ，且 f(k+1 ) =2*f(k)+1 。此后不难证明 f(n)=2n-1 。 n=64 时， 假如每秒钟一次， 共需多长

7、时间呢？一个平年 365 天有 31536000 秒，闰年 366 天有 31622400 秒，平均每年 31556952 秒，计算一下， 1.844674407584554049253.855 年这表明移完这些 金片需要 5845 亿年以上， 而地球存在至今不过 45 亿年，太阳系的预期寿命据说也就是数百 亿年。真的过了 5845 亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙 宇等，都早已经灰飞烟灭。1 汉诺威塔的概述11 汉诺威塔及其调整的示意图如图 1-1 所示为初步设想的效果图图 1-11.2 问题内容汉诺塔问题： 这是一个古典的数学问题， 是一个用递归方法解题的典型例

8、子。 问题是这样的： 古代有一个梵塔， 塔内有三个座、 、，开始时座上有个盘子， 盘子的大小不等， 大的在下， 小的在上。 有一个老和尚想把这个盘子从座移动到座。 但每次一允许移 动一个盘子，且在移动的过程中在个座上都始终保持大盘在下，小盘在上。1.3 预期目标通过编写汉诺威塔的程序代码， 来了解汉诺威塔的本质和历史， 来加深对程序种方法的理解， 并且熟悉所学过的书本知识。可以运行出友好的界面，并且可以根据界面的提示输入任意的层数，当输入的层数不同时， 所运行的步骤也不同，显示出移动的顺序，还可以自动演示移动的过程。1.4 遇到的问题 汉诺威塔是一个古老的问题， 它不仅是一个有趣味的数学问题，

9、 而且是关于计算机编程的一 个课题。在编程中面对的主要问题有以下几个：采用递归对移动的显示采用 if 和 switch 语句来对汉诺威塔的每一层进行处理 汉诺威塔的显示1.5 学要解决的技术 我们需要去解决以上的主要问题， 通过 c+的递归算法， 和一些基本的语句， 尽管有些重复， 但也是必要的。2 需求分析2.1 分支结构 if 语句If 语句的表达方法：if （表达式 1 ）语句 1else if （表达式 2）语句 2else if （表达式 3）语句 3else if （表达式 m）语句 melse 语句 n在每个语句中，可以有多个语句，但需要加上大括号 对于可能发生的事情，我们平时经

10、常会说“如果，那么”。语文里， 我们叫它条件 复句。“如果”之后的内容我们称为条件，当条件满足时，就会发生“那么”之后的事件。 我们来看这样一句英语： If mark90, cout ” GOOD”! endl. 把它翻译成中文就是：如 果分数大于 90，则输出 GOO。D其实在程序设计中， 也是用“如果”来描述可能发生的情况的。 它和刚才的那句英语很相似， 具体的语法格式是：我们把若干句语句放在一个大括号中， 称为语句块。 运行到该 if 语4.1.1 ）来表示 if句，当条件满足时，就会执行语句块内的内容。我们也可以用流程图（图 语句。请注意， if 语句的结束是没有分号的，分号只是属于语

11、句块中的语句2.2 分支结构 Switch 语句在 C+中，也有这样的开关，那就是 switch 语句。它能够很简捷地描述出多岔路口的情况。 具体的语法格式为：switch （表达式）case 常量表达式 1：语句块 1；break ；case 常量表达式 n：语句块 n；break ；default语句块 n+1；在 switch 语句中， 我们要记住四个关键词， 分别是 switch 、case 、default 和 break 。switch 是语句的特征标志 （图中标作 sw）；case 表示当 switch 后的表达式满足某个 case 后的常量 时，运行该 case 以后的语句块。

12、要注意，任意两个 case 后的常量不能相等，否则 switch 将不知道选择哪条路走。 default 表示当表达式没有匹配的 case 时，默认（ default ）地运 行它之后的语句块（图 4.4.1 中未标出）； break 表示分岔路已经到头，退出 switch 语句。2.4 问题概述这个问题在盘子比较多的情况下， 很难直接写出移动步骤。 我们可以先分析盘子比较少 的情况。假定盘子从大向小依次为：盘子1，盘子 2， . ，盘子 64。如果只有一个盘子，则不需要利用 B座，直接将盘子从 A移动到 C。如果有 2 个盘子， 可以先将盘子 1 上的盘子 2 移动到 B；将盘子 1移动到

13、c；将盘子 2 移动到 c。这说明了： 可以借助 B将 2 个盘子从 A移动到 C，当然，也可以借助 C将 2 个盘子从 A移动到 B。如果有 3 个盘子，那么根据 2 个盘子的结论，可以借助 c 将盘子 1 上的两个盘子从 A 移动到 B；将盘子 1 从 A移动到 C，A变成空座；借助 A座，将 B 上的两个盘子移动到 C。这 说明：可以借助一个空座，将 3 个盘子从一个座移动到另一个。如果有 4 个盘子，那么首先借助空座 C，将盘子 1 上的三个盘子从 A 移动到 B；将盘子1 移动到 C， A变成空座；借助空座 A，将 B 座上的三个盘子移动到 C。 上述的思路可以一直扩展到 64个盘子

14、的情况： 可以借助空座 C将盘子 1 上的 63个盘子从 A 移动到 B；将盘子 1移动到 C，A变成空座；借助空座 A，将 B座上的 63 个盘子移动到 C 其实算法非常简单，当盘子的个数为n时，移动的次数应等于 2n 1 （有兴趣的可以自己证明试试看） 。后来一位美国学者发现一种出人意料的简单方法， 只要轮流进行两步 操作就可以了。 首先把三根柱子按顺序排成品字型， 把所有的圆盘按从大到小的顺序放在柱 子 A 上，根据圆盘的数量确定柱子的排放顺序： 若 n 为偶数， 按顺时针方向依次摆放 A B C； 若 n 为奇数，按顺时针方向依次摆放 A C B 。按顺时针方向把圆盘 1 从现在的柱子

15、移动到下一根柱子， 即当 n 为偶数时， 若圆盘 1 在柱子 A，则把它移动到 B；若圆盘 1在柱子 B，则把它移动到 C；若圆盘 1 在柱子 C，则把 它移动到 A。接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆 盘移动到空柱子上， 当两根柱子都非空时， 移动较小的圆盘。 这一步没有明确规定移动哪个 圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。反复进行操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是 按照移动规则向一个方向移动金片：如3 阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC2.5 三层的汉诺威塔演示图 2-2 为演

16、示的示意图先将最小的放到第二根柱子上再将中间的放到第三根柱子上再将第二根柱子上最小的放到第三根柱子上图 2-2 然后把做大的盘子放到第二根柱子上，后面依次类推 3 算法与代码3.1 分析 递归算法与 hanoi 函数 第一步：总体的递归大体的流程图如图 3-1 所示思路：首先，如果要把最大的盘子也就是最底端的盘子移到另一个柱子上，则需要先把上面的 n-1 层的盘子移走。再如此去移动剩下的盘子。第二步：对递归的详细处理与应用题目要求为： 显示九层的汉诺威塔的移动过程。则要构建移动函数 move（），并且找到判断条件，进行选择。 详细的流程图如 3-2 所示3.2 代码与注释3.2.1Hanoi

17、函数关于递归调整的代码 ：void Hanoi(int n,char A,char B,char C) / 输入要显示移动的层数和三个底座 if(n=1)coutmoveAtoCendl; / 采用递归， 如果 n=1 则把 A 上盘子移 到 C 的上面。elseHanoi(n-1,A,C,B);coutmoveAtoC=0;n-)switch(an)case 0:coutsetw(24)初始化函数 显示函数 过关条件判断函数switch 的选择输出不同行数，显示不同的塔形。显示函数，输出塔的形状;break;case 1:coutsetw(24)1;break;break;break;bre

18、ak;case 2:coutsetw(24)case 3:coutsetw(24)case 4:coutsetw(24)case 5:coutsetw(24)- ;break;case 6:coutsetw(24)switch(bn)case 0:coutsetw(24)6-;break;break;case 1:coutsetw(24)1-;break;case 2:coutsetw(24) -2- ;break;case 3:coutsetw(24) -3- ;break;case 4:coutsetw(24) -4- ;break;case 5:coutsetw(24)- ;break;

19、case 6:coutsetw(24)6-;break; switch(cn)case 0:coutsetw(24)endl;break;case 1:coutsetw(24)1-endl;break;case 2:coutsetw(24) -2- endl;break;case 3:coutsetw(24) -3- endl;break;case 4:coutsetw(24) -4- endl;break;case 5:coutsetw(24)- endl;break;case 6:coutsetw(24)6- endl;break; cout_endl; coutCendl; / A输出三

20、个塔座的不同塔形B根据 an,bn,cn 的不同传递的值来 switch 进行选择，从而显示 A，B，C 底座上的不同 塔形。Act ： cout 请输入你要进行演示的层数 ：（1 代表 3层，2代表 4层，3代表 5层， 4 代表 6 层 ）;cing;输入不正确，请重新输入 !;goto act;if(g4|g1)cout cout - 第 g+2 层的演示 -; coutendlendlendl;coutWelcoming汉诺塔Chushihua(g+1);Show(g+1);cout 请按回车键继续。 ;cin.get();cin.get();Hano(g+2,A,B,C,g+1);c

21、out=0;n-) if(an=0) ax=n; if(bn=0) bx=n;根据输入的不同值进行选择塔层的每一层，形成不同的状if(cn=0) cx=n; switch(Get)case A:if(ax=0)return;elsexch=aax-1; aax-1=0;ax-;break;case B:if(bx=0)return;elsexch=bbx-1; bbx-1=0;bx-;break;case C:if(cx=0)return;elsexch=ccx-1; ccx-1=0;cx-;break;switch(To)case A:aax=xch;break;case B:bbx=xch

22、;break;case C:ccx=xch;break;递归演示函数，显示移void Disk:Hano(int n,char a,char b,char c,int y) / 动后的塔形。if(n=1)coutWelcoming汉诺塔cout第 y+1 层的演示 -;coutendlendlendl;Mov(a,c,y);Show(y+1);cout 请按回车键继续。 endl;cin.get();elseHano(n-1,a,c,b,y);coutWelcoming汉诺塔cout第 y+1 层的演示 -;coutendlendlendl;Mov(a,c,y);Show(y+1);cout

23、请按回车键继续。 endl;cin.get();Hano(n-1,b,a,c,y);对所输入的层数，输出原始塔的形状，并且进行移动演示操作。 如图 3-5 ，图 3-6 所示图 3-5图 3-64 运行结果以三层为例：初始的运行结果 ：如图 4-1 ，图 4-2, 图 4-3 ，图 4-4 形成的系列显示图 4-1图 4-2图 4-3图 4-4总结通过这一次对汉诺威塔的课程设计， 我对数据结构的知识和 C+的基础知识又一次复习， 并且从起初的构思， 首先想到如何去移动， 表示出移动的顺序， 再者是用编程来对汉诺威塔 图形的实现， 并且画出汉诺威塔开始的图形， 再画出移动过程中某一步的图形， 最

24、后是实现 后的效果图。 要对汉诺威塔实现连续的移动的演示， 因此又另外写了移动函数与主屏演示的 函数， 从而实现汉诺威塔问题的解法。 对于汉诺威塔的设计与参考， 对于数据结构的编程的 规范化和对于程序的思想思路的开拓有了新的理解。同时， 如果能够设计出更便捷的方法和友好的界面， 那么就更好去做出更加人性化的设计程序。 汉诺威塔是一种益智的游戏， 经过 练习更加会喜爱上它。附录 ：自动演示代码(层数最高 6 层)：#include #include #include class Position / Position public:friend class Disk; void Chushihu

25、a(int x); void Show(int x); / int Pan(int x); / protected:int a6;/ 为了下面用 int b6;int c6;void Position:Chushihua(int x) /初始化函数显示函数 过关条件判断函数switch/的选择输出不同行数，显示不同的塔形。初始化函数int n=5;for(;n=0;n-)an=0;bn=0;cn=0; for(n=x;n=0;n-)an=n+1; void Position:Show(int x) / int n=0; for(n=x;n=0;n-) switch(an) case 0:cou

26、tsetw(24) case 1:coutsetw(24) case 2:coutsetw(24) case 3:coutsetw(24)显示函数case 4:coutsetw(24) 4;break; ;break; - ;break; - ;break;break;case 5:coutsetw(24)- ;break;case 6:coutsetw(24)switch(bn)case 0:coutsetw(24)6-;break;break;case 1:coutsetw(24)1-;break;case 2:coutsetw(24) -2- ;break;case 3:coutsetw

27、(24) -3- ;break;case 4:coutsetw(24) -4- ;break;case 5:coutsetw(24)- ;break;case 6:coutsetw(24)6-;break; switch(cn)case 0:coutsetw(24)endl;break;case 1:coutsetw(24)1-endl;break;case 2:coutsetw(24) -2- endl;break;case 3:coutsetw(24) -3- endl;break;case 4:coutsetw(24) -4- endl;break;case 5:coutsetw(24)

28、- endl;break;case 6:coutsetw(24)6- endl;break; cout_endl; coutABCendl;int Position:Pan(int x) /过关条件判断函数来判断是否运行正确int n=x;if(a0=0&b0=0&cn=n+1) return 1;else return 0;class Disk:public Positionpublic:void hanoi();/ Disk/主界面函数，在主函数中调用void Move(char a,char c,int m);/移动函数void Mov(char Get,char To,int y);/

29、演示移动函数void Hano(int n,char a,char b,char c,int y); /递归演示函数;void Disk:hanoi() / 主界面函数int m=0;int g=0;act:cout 请输入你要进行演示的层数 ：(1 代表 3层，2代表 4层，3代表 5层， 4 代表 6 层 );cing;输入不正确，请重新输入!;goto act;if(g4|g1)cout cout - 第 g+2 层的演示 -; coutendlendlendl;coutWelcoming汉诺塔Chushihua(g+1);Show(g+1);cout 请按回车键继续。 ;cin.get

30、();cin.get();Hano(g+2,A,B,C,g+1);cout 演示完毕！请按回车键。 ;cin.get();void Disk:Move(char x,char z,int m)/ 移动函数，对塔的每层进行处理，形成不同的塔 形和移动。int n=0;if(x=A&z=C)for(n=0;n=6;n+)if(an=m &an+1!=0)cin.get();cout 操作不正确！请按回车键继续。 endl;/ 手动的部分 cin.get();return; for(n=0;nm) cin.get(); cout 操作不正确！请按回车键继续。 cin.get(); return; f

31、or(n=0;n=6;n+)if(an=0) an-1=0;break; for(n=0;n=5;n+)if(cn=0) cn=m;break; if(x=A&z=B) for(n=0;n=6;n+) if(an=m&an+1!=0)cin.get();cout 操作不正确！请按回车键继续。 cin.get();return; for(n=0;nm) endl;endl;cin.get();cout 操作不正确！请按回车键继续。 endl; cin.get(); return; for(n=0;n=5;n+)if(an=0) an-1=0;break; for(n=0;n=5;n+)if(bn

32、=0) bn=m;break; if(x=B&z=C) for(n=0;n=6;n+)if(bn=m&bn+1!=0)cin.get();cout 操作不正确！请按回车键继续。 endl; cin.get();return; for(n=0;nm)cin.get();cout 操作不正确！请按回车键继续。 endl; cin.get();return; for(n=0;n=5;n+)if(bn=0) bn-1=0;break; for(n=0;n=5;n+)if(cn=0) cn=m;break; if(x=B&z=A) for(n=0;n=6;n+) if(bn=m&bn+1!=0)cin.

33、get();cout 操作不正确！请按回车键继续。 endl; cin.get();return; for(n=0;nm) cin.get(); cout 操作不正确！请按回车键继续。 endl; cin.get(); return; for(n=0;n=5;n+)if(bn=0) bn-1=0;break; for(n=0;n=5;n+)if(an=0) an=m;break;35 if(x=C&z=A)for(n=0;n=6;n+)if(cn=m&cn+1!=0)cin.get();endl;endl;cout 操作不正确！请按回车键继续。cin.get();return;for(n=0;nm)cin.get();cout 操作不正确！请按回车键继续。cin.get();return;for(n=0;n=5;n+)if(cn=0) cn-1=0;break;for(n=0;n=5;n+)if(an=0)an=m;break; if(x=C&z=B)for(n=0;n=6;n+)if(cn=m&cn+1!=0)36cin.get(); cout 操作不正确！请按回车键继续。 cin.get();return;for(n=0;nm) cin.get(); cout 操作不正确！请按回车键继续