汉诺塔程序实验报告

《汉诺塔程序实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验题目：Hanoi塔问题一、问题描述：假设有三个分别命名为A,B和C的塔座，在塔座B上插有n个直径大小各不相同、从小到大编号为1,2,…，n的圆盘。现要求将塔座B上的n个圆盘移至塔座A上并仍按同样顺序叠排，圆盘移动时必须遵守以下规则：(1)每次只能移动一个圆盘；(2)圆盘可以插在A,B和C中任一塔上；(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。要求：用程序模拟上述问题解决办法，并输出移动的总次数，圆盘的个数从键盘输入；并想办法计算出程序运行的时间。二、算法思路：1、建立数学模型：这个问题可用递归法解决，并用数学归纳法又个别

2、得出普遍解法：假设塔座B上有3个圆盘移动到塔座A±：(1)〃将塔座B上2个圆盘借助塔座A移动到塔座C上；(2)〃将塔座B上1个圆盘移动到塔座A上；(3)〃将塔座C上2个圆盘借助塔座B移动到塔座A上。其屮笫2步可以直接实现。笫1步又可用递归方法分解为：1.1〃将塔座B上1个圆盘从塔座X移动到塔座A；1.2〃将塔座B上1个圆盘从塔座X移动到塔座C；1.3〃将塔座A上1个圆盘从塔座Z移动到塔座Co第3步可以分解为：3.1将塔座C上1个圆盘从塔座Y移动到塔座B；3.2将塔座C上1个圆盘从塔座Y移动到塔座A；3.3将塔座B上1个圆盘从塔座X移动到

3、塔座Ao综上所述：可得到移动3个圆盘的步骤为B->A,B->C,A->C,B->A,C->B,C->A,B->A,2、算法设计：将n个圆盘rflB依次移到A,C作为辅助塔座。当n二1时，可以直接完成。否则，将塔座B顶上的n-1个圆盘借助塔座A移动到塔座C上；然后将圆盘B上第n个圆盘移到塔座A上；最后将塔座C上的n-l个圆盘移到塔座A上，并用塔座B作为辅助塔座。三、原程序#include#include#includeinttimes=0;voidmove(chara,cha

4、rb){printf("%c---->%c",a,b);}voidhno(intn,chara,charb,charc)if(n==l)move(a,c);times++;}else{hno(n-l,a,c,b);move(a,c);times++;hno(n-l’bac);}}voidmain(){unsignedstart,finish;intN;printf("请输入汉诺塔的层数:");scanf(H%d",&N);start=GetTickCount();//hnoJN/BVC'/A*)；finish=GetTickCoun

5、t();floattime=(finish-start)/1000.0;printf("共移动了%d次！",times);coutvv”总共需要时间为:"«time«endl;}四：4cAAcBcAbbaBBcBBBccAc若又-冃吉->->事鹫舉腐霜务0-016^ressitnykeytocont;inue五.结论分析通过对上述递归在Hanoi塔问题上的应用分析，可以得出如下结论：递归应用中的Hanoi塔问题分析递归应用中的1、Hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完

6、成3件事：①将所有的实参、返回地址等信息传递给被调用函数保存。②为被调用函数的局部变量分配存储区；③将控制转移到被调用函数的入口。从被调用函数返冋调用函数前，系统也应完成3件事：①保存被调用函数的结果；②释放被调用函数的数据区；③依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用吋，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”來实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个幣数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函

7、数的数据区必在栈顶。2、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；3、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户口行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但4、递归是串行的，其第n步运算依赖于第步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。