【精品】汉诺塔论文

《【精品】汉诺塔论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1摘要2一、背景知识3二、问题重述3三、算法分析3四、流程及程序设计5⑴、流程图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、子2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上本文的主要算法是利用函数的递归调用算法。首先，想办法将A座上的前n-1个盘借助C座移动到B座上，然后将A组上的第n个盘移动到C座上。然后再将B座上的n-1个盘借助A座移动到C座上，此次移动也和第一次移动一样，重复递归，直到最后一个盘为止。关键词：汉诺塔递归思想函数调用数组指针一、背景知识汉诺塔（又称河内塔）问题來自中东地区一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A）,其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B

3、和塔C）。从世界创始之口起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。19世纪的法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1个塔柱叫做1次）为:18,446,744,073,709,551,615次。假设僧侣们个个身强力壮，每天24小时不知疲倦地不停工作，而且动作敏捷快速，1秒钟就能移动1个金盘，那么，完成这个任务也得花5

4、800亿年！二、问题重述有三个柱子A,B,CoA柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用l,2,...,n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘了不能放在小盘了上，只能小盘了放在大盘了上。用计算机算法思想解决该问题，利用C++实现其动态演示。三、算法分析设A上有n个盘子。当n=l时，则将圆盘从A直接移动到C。当n大于等于2时，移动的过程可分解为三个步骤：第一步把A上的n-i个圆盘移到B上；第二步把A上的一个圆盘移到C上；第三步把B上

5、的n・i个圆盘移到C±；其屮第一步和第三步是类同的。为了更清楚地描述算法，用图示法描述如下：将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的丁作就可以按照以下过程进行：①第一次调用递归n12…NLJ1N-1BC①将一个盘子从A移动到B上;②第二次调用递归r—2I

6、….N-1N「11BC重复以上过程，直到将全部的盘子移动到位时为止。由递归算法我们可以得到递推关系：rM(n)=2M(n-l)+l当n>l时[M(n)=l当n=l时四、流程及程序设计⑴、流程图有上述流程图得岀实现递归函数过程的流程图设计如下图所示:(2)、模块及其功能

7、介绍首先定义两个类：Tower类(栈)Hanoi类(包含三个Tower类对象组成)，程序中大部份功能函数封装在这两个类中(包括：递归算法Hanoi::Move()>图形显示函数Hanoi::0utlin()>移动演示函数Hanoi::MoveShow()等)塔的盘子是字符串由(’二’)组成的另外述有一些函数：Push函数的功能是放入盘子，pop函数的功能是取出盘子重要函数的分析：voidMove(intn,intA,intB,intC)递归(这里的A,B,C是相对的,不等同外面定义的A塔，B塔，C塔){if(n==l)//递归的终止条件

8、{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塔}五.调试与算法复杂度分析⑴、运行结果（以4层Hanoi塔为类）运行程序得到如下界面：程序主界面汁♦建立汉诺塔2.算法思想3.结東

9、程序请嗚只忘禹扭和<1，2,3>,1请输入层数<1-10>:4(](][](][](][][][](](][][](](](][](]游戏的初始状态当完成第一步时，A上第-•个盘就移动到B上这时按任意键继续