摘要：汉诺塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。传说固然只是传说，这个古老的故事到今天又引申出一连串的包括统筹、管理等等数学问题。在现实生活中，任何一个人都不可能直接写出移动盘子的每一个具体步骤。比较经典的使用递归算法也是在这方面做了大量研究得出的一种相对优化的算法方案。本文主要从图形学的角度对这个问题作了一些简单的探讨。整个程序采用了自顶向下，逐步细化的设计方法。主要分为三个模块：图形环境初始化、问题求解、以及过程动画演示。程序能够处理用户输入的不同初始值使需要搬动的盘子数初始化。初始化图形采用点阵方式直接写屏。关键词 汉诺塔，递归思想 函数调用，演示目录背景知识31设计目的和要求4 1.1设计要求4 1.2设计要求42 系统设计5 2.1汉诺威塔问题5 2.2设计思路5 2.3算法分析63 流程及程序设计10 3.1流程图10 3.2模块及功能114 详细设计135 系统实现305 系统实现306 小结347 参考文献35背景知识：汉诺塔（又称河内塔）问题来自中东地区一个古老的传说：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。19世纪的法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1个塔柱叫做1次）为：18，446，744，073，709，551，615次。假设僧侣们个个身强力壮，每天24小时不知疲倦地不停工作，而且动作敏捷快速，1秒钟就能移动1个金盘，那么，完成这个任务也得花5800亿年！1 设计目的和要求1.1设计目的随着计算机技术以及外围设备的发展，计算机在辅助设计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。如何运用计算机技术、运用算法编程来优化解决低阶汉诺威塔问题对我们学生来说具有可实现和可操作性。本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解决、实现低阶汉诺威塔问题。1.2设计要求1.2.1功能要求 能够实现按用户需要对输入的不同盘子数量进行处理。 能够实现根据输入条件，给出完整的解决方案。 能够实现每一个搬运步骤的演示。1.2.2环境要求 能够在windows操作系统下正常运行。有友好的界面用户能接受的简单的操作。2.系统设计2.1汉诺威塔问题n阶汉诺威塔问题：有三个柱子A, B, C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上如3阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC2.2设计思路ABC图2.1 汉诺塔对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1. 命令僧人63将63个盘子从A座移到C座2. 自己将最底下的最大的一个盘子从A座移到C座3. 再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1. 命令僧人62将62个盘子从A移动到C2. 自己将一个盘子从A座移动到B座3. 再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。按照如此的思路设计递归算法，很容易得出盘子的移动方案。2.3算法分析设A上有n个盘子。 当n=1时，则将圆盘从A直接移动到C。 当n大于等于2时，移动的过程可分解为三个步骤： 第一步 把A上的n-i个圆盘移到B上； 第二步 把A上的一个圆盘移到C上； 第三步 把B上的n-i个圆盘移到C上；其中第一步和第三步是类同的。 为了更清楚地描述算法，用图示法描述如下：将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行：第一次调用递归 将一个盘子从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阶汉诺威塔问题。其中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阶汉诺威塔问题，结论也成立。到此证明完毕。（图1） 2阶汉诺威塔问题状态树（图2） n阶和3阶汉诺威塔问题状态树3.流程及程序设计3.1流程图：（如下图所示）开始定义结构体数组M存放盘号和塔座高度程序初始化输入要演示的盘块数nn10n=10绘制塔座和盘块调用递归函数hanoi( )n= =1?调用move( )函数将盘块从A移到C将前n-1个盘块从A移到B再将A的第n个盘块移到C最后将B上的n-1个盘移到C结 束有上述流程图得出实现递归函数过程的流程图设计如下图所示：开 始n= =1?将盘块从A座移到C座将前n-1个盘块从A座移到B座再将A座的第n个盘块移到C座最后将B座上的n-1个盘块移到C座结 束3.2模块及其功能介绍首先定义两个类: Tower类（栈）Hanoi类（包含三个Tower类对象组成），程序中大部份功能函数封装在这两个类中（包括：递归算法Hanoi:Move()、图形显示函数Hanoi:Outlin()、移动演示函数Hanoi:MoveShow() 等 ）塔的盘子是字符串由（=, ）组成的另外还有一些函数：Push函数的功能是放入盘子， pop函数的功能是取出盘子重要函数的分析：void Move(int n,int A,int B,int C)递归 （这里的A，B，C是相对的，不等同外面定义的A塔，B塔，C塔）if(n=1)/递归的终止条件move(A,C);/将A塔上的最后一个盘子盘子直接移动到C塔 elseMove(n-1,A,C,B);/将A塔上的n-1个盘子通过C塔移动到B塔 move(A,C);/将A塔上的最后一个盘子盘子直接移动到C塔 Move(n-1,B,A,C);/将B塔上的n-1个盘子通过A塔移动到C塔4.系统详细设计：#include#includeusing namespace std;#include #define MAX 10000struct Stackstring data;Stack *next;class Tower int floor; int broad;public:Stack *top; int Top; Tower(int store) floor=store; if(floor6)broad=4+2*floor;else broad=2+2*floor;Top=0;string bro; for(int i=0;idata=bro;temp-next=top;top=temp; string OutFloor(int i)Stack *toptemp=top;for(int j=0;jnext;return toptemp-data; void push(string disc) Stack *temp=new Stack; temp-data=disc;temp-next=top;top=temp;