汉诺塔实验报告

实验报告课程名称__________数据结构___________实验名称___________汉诺塔_______________实验类型一验证性实验_______________________实验地点计机房实验日期304指导教师_____________魏海平___________专业计算机科学与技术班级计算机1002______________学号20_____________姓名________张森___________辽宁石油化工大学计算机与通信工程学院数据结构实验报告评分表项目要求分数有无项目（）得分J实验目的明确5实验内容理解透彻5预习报告实验方案程序总体框架设计完整10（30分）设计完整完成相关辅助代码5合理测试方案合理5发现问题5实验过程问题的分析15（30分）问题的解决方法10内容翔实无缺漏5实验报告如实记录实验过程10（20分）撰写规整5实验总结实验结果的分析5（10分）按照结果对原实验方案的改进意见5实验体会实验的收获5（10分）实验内容的发散考虑5总分.实验目的1通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性.问题描述2汉诺塔问题来自一个古老的传说在世界刚被创建的时候有一座钻石宝塔塔其上有个金碟所A,64有碟子按从大到小的次序从塔底堆放至塔顶紧挨着这座塔有另外两个钻石宝塔塔和塔从世界创始B C之日起，婆罗门的牧师们就一直在试图把塔上的碟子移动到塔上去，其间借助于塔的帮助每次只能A C B移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面当牧师们完成任务时，世界末日也就到了.算法设计思想3对于汉诺塔问题的求解，可以通过以下三个步骤实现将塔上的个碟子借助塔先移到塔上1A n-1CB把塔上剩下的一个碟子移到塔上2A C将个碟子从塔借助于塔移到塔上3n-1B AC.实验步骤4用或语言设计实现汉诺塔游戏；

1.C++c让盘子数从开始到进行实验，记录程序运行时间和递归调用次数；

2.27画出盘子数和运行时间、递归调用次数的关系图，并进行分析

3.n tm实验内容及实验结果请写出具体的实验步骤，并给出相应的实验结果，附上编写的程序及其运行结果截图!!#includestdio.hvoid haniointn,char A,char B,char Cif n==l printfnMovedisk from%c to%c\n”,A,B;else{；hanion-l,A,C,BprintfnMove diskfrom%c to%c\nH,A,B；；hanion-l,C,B,A voidmainint n;printfninput thenumber ofdisk:1;scanfH%dH,n;printfthe stepsfor%d diskare:\n*\n;；；；hanion AB C;运行结果程］*D:\ly DocuMents\Iy QQFiles3rnoue1fron Ato Bnoue2fron Ato Ciioue1fron Bto Cnoue3fron Ato Bnoue1fron Cto Anoue2from Cto Bnoue1fron Ato Bcount=7countl=

4、结论7通过对上述递归在塔问题上的应用分析，我们可以得出如下结论:Hanoi、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序1在这种情况下，程序的地址空间可能动态变化；、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈2但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间因此，可以考虑采用并行计算进行处理，但、递归是串行的，其第步运算依赖于第步运算，所以在计算机软件理论上不存在递归问题并行计算的3n n-l缓存大小可能性实际上是否存在并行递归计算有待进一步探讨入总结通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开发。