黑夜给了我黑色的眼睛,我却用它寻找光明精编版

汉诺塔实验报告实验报告课程名称数据结构实验名称汉诺塔实验类型验证性实验实验地点计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.实验步骤：1.用c++或c语言设计实现汉诺塔游戏；2.让盘子数从2开始到7进行实验，记录程序运行时间和递归调用次数；3.画出盘子数n和运行时间t、递归调用次数m的关系图，并进行分析。实验内容及实验结果请写出具体的实验步骤，并给出相应的实验结果，附上编写的程序及其运行结果截图!!#includevoidhanio(intn,charA,charB,charC){if(n==1)printf("Movediskfrom%cto%c\n",A,B);else{hanio(n-1,A,C,B);printf("Movediskfrom%cto%c\n",A,B);hanio(n-1,C,B,A);}}voidmain(){intn;printf("inputthenumberofdisk:");scanf("%d",&n);printf("thestepsfor%ddiskare:\n",n);hanio(n,'A','B','C');}运行结果：7、结论通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论：1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但缓存大小3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。8、总结通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开发。