汉诺塔实验报告.doc

实 验 报 告 课程名称 数据结构 实验名称 汉诺塔 实验类型 验证性实验 实验地点 计304机房 实验日期 指导教师 魏海平 专业 计算机科学与技术 班级 计算机1002 学号 20 姓名 张森 辽宁石油化工大学计算机与通信工程学院 数据结构实验报告评分表 项目 要求 分数 有无项目（√） 得分 预习报告 （30分） 实验目的明确 5 实验内容理解透彻 5 实验方案设计完整合理 程序总体框架设计完整 10 完成相关辅助代码 5 测试方案合理 5 实验过程 （30分） 发现问题 5 问题的分析 15 问题的解决方法 10 实验报告 （20分） 内容翔实无缺漏 5 如实记录实验过程 10 撰写规整 5 实验总结 （10分） 实验结果的分析 5 按照结果对原实验方案的改进意见 5 实验体会 （10分） 实验的收获 5 实验内容的发散考虑 5 总分 1.实验目的： 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。 2.问题描述： ?? 汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 3.算法设计思想： ????对于汉诺塔问题的求解，可以通过以下三个步骤实现：????(1)将塔A上的n-1个碟子借助塔C先移到塔B上。????(2)把塔A上剩下的一个碟子移到塔C上。????(3)将n-1个碟子从塔B借助于塔A移到塔C上。 4.实验步骤： 用c++ 或c语言设计实现汉诺塔游戏； 让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数； 画出盘子数n和运行时间t 、递归调用次数m的关系图，并进行分析。 实验内容及实验结果 请写出具体的实验步骤，并给出相应的实验结果，附上编写的程序及其运行结果截图!! #includestdio.h void hanio(int n,char A,char B,char C) { if (n==1) printf(Move disk from %c to %c\n,A,B); else{ hanio(n-1,A,C,B); printf(Move disk from %c to %c\n,A,B); hanio(n-1,C,B,A);} } void main() { int n; printf(input the number of disk:); scanf(%d,n); printf(the steps for %d disk are:\n,n); hanio(n,A,B,C); } 运行结果： 7、结论 通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论： 1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化； 2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但 缓存大小3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。 缓存大小 8、总结 通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开发。