汉诺塔程序实验报告

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

2、有3个圆盘移动到塔座 A上：(1) 将塔座B上2个圆盘借助塔座 A移动到塔座C上;(2) 将塔座B上1个圆盘移动到塔座 A上;(3) 将塔座C上2个圆盘借助塔座 B移动到塔座A上。X 移动到塔座 A；X 移动到塔座 C； Z 移动到塔座 C。Y移动到塔座Y移动到塔座X移动到塔座B；A；A。其中第 2步可以直接实现。第 1步又可用递归方法分解为：1.1将塔座B上1个圆盘从塔座1.2将塔座B上1个圆盘从塔座1.3将塔座A上1个圆盘从塔座第 3 步可以分解为：3.1将塔座C上1个圆盘从塔座3.2将塔座C上1个圆盘从塔座3.3将塔座B上1个圆盘从塔座综上所述：可得到移动 3 个圆盘的步骤为B-A,B-

3、C, A-C, B-A, C-B, C-A, B-A,2、算法设计：将n个圆盘由B依次移到A, C作为辅助塔座。当 n=1时，可以直接完成。否则，将塔 座B顶上的n-1个圆盘借助塔座 A移动到塔座C上；然后将圆盘B上第n个圆盘移到塔 座A上；最后将塔座 C上的n-1个圆盘移到塔座 A上，并用塔座B作为辅助塔座。三、原程序#include #include #include int times = 0;void move(char a, char b)printf(%c %c n, a,b);void hno(int n,char a , char b, char c) if (n=1)move

4、(a,c);times +;elsehn o( n-1,a,c,b);move(a,c);times +;hn o( n-1,b,a,c);void mai n()un sig ned start,fi ni sh;int N;printf(请输入汉诺塔的层数：);scan f(%d,&N);start=GetTickCou nt();hn o(N,B,C,A);fini sh=GetTickCou nt();float time=(fi ni sh-start)/1000.0;printf(共移动了 %d 次! n,times);cout总共需要时间为：timenyDeslrtophorne

5、work,.3LinI31D#bugCppl ewe*五结论分析 通过对上述递归在 Hanoi 塔问题上的应用分析，可以得出如下结论： 递归应用中的 Hanoi 塔问题分析递归应用中的1、Hanoi 塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在 运行被调用函数之前，系统先完成 3 件事： 将所有的实参、返回地址等信息传递给被调用函数保存。 为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。从被调用函数返回调用函数前，系统也应完成 3 件事： 保存被调用函数的结果； 释放被调用函数的数据区； 依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成

6、嵌套调用时，按照 “后调用先返回 ”的原则，上述函数之间的信息传递和控制转 移必须通过 “栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个 栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数 退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。2、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模 取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；3、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用 户自行管理递归工作栈。 但递归应用于计算机时需要占用大量系统资源 （包括堆栈、 软中断 和存贮空间等） ，并消耗大量处理时间。因此，