汉诺塔实验报告11页

1、课课 程程 设设 计计2012 年12 月21日目录目录1、概述、概述.42 2、实验目的、实验目的.43 3、问题分析、问题分析.54 4、实验步骤、实验步骤.55 5、流程图、流程图.66 6、程序代码：、程序代码：.77 7、程序调试与测试、程序调试与测试.108 8、结论、结论.129 9、总结、总结.15一、概述一、概述数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问题的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程都有密切联系，具有独特的承上启下的重要位置。拥有数据结构这门课程的知识准备，对于学习计算机专业的其他课程，如操作系

2、统、数据库管理系统、软件工程的都是有益的。二、实验目的二、实验目的 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。 三、问题分析三、问题分析任务：有三个柱子 A, B, C. A 柱子上叠放有 n 个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用 1, 2, ., n 编号。要求借助柱子 B，把柱子 A 上的所有的盘子移动到柱子C 上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。分析：首先容易证明，当盘子的个数为 n 时，移动的次数应等于 2n - 1。首先把三根柱子按顺序排成品字型，把所有的圆盘按从

3、大到小的顺序放在柱子 A 上。根据圆盘的数量确定柱子的排放顺序：若 n 为偶数，按顺时针方向依次摆放 A B C；若 n 为奇数，按顺时针方向依次摆放 A C B。（1）按顺时针方向把圆盘 1 从现在的柱子移动到下一根柱子，即当 n 为偶数时，若圆盘1 在柱子 A，则把它移动到 B；若圆盘 1 在柱子 B，则把它移动到 C；若圆盘 1 在柱子 C，则把它移动到 A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。反复进行（1

4、）（2）操作，最后就能按规定完成汉诺塔的移动。四、实验步骤四、实验步骤 1、用 c+ 或 c 语言设计实现汉诺塔游戏；,2、让盘子数从 2 开始到 7 进行实验，记录程序运行时间和递归调用次数；3、画出盘子数 n 和运行时间 t 、递归调用次数 m 的关系图，并进行分析。五、流程图五、流程图开始输入 m（m=20）是否继续结束输出结果2、否1、是 六、程序代码：六、程序代码：#include #include / Hanoi 塔class Hanoipublic:Hanoi()cout floor;if (floor 20)cout 层数错误重新输入：;goto input;cout endl

5、;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 = 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;

6、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 第 stepcount 步 endl;int i;int j;for(i = 0; i floor + 1; i+)if(i = 0)cout A;elsecout ;cout ;for(i = 0; i floor + 1; i+)if(i = 0)cout B;elsecout ;cout

7、;for(i = 0; i floor + 1; i+)if(i = 0)cout C;elsecout ;cout endl;for(i = 0; i floor; i+)for(j = 0; j floor + 1; j+)cout arrayAij;cout ;for(j = 0; j floor + 1; j+)cout arrayBij;cout ;for(j = 0; j floor + 1; j+)cout arrayCij;cout endl;system(pause);Hanoi()for (int i = 0; i 0)hanoiShow(n - 1, A, C, B);m

8、ove(n, A, B);hanoiShow(n - 1, C, B, A);elsereturn;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;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;step

9、count+;Display();int stepcount;int floor;char *arrayA;char *arrayB;char *arrayC;#endif自定义头文件#include stdafx.h#include Hanoi.h七、程序调试与测试七、程序调试与测试在编译过程中发现错误经查找之后发现没有对主函数 main 说明经改正后运行结果运行结果第一步第一步先输入要玩的层数第二步第二步手动运行手动运行八、结论八、结论通过对上述递归在 Hanoi 塔问题上的应用分析，我们可以得出如下结论：1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进