汉诺塔论文.docVIP

目 录 目 录 1 摘 要 2 一、背景知识 3 二、问题重述 3 三、算法分析 3 四、流程及程序设计 5 (1)、流程图 5 (2)、模块及其功能介绍 6 五、调试与算法复杂度分析 7 (1)、运行结果 7 (2)、Hanoi塔问题复杂度分析 9 总 结 10 参考文献 11 附 录 12 摘 要 汉诺威塔是一款集娱乐与运算的智力游戏，它不仅能使人在休闲的时候放松心情，而且还能在玩的过程中不断的提高你的思维能力。 有三个柱子A, B, C A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上关键词：汉诺塔递归思想函数调用数组指针汉诺塔问题来自中东地区一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。19世纪的法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1个塔柱叫做1次）为：18，446，744，073，709，551，615次假设僧侣们个个身强力壮，每天24小时不知疲倦地不停工作，而且动作敏捷快速，1秒钟就能移动1个金盘，那么，完成这个任务也得花5800亿年！ 有三个柱子A, B, CA柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子； 2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。设A上有n个盘子。 n=1时，则将圆盘从A直接移动到C。 当n大于等于2时，移动的过程可分解为三个步骤： 第一步 把A上的n-个圆盘移到B上； 第二步 把A上的一个圆盘移到C上； 第三步 把B上的n-个圆盘移到C上；其中第一步和第三步是类同的。 为了更清楚地描述算法将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行： 第一次调用递归 ②将一个盘子从A移动到B上； ③第二次调用递归 重复以上过程，直到将全部的盘子移动到位时为止。 有上述流程图得出实现递归函数过程的流程图设计如下图所示： (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塔 } else{ Move(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塔 } } 五、调试与算法复杂度分析 (1)、运行结果(以4层Hanoi塔为类) 运行程序得到如下界面： 程序主界面 游戏的初始状态 当完成第一步时，A上第一个盘就移动到B上这时按任意键继续。如下： 第一步结束时状态 第二步结束时状态 ︰ ︰ ︰ 第十五步结束的状态 最后就完成了将A上所有的盘子移动到C盘上。 (2)、Hanoi塔问题复杂度分析 ①时间复杂度 程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves（n）用迭代方法计算公式，得到结果moves(n)=2n-1。因此，hanoi函数的时间复杂度为O(2 n) 。 ② 空间复杂度 从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n