汉诺塔实验报告

课课 程程 设设 计计 2012 年12 月21日 目录目录 1、概述、概述.4 2 2、实验目的、实验目的.4 3 3、问题分析、问题分析.5 4 4、实验步骤、实验步骤.5 5 5、流程图、流程图.6 6 6、程序代码：、程序代码：.7 7 7、程序调试与测试、程序调试与测试.10 8 8、结论、结论.12 9 9、总结、总结.15 一、概述一、概述 数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问 题的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程 都有密切联系，具有独特的承上启下的重要位置。拥有数据结构这门课程的知识准备， 对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。 二、实验目的二、实验目的 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空 间复杂性。 三、问题分析三、问题分析 任务：有三个柱子 A, B, C. A 柱子上叠放有 n 个盘子，每个盘子都比它下面的盘子要 小一点， 可以从上到下用 1, 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，则把它移动到 A。 （2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。 即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘 这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行 动是唯一的。 反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。 四、实验步骤四、实验步骤 1、用 c+ 或 c 语言设计实现汉诺塔游戏；, 2、让盘子数从 2 开始到 7 进行实验，记录程序运行时间和递归调用次数； 3、画出盘子数 n 和运行时间 t 、递归调用次数 m 的关系图，并进行分析。 五、流程图五、流程图 开始 输入 m（m=20） 是否继续 结束 输出结果 2、 否 1、是 六、程序代码：六、程序代码： #include #include / Hanoi 塔 class Hanoi public: Hanoi() cout floor; if (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 = 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 第 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 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); 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; 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 七、程序调试与测试七、程序调试与测试 在编译过程中发现错误 经查找之后发现没有对主函数 main 说明 经改正后 运行结果运行结果 第一步第一步 先输入要玩的层数 第二步第二步 手动运行手动运行 八、结论八、结论 通过对上述递归在 Hanoi 塔问题上的应用分析，我们可以得出如下结论： 1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这 一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化； 2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不 需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源 （包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑 采用并行计