汉诺塔实验报告范本模板.docx

1、汉诺塔实验报告范本模板课 程 设 计2012年12月21日一、概述数据结构是计算机学科非常重要的一门专业基础理论课程,要想编写针对非数值计算问题的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程都有密切联系，具有独特的承上启下的重要位置.拥有数据结构这门课程的知识准备，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。二、实验目的 通过本实验，掌握复杂性问题的分析方法,了解汉诺塔游戏的时间复杂性和空间复杂性. 三、问题分析任务：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1， 2，

2、。.， n编号。要求借助柱子B,把柱子A上的所有的盘子移动到柱子C上.移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。分析：首先容易证明,当盘子的个数为n时,移动的次数应等于2n - 1。首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数,按顺时针方向依次摆放 A C B。(1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C,则把

3、它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性,其实不然，可实施的行动是唯一的。反复进行（1）（2)操作，最后就能按规定完成汉诺塔的移动。四、实验步骤 1、用c+ 或c语言设计实现汉诺塔游戏；,2、让盘子数从2 开始到7进行实验,记录程序运行时间和递归调用次数；3、画出盘子数n和运行时间t 、递归调用次数m的关系图，并进行分析。五、流程图 六、程序代码：#include iostream。hinclude stdlib。h/ Hanoi 塔cl

4、ass Hanoipublic: Hanoi（） cout ”请输入你想玩的层数（1-20）：； input： cin floor; if （floor 1 | floor 20） cout 层数错误重新输入：； goto input; cout endl; arrayA = new char floor； arrayB = new char *floor; arrayC = new char floor; for (int h = 0； h floor; h+） arrayAh = new charfloor + 1； arrayBh = new charfloor + 1； arrayCh

5、 = new charfloor + 1; for（int i = 0； i floor； i+) for（int j = 0; j floor + 1; j+） arrayAij = 0; arrayBij = 0; arrayCij = 0; for（int n = 0； n floor; n+) for(int m = 0; m = n； m+） arrayAnm = ; stepcount = 0； void HanoiShow() hanoiShow(floor， arrayA, arrayB, arrayC)； void Display（） system(”cls）; cout 第

6、” stepcount ”步” endl； int i; int j； for(i = 0; i floor + 1; i+） if(i = 0） cout A; else cout ； cout ”; for(i = 0; i floor + 1; i+） if(i = 0) cout B； else cout ； cout ” ”； for（i = 0; i floor + 1; i+） if（i = 0) cout C； else cout ； cout ” endl；; for（i = 0; i floor; i+） for（j = 0; j floor + 1； j+) cout a

7、rrayAij； cout ” ； for(j = 0; j floor + 1； j+） cout arrayBij； cout ”； for(j = 0； j floor + 1； j+) cout 0） hanoiShow（n - 1, A， C， B）; move（n， A, B)； hanoiShow(n - 1， C， B， A)； else return; void move（int n, char *D, char S) int dc = 1； int sc = 1； int i； int j； for(i = 0； i floor; i+） if(Di0 = ） dc = i

8、； break； for(j = 0; j floor； j+) if(Sj0 = #） sc = j 1； break; if(sc = 1） sc = floor - 1； for（int k = 0； k floor + 1; k+) Ssck = Ddck; Ddck = 0； stepcount+； Display（); int stepcount; int floor； char arrayA; char arrayB; char arrayC；; #endif自定义头文件#include stdafx。h”include ”Hanoi.h七、程序调试与测试在编译过程中发现错误经查

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