汉诺塔论文

1目录目录..............................................................1摘要.............................................................2一、背景知识.......................................................3二、问题重述.......................................................3三、算法分析.......................................................3四、流程及程序设计.................................................5(1)、流程图.......................................................5(2)、模块及其功能介绍.............................................6五、调试与算法复杂度分析...........................................7(1)、运行结果.....................................................7(2)、HANOI塔问题复杂度分析........................................9总结...........................................................10参考文献..........................................................11附录............................................................122摘要汉诺威塔是一款集娱乐与运算的智力游戏，它不仅能使人在休闲的时候放松心情，而且还能在玩的过程中不断的提高你的思维能力。有三个柱子A,B,C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1,2,...,n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上本文的主要算法是利用函数的递归调用算法。首先，想办法将A座上的前n-1个盘借助C座移动到B座上，然后将A组上的第n个盘移动到C座上。然后再将B座上的n-1个盘借助A座移动到C座上，此次移动也和第一次移动一样，重复递归，直到最后一个盘为止。关键词：汉诺塔递归思想函数调用数组指针3一、背景知识汉诺塔（又称河内塔）问题来自中东地区一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。19世纪的法国大数学家鲁卡曾经研究过这个问题，他正确地指出，要完成这个任务，僧侣们搬动金盘的总次数（把1个金盘从某个塔柱转移到另1个塔柱叫做1次）为：18，446，744，073，709，551，615次。假设僧侣们个个身强力壮，每天24小时不知疲倦地不停工作，而且动作敏捷快速，1秒钟就能移动1个金盘，那么，完成这个任务也得花5800亿年！二、问题重述有三个柱子A,B,C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1,2,...,n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。用计算机算法思想解决该问题，利用C++实现其动态演示。三、算法分析设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上；4③第二次调用递归重复以上过程，直到将全部的盘子移动到位时为止。由递归算法我们可以得到递推关系：M(n)=2M(n-1)+1当n1时M(n)=1当n=1时5四、流程及程序设计(1)、流程图有上述流程图得出实现递归函数过程的流程图设计如下图所示：开始定义结构体数组M存放盘号和塔座高度程序初始化输入要演示的盘块数nn1||n10n=10绘制塔座和盘块调用递归函数hanoi()n==1?调用move()函数将盘块从A移到C将前n-1个盘块从A移到B再将A的第n个盘块移到C最后将B上的n-1个盘移到C结束6(2)、模块及其功能介绍首先定义两个类:Tower类（栈）Hanoi类（包含三个Tower类对象组成），程序中大部份功能函数封装在这两个类中（包括：递归算法Hanoi::Move()、图形显示函数Hanoi::Outlin()、移动演示函数Hanoi::MoveShow()等）塔的盘子是字符串由（'=',''）组成的另外还有一些函数：Push函数的功能是放入盘子，pop函数的功能是取出盘子重要函数的分析：voidMove(intn,intA,intB,intC)递归（这里的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塔}}开始n==1?将盘块从A座移到C座将前n-1个盘块从A座移到B座再将A座的第n个盘块移到C座最后将B座上的n-1个盘块移到C座结束7五、调试与算法复杂度分析(1)、运行结果(以4层Hanoi塔为类)运行程序得到如下界面：程序主界面游戏的初始状态当完成第一步时，A上第一个盘就移动到B上这时按任意键继续。如下：8第一步结束时状态第二步结束时状态︰︰︰9第十五步结束的状态最后就完成了将A上所有的盘子移动到C盘上。(2)、Hanoi塔问题复杂度分析①时间复杂度程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves（n），用迭代方法计算公式，得到结果moves(n)=2n-1。因此，hanoi函数的时间复杂度为O(2n)。②空间复杂度从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间。如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是n，而塔3的容量是n－1，因此所需要的空间总数为3n－1。Hanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范围内，只能解决n值比较小（n=30）的hanoi问题。对于这个较小的n值，堆栈在空间需求上的差别相当小，可以随意使用。10总结计算机算法设计与分析和现代计算机技术的实际应用相结合，是我在本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的美观的运行结果界面以及另人兴奋的可用程序，都是一个很好的学习和锻炼的过程。使我们巩固了原有的理论知识，培养了我灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力。使我体会到自身知识和能力能在实际中的应用和发挥。通过学习我丰富了计算机操作经验，更增强了对C++语言的使用技巧。汉诺塔是个不错的数学游戏，由于问题的有趣，所以能很好地提高参与者地热情与兴趣。现在汉诺塔也被运用于很多智力游戏中，我们在玩手机游戏的时候，也会锻炼一下自己的脑力。汉诺塔也很好的体现了数学的递归思想。设计汉诺塔程序，充分了解汉诺塔问题的本质以及怎样移动盘子。认真看课本的方法，还能对平时上课的内容得到巩固和熟练。11参考文献1严蔚敏.数据结构（C语言版）.清华大学出版社.20072吴乃陵.,况迎辉.C++程序设计（第2版）.高等教育出版社.20073王晓东.计算机算法设计与分析（第三版）.电子工业出版社.200712附录#includeiostream#includestringusingnamespacestd;#includestdlib.h#defineMAX10000structStack{stringdata;Stack*next;};classTower{intfloor;intbroad;public:Stack*top;intTop;Tower(intstore){floor=store;if(floor6)broad=4+2*floor;elsebroad=2+2*floor;Top=0;stringbro;for(inti=0;ibroad/2;i++)bro=bro+[];Stack*temp=newStack;temp-data=bro;temp-next=top;top=temp;}13stringOutFloor(inti){Stack*toptemp=top;for(intj=0;jTop-i;j++)toptemp=toptemp-next;returntoptemp-data;}voidpush(stringdisc){Stack*temp=newStack;temp-data=disc;temp-next=top;top=temp;Top++;}stringpop(){Stack*temp;stringx;if(top==NULL)returnNULL;else{x=top-data;temp=top;top=top-next;free(temp);Top--;returnx;}}stringdisc(intspace){stringdis;for(inti=0;ispace;i++)14dis=dis+'';for(intj=space;ibroad-space;i++)dis=dis+'=';for(intk=broad-space;kbroad;k++)dis=dis+'';returndis;}};classHanoi{intStore;intbroad;Tower*A;Tower*B;Tower*C;intstep;intSTEP[MAX];voidmove(intA,intC){step++;STEP[step]=A*10+C;}voidMove(intn,intA,intB,intC){if(n==1)move(A,C);else{Move(n-1,A,C,B);move(A,C);15Move(n-1,B,A,C);}}public:Hanoi(intstore){Store=store;if(Store6)broad=4+2*Store;elsebroad=2+2*Store;A=newTower(store);for(inti=1;i=Store;i++)A-push(A-disc(i));B=newTower(store);C=newTower(store);step=0;Move(Store,1,2,3);}voidOutStep(){intStepTemp;cou