Hanoi塔问题实验报告

上传人:文*** 文档编号:161910897 上传时间:2022-10-16 格式:DOC 页数:3 大小:60KB
收藏 版权申诉 举报 下载
Hanoi塔问题实验报告_第1页
第1页 / 共3页
Hanoi塔问题实验报告_第2页
第2页 / 共3页
Hanoi塔问题实验报告_第3页
第3页 / 共3页
资源描述:

《Hanoi塔问题实验报告》由会员分享,可在线阅读,更多相关《Hanoi塔问题实验报告(3页珍藏版)》请在装配图网上搜索。

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

2、塔座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移动到塔座C。第3步可以分解为:3.1 将塔座C上1个圆盘从塔座Y移动到塔座B;3.2 将塔座C上1个圆盘从塔座Y移动到塔座A;3.3 将塔座B上1个圆盘从塔座X移动到塔座A。综上所述:可得到移动3个圆盘的步骤为B-A,B-C, A-C, B-A, C-B, C-A, B-A,2、算法设计:

3、将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(a,c); times +; else hno(n-1,a,c,b); m

4、ove(a,c); times +; hno(n-1,b,a,c); void main()unsigned start,finish; int N; printf(请输入汉诺塔的层数:); scanf(%d,&N); start=GetTickCount();/ hno(N,B,C,A); finish=GetTickCount(); float time=(finish-start)/1000.0; printf(共移动了%d次! n,times); cout总共需要时间为: timeendl;四:五结论分析通过对上述递归在 Hanoi 塔问题上的应用分析,可以得出如下结论: 递归应用中的

5、Hanoi塔问题分析递归应用中的1、Hanoi 塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时,在运行被调用函数之前,系统先完成3件事:将所有的实参、返回地址等信息传递给被调用函数保存。 为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。从被调用函数返回调用函数前,系统也应完成3件事:保存被调用函数的结果;释放被调用函数的数据区;依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时,按照“后调用先返回”的原则,上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为其

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

展开阅读全文
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!