课程设计汉诺威塔

《课程设计汉诺威塔》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、摘要：汉诺塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。传说固然只是传说，这个古老的故事到今天又引申出一连串的包括统筹、管理等等数学问题。在现实生活中，任何一个人都不可能直接写出移动盘子

2、的每一个具体步骤。比较经典的使用递归算法也是在这方面做了大量研究得出的一种相对优化的算法方案。本文主要从图形学的角度对这个问题作了一些简单的探讨。整个程序采用了自顶向下，逐步细化的设计方法。主要分为三个模块：图形环境初始化、问题求解、以及过程动画演示。程序能够处理用户输入的不同初始值使需要搬动的盘子数初始化。初始化图形采用点阵方式直接写屏。关键词汉诺塔，递归思想函数调用，演示34/35目录背景知识31设计目的和要求41.1设计要求41.2设计要求42系统设计52.1汉诺威塔问题52.2设计思路52.3算法分析63流程及程序设

3、计103.1流程图103.2模块及功能114详细设计135系统实现305系统实现306小结347参考文献3534/35背景知识：汉诺塔（又称河内塔）问题来自中东地区一个古老的传说：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)184467440737

4、09551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。19世纪的法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1个塔柱叫做1次）为：18，446，744，073，709，551，615次。假设僧侣们个个身强力壮，每天24小时不知疲倦地不停工作，而且动作敏捷快速，1秒钟就能移动1个金盘，那么，完成这个任务也得花5800亿年！34/351设计目的和要求1.1设计目的随着计算机技术以及外围设备的发展，计算机在辅助设

5、计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。如何运用计算机技术、运用算法编程来优化解决低阶汉诺威塔问题对我们学生来说具有可实现和可操作性。本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解决、实现低阶汉诺威塔问题。1.2设计要求1.2.1功能要求①能够实现按用户需要对输入的不同盘子数量进行处理。②能够实现根据输入条件，给出完整的解决方案。③能够实现每一个搬运步骤的演示。1.2.2环境要求①能够在windows操作系统下正常运行。②有友好的界面③用户能接受的简单的操作。34/352.系统设计2

6、.1汉诺威塔问题n阶汉诺威塔问题：有三个柱子A,B,C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1,2,...,n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C2.2设计思路ABC图2.1汉诺塔对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设

7、把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1.命令僧人63将63个盘子从A座移到C座34/351.自己将最底下的最大的一个盘子从A座移到C座2.再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1.命令僧人62将62个盘子从A移动到C2.自己将一个盘子从

8、A座移动到B座3.再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。按照如此的思路