汉诺威塔数据结构课程设计.docx

1、汉诺威塔数据结构课程设计数据结构课程设计题 目： 汉诺威塔 班 级： 姓 名： 学 号： 同组人姓名： 起 迄 日 期: 课程设计地点: 指导教师： 评阅意见：成绩评定：评阅人： 日期：目 录一、 前言 二、 系统功能分析 2.1 汉诺威塔问题 2.2 解析汉诺威塔问题 三、 总体设计四、 详细设计五、 系统实现六、 结论结束语参考文献附录 一、 前言汉诺威塔是一款集娱乐与运算的智力游戏，它不仅能使人在休闲的时候放松心情，而且还能在玩的过程中不断的提高你的思维能力。本设计着手于怎么运算出n层汉诺威塔的解决方案，然而经过不断的调试以及自己的在做的过程中也不断的去尝试着怎么自己能过汉诺威塔多少层，

2、经过几个星期的努力，以及不断的调试，我发现我能把7层的汉诺威塔玩过已经是很不错了。如想玩下去的，只要你能记得那些步骤，那么这汉诺威塔也不是什么难的了。本设计如有差错，望各位谅解，在此我诚恳的希望大家能提出意见，以便我能及时修改。汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数

3、)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。二、 系统功能分析 科技奖励工作是推动科学技术进步的一项重要的激励机制，对促进国家和地方社会经济发展，调动广大科研工作者的积极性具有重大作用。实践证明，网络技术的运用有利于更快地促进科技成果的利用，从而有利于发展科技生产力，繁荣国家和地方社会经济生活。本设计可以实现从2到n层的汉诺威塔以供玩家思考和了解其运行过程。本设计通过一系列的实践证明了前九层汉诺威塔的准确性，根据本人推论，以后的每一层的准度应该与事实相符，鉴于工作量实在太大，故而敬请各为原谅！2.1汉诺威塔问题n

4、阶汉诺威塔问题：有三根杆子A,B,C。A杆上有n个碟子 每次移动一块碟子,小的只能叠在大的上面 把所有碟子从A杆全部移到C杆上经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC2.2解析汉诺威塔问题下面用归纳法证明n阶汉诺威塔问题，可以用n层二叉树描述，而且它的解就是该二叉树的中序遍历序列。用一个四元组(n,A,B,C)表示把n个盘子从A搬到C,中间可以借助B的n阶汉诺威塔问题。其中A、B、C的地位是相对的，第一个表示起始位置，最后一个表示终止位置，中间表示过渡位置。例如(n,A,B,C)表示把n个盘子从B搬到C，

5、中间可以借助A的n阶汉诺威塔问题。用一个三元组(n),A,B)表示把第n个盘子从A直接搬到B。假设有两个盘子，要把两个盘子从A搬到C，即(2,A,B,C),就必须先把第1个盘子从A搬到B，即(1),A,B),再把第2个盘子从A直接搬到C，即(2),A,C),最后把第1个盘子从B直接搬到C，即(1),B,C),序列(1),A,B),(2),A,C),(1),B,C)正好是以(2,A,B,C)为根，以(1,A,C,B)和(1,B,A,C)为左右孩子的二叉树的中序遍历序列(访问结点时，去掉过渡位置，盘子数加括号)(见图1)，其中双亲结点与左孩子的关系是，盘子个数减1，过渡位置和终止位置交换，与右孩子

6、的关系是，盘子个数减1，起始位置和过渡位置交换。假如有n个盘子时，结论成立。现在假设有n+1个盘子。要把n+1个盘子从A搬到C，即(n+1,A,B,C)，必须先把前n个盘子从A搬到C，即(n+1),A,C)，最后把前n个盘子从B搬到C，即(n,A,B,C)。序列(n,A,C,B),(n+1),A,C),(n,B,A,C)正好是以(n+1,A,B,C)为根，以(n,A,C,B)和(n,B,A,C)为左右孩子的二叉树的中序遍历顺序(中序遍历左子树，访问根结点，中序遍历右子树)(见图2)。而左右子树都是n阶汉诺威塔问题，结论也成立。到此证明完毕。如下所示：图（a）汉诺威塔问题状态图 图（b）n阶和3

7、阶汉诺威塔问题状态图 三、 总体设计首先建立一个程序。然后创建类Hanoi，将公有继承和私有继承分好类。其次建立各类函数：void Hanoi:move(int numDisk,string init,string desti,string templ)void Hanoi:moveOne(int numDisk,string init,string desti)void Hanoi:Solve ()最后构建主函数，应用各种函数，使整个程序能运行。解决图3.1从而达到图3.2所示画面即我们这个程序所要完成的功能。图3.1 汉诺威塔游戏开始界面图3.2 汉诺威塔游戏结束界面四、 详细设计汉诺威塔

8、程序代码：#include iostream#include stringusing namespace std;class Hanoi /定义类Hanoipublic : /共有成员 hanoi(int disks) totalDisks=disks; void Solve();private : /私有成员 int totalDisks; void move(int numDisk,string init,string desti,string templ) ;/移动函明void moveOne(int numDisk ,string init,string desti) ; ; void

9、 hanoi:move(int numDisk,string init,string desti,string templ) /定义移动函数 if(numDisk=1) moveOne(numDisk,init,desti); else move(numDisk-1,init,templ,desti); moveOne(numDisk,init,desti); move(numDisk-1,templ,desti,init); void hanoi:moveOne(int numDisk,string init,string desti) cout移动塔层 numDisk from init

10、to destiendl;void hanoi:Solve () string init=A,desti=C,templ=B; move(totalDisks,init,desti,templ);int main(int argc, char* argv) /主函数 int a; loop:cout请输入你想要输入的汉诺威塔的层数：a; cout塔层数从上至下编号为1、2、3、4、5、6,endl; hanoi hanoi(a); hanoi.Solve(); goto loop; return 0;五、 系统实现程序运行如下：图5.1 程序运行界面图5.2 4层汉诺威塔运行界面六、结论 通过

11、这次课程设计，让我对数据结构有了新一层的了解，让我明白各种函数以及类的应用，明白了算法对程序的重要性。由于本次程序是解决一个游戏的过关问题，所以必须亲自玩那个游戏，从而推出程序的重要性。这玩游戏的过程让我感觉到汉诺威塔的趣味性，这是一个集智益与娱乐于一体的游戏，很值得一玩。 本程序运行13层以下速度很快，13层以上则要等一段时间了。图7.1结 束 语本次课程设计，使我对从汉诺威塔设计方案到设计的基本过程的设计方法、步骤、思路、有一定的了解与认识。在课程设计过程中，我基本能按照规定的程序进行，先针对汉诺威塔设计收集、调查有关资料，其间，与同学之间对递归的算法讨论、修改，再讨论、再修改，最后定案。

12、最终用c+语言实现了可视化的汉诺威塔算法。程序设计达到了专业学习的预期目的。课程设计之后，我普遍感到不仅实际动手能力有所提高，更重要的是进一步激发了我对专业知识的兴趣，并能够结合实际存在的问题在专业领域内进行更深入的学习。 对我们计算机专业的本科生来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。通过课程设计，让我找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型。参考文献 1数据结构（C语言版）作者：严蔚敏 吴伟民 出版社：清华大学出版社 时间：2006/102 C+程序设计 作者：郑莉，董渊，张瑞丰 出版社：清华大学出版社 时间：2003/12 附录