《课程设计汉诺威塔》由会员分享，可在线阅读，更多相关《课程设计汉诺威塔（35页珍藏版）》请在金锄头文库上搜索。
1、摘要：摘要：汉诺塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着 64 个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。传说固然只是传说，这个古老的故事到今天又引申出一连串的包括统筹、管理等等数学问题。在现实生活中，任何一个人都不可能直接写出移动盘子的每一个具体步骤。比较经典的使用递归算法也是在这方面做了大量
2、研究得出的一种相对优化的算法方案。本文主要从图形学的角度对这个问题作了一些简单的探讨。整个程序采用了自顶向下，逐步细化的设计方法。主要分为三个模块：图形环境初始化、问题求解、以及过程动画演示。程序能够处理用户输入的不同初始值使需要搬动的盘子数初始化。初始化图形采用点阵方式直接写屏。关键词 汉诺塔，递归思想 函数调用，演示1 / 36目录目录背景知识.31 设计目的和要求.41.1 设计要求.41.2 设计要求.42 系统设计.52.1 汉诺威塔问题.52.2 设计思路.52.3 算法分析.63 流程及程序设计.103.1 流程图.103.2 模块及功能.114 详细设计.135 系统实现.30
3、5 系统实现.306 小结.347 参考文献.352 / 36背景知识：背景知识：汉诺塔（又称河内塔）问题来自中东地区一个古老的传说：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着 64 个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。19 世纪的
4、法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把 1 个金盘从某个塔柱转移到另 1 个塔柱叫做 1 次）为：18，446，744，073，709，551，615 次。假设僧侣们个个身强力壮，每天 24 小时不知疲倦地不停工作，而且动作敏捷快速，1 秒钟就能移动 1 个金盘，那么，完成这个任务也得花 5800 亿年！3 / 361 1 设计目的和要求设计目的和要求1.11.1 设计目的设计目的随着计算机技术以及外围设备的发展，计算机在辅助设计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。如何运用计算机技术、运用算法编程来优化解决低阶汉
5、诺威塔问题对我们学生来说具有可实现和可操作性。本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解决、实现低阶汉诺威塔问题。1.21.2 设计要求设计要求1.2.11.2.1 功能要求功能要求 能够实现按用户需要对输入的不同盘子数量进行处理。 能够实现根据输入条件，给出完整的解决方案。 能够实现每一个搬运步骤的演示。1.2.21.2.2 环境要求环境要求 能够在 windows 操作系统下正常运行。有友好的界面用户能接受的简单的操作。4 / 36ABC图 2.1 汉诺塔2.2.系统设计系统设计2.12.1 汉诺威塔问题汉诺威塔问题n阶汉诺威塔问题：有三个柱子A, B, C。A柱子上叠
6、放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上如 3 阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC2.22.2 设计思路设计思路对于一个类似的这样的问题，任何一个人都不可能直接写出移动 盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我 们假设把该任务交给一个僧人，为了方便叙述，将他编号为 64。僧 人自然会这样想：假如有另外一个僧人能有办法将 63 个盘子从一个座移到另一个座，那么问
7、题就解决了，此时僧人 64 只需这样做： 1. 命令僧人 63 将 63 个盘子从 A 座移到 C 座5 / 362. 自己将最底下的最大的一个盘子从 A 座移到 C 座 3. 再命令僧人 63 将 63 个盘子从 B 座移到 C 座 为了解决将 63 个盘子从 A 座移到 B 座的问题，僧人 63 又想： 如果能再有一个僧人 62 能将 62 个盘子移动到另一座，我就能将 63 个盘子从 A 座移动到 B 座。他是这样做的： 1. 命令僧人 62 将 62 个盘子从 A 移动到 C 2. 自己将一个盘子从 A 座移动到 B 座 3. 再命令僧人 62 将 62 个盘子移到 B 座 再进行一次
8、递归。如此“层层下放” ，直到后来找到第 2 个僧人， 让他完成将 2 个盘子从一个座移到另一个座，进行到此，问题就解 决了。最后找到第 1 个僧人，让他完成将一个盘子从一个座移动到 另一个座，至此，全部工作已经完成，都是可以执行的。 按照如此的思路设计递归算法，很容易得出盘子的移动方案。 2.32.3 算法分析算法分析设 A 上有 n 个盘子。 当 n=1 时，则将圆盘从 A 直接移动到 C。 当 n 大于等于 2 时，移动的过程可分解为三个步骤： 第一步 把 A 上的 n-i 个圆盘移到 B 上； 第二步 把 A 上的一个圆盘移到 C 上； 第三步 把 B 上的 n-i 个圆盘移到 C 上
9、；其中第一步和第三步是类同的。 为了更清楚地描述算法，用图示法描述如下：将 N 个盘子从 A 杆上借助 C 杆移动到 B 杆上。这样移动 N 个盘子的工作就可以按照以下过程进行：第一次调用递归 6 / 36将一个盘子从 A 移动到 B 上；第二次调用递归重复以上过程，直到将全部的盘子移动到位时为止。由递归算法我们可以得到递推关系：M(n)=2M(n-1)+1 当 n1 时M(n)=1 当 n=1 时下面用归纳法证明 n 阶汉诺威塔问题，可以用 n 层二叉树描述，而且它的解就是该二叉树的中序遍历序列。用一个四元组(n,A,B,C)表示把 n 个盘子从 A 搬到 C,中间可以借助 B 的 n 阶汉
10、诺威塔问题。其中 A、B、C 的地位是相对的，第一个表示起始位置，最后一个表示终止位置，中间表示过渡位置。例如(n,A,B,C)表示把 n 个盘子从 B 搬到 C，中间可以借助 A 的 n 阶汉7 / 36诺威塔问题。用一个三元组(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
