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

0 数数据据结结构构课课程程设设计计 题 目： 汉诺威塔 班 级： 姓 名： 学 号： 同组人姓名： 起 迄 日 期: 课程设计地点: 指导教师： 评阅意见：评阅意见： 成绩评定：成绩评定： 评阅人：评阅人： 日期：日期： 1 目目 录录 目录 一、一、 前言前言 二、二、 系统功能分析系统功能分析 2.1 汉诺威塔问题汉诺威塔问题 2.2 解析汉诺威塔问题解析汉诺威塔问题 三、三、 总体设计总体设计 四、四、 详细设计详细设计 五、五、 系统实现系统实现 六、六、 结论结论 结束语结束语 2 参考文献参考文献 附录附录 一、一、前言前言 汉诺威塔是一款集娱乐与运算的智力游戏，它不仅能使人在休闲的时 候放松心情，而且还能在玩的过程中不断的提高你的思维能力。 本设计着手于怎么运算出 n 层汉诺威塔的解决方案，然而经过不断的 调试以及自己的在做的过程中也不断的去尝试着怎么自己能过汉诺威塔多 少层，经过几个星期的努力，以及不断的调试，我发现我能把 7 层的汉诺 威塔玩过已经是很不错了。如想玩下去的，只要你能记得那些步骤，那么 这汉诺威塔也不是什么难的了。 本设计如有差错，望各位谅解，在此我诚恳的希望大家能提出意见， 以便我能及时修改。 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神 勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着 64 个圆的金片， 最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地 把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为 帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己 运行计算，程序见尾部。面对庞大的数字(移动圆片的次数) 18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的 移动。 后来，这个传说就演变为汉诺塔游戏。 二、二、系统功能分析系统功能分析 科技奖励工作是推动科学技术进步的一项重要的激励机制，对促进国家 和地方社会经济发展，调动广大科研工作者的积极性具有重大作用。实践证明， 3 网络技术的运用有利于更快地促进科技成果的利用，从而有利于发展科技生产 力，繁荣国家和地方社会经济生活。 本设计可以实现从 2 到 n 层的汉诺威塔以供玩家思考和了解其运行过程。本设计通过 一系列的实践证明了前九层汉诺威塔的准确性，根据本人推论，以后的每一层的准度应该 与事实相符，鉴于工作量实在太大，故而敬请各为原谅！ 2.1 汉诺威塔问题 n 阶汉诺威塔问题： 有三根杆子 A,B,C。A 杆上有 n 个碟子 每次移动一块碟子,小的只能叠在大的上面 把所有碟子从 A 杆全部移到 C 杆上 经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片： 如 3 阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC 2.2解析汉诺威塔问题解析汉诺威塔问题 下面用归纳法证明 n 阶汉诺威塔问题，可以用 n 层二叉树描述，而且它的 解就是该二叉树的中序遍历序列。 用一个四元组(n,A,B,C)表示把 n 个盘子从 A 搬到 C,中间可以借助 B 的 n 阶汉诺威塔问题。其中 A、B、C 的地位是相对的，第一个表示起始位置，最 后一个表示终止位置，中间表示过渡位置。例如(n,A,B,C)表示把 n 个盘子从 B 搬到 C，中间可以借助 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，过渡位置和终止位置交换，与右孩子的关系是， 盘子个数减 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）汉诺威塔问题状态图 4 图（b）n 阶和 3 阶汉诺威塔问题状态图 5 三、三、 总体设计总体设计 首先建立一个程序。 然后创建类 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 汉诺威塔游戏结束界面 6 四、四、 详细设计详细设计 汉诺威塔程序代码： #include “iostream“ #include “string“ using namespace std; class Hanoi /定义类 Hanoi public : /共有成员 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 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) couta; cout“塔层数从上至下编号为 1、2、3、4、5、6,“endl; hanoi hanoi(a); hanoi.Solve(); goto loop; return 0; 五、五、 系统实现系统实现 程序运行如下： 图 5.1 程序运行界面 汉诺威塔 第五章 系统实现 8 图 5.2 4 层汉诺威塔运行界面 9 六、结论 通过这次课程设计，让我对数据结构有了新一层的了解，让我明白各种 函数以及类的应用，明白了算法对程序的重要性。由于本次程序是解决一个游 戏的过关问题，所以必须亲自玩那个游戏，从而推出程序的重要性。这玩游戏 的过程让我感觉到汉诺威塔的趣味性，这是一个集智益与娱乐于一体的游戏， 很值得一玩。 本程序运行 13 层以下速度很快，13 层以上则要等一段时间了。 图 7.1 结结 束束 语语 本次课程设计，使我对从汉诺威塔设计方案到设计的基本过程的设计方法、 步骤、思路、有一定的了解与认识。在课程设计过程中，我基本能按照规定的 程序进行，先针对汉诺威塔设计收集、调查有关资料，其间，与同学之间对递 归的算法讨论、修改，再讨论、再修改，最后定案。最终用c+语言实现了可 视化的汉诺威塔算法。 程序设计达到了专业学习的预期目的。课程设计之后，我普遍感到不仅实 际动手能力有所提高，更重要的是进一步激发了我对专业知识的兴趣，并能够 结合实际存在的问题在专业领域内进行更深入的学习。 对我们计算机专业的本科生来说，实际能力的培养至关重要，而这种实际 10 能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。通过课程设计， 让我找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识， 为求职与正式工作做好充分