汉诺塔程序实验报告

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

2、塔座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移动到塔座ao综上所述：可得到移动3个圆盘的步骤为b->a, b->c, a-

3、>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<stdio.h>#include <iostream.h>#include <windows.h>int times = 0;void move(char a, char b)printf(&quo

4、t;%c -> %c n", a,b);void hno(int n,char a , char b, char c)if (n=l)move(a,c);times +;elsehno(n-l,a,c,b);move(a,c);times +;hno(n-lbac);void main()unsigned start,finish;int n;printf("请输入汉诺塔的层数:"); scanf(h%d",&n);start=gettickcount();/hnojn/bvc'/a*)；finish=gettickcount();

5、float time=(finish-start)/1000.0;printf("共移动了%d 次！ n",times);coutvv”总共需要时间为:"«time«endl;四：4c a a c b cabbab b c bb b c c a c若 又-冃 吉->->事鹫舉腐霜务 0-016ress itny key to cont; inue五.结论分析通过对上述递归在hanoi塔问题上的应用分析，可以得出如下结论： 递归应用中的hanoi塔问题分析递归应用中的1、hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用另一

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