汉诺塔实验报告
2012 年 12 月 21 日
目录
1、概
述 ................................................................ 错误～未定义书签。4
2、实验目的 ........................................................ 错误～未定义书签。4
3、问题分
析 ..................................................................... ...................... 2 4、实验步
骤 ........................................................ 错误～未定义书签。5
5、流程
图 ..................................................................... .......................... 3 6、程序代
码: .................................................................... ................... 4 7、程序调试与测
试 ..................................................................... .......... 8 8、结
论 .............................................................. 错误～未定义书签。12
9、总
结 .............................................................. 错误～未定义书签。15
一、概述
数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问题
的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程都有
密切联系，具有独特的承上启下的重要位置。拥有《数据结构》这门课程的知识准备，对于
学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。
二、实验目的
通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。
三、问题分析
任务:有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小
一点，
可以从上到下用1, 2, ..., n编号。要求借助柱子B，把柱子A上的所有的盘子移动到柱子C上。
移动条件为:1、一次只能移一个盘子;
2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。
分析:首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 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)
输出结果
1、是
是否继续
2、否
结束
六、程序代码: #include
class Hanoi
{
public:
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++)
{
arrayA[h] = new char[floor + 1];
arrayB[h] = new char[floor + 1];
arrayC[h] = new char[floor + 1];
}
for(int i = 0; i < floor; i++)
{
for(int j = 0; j < floor + 1; j++)
{
arrayA[i][j] = '\0';
arrayB[i][j] = '\0';
arrayC[i][j] = '\0';
}
}
for(int n = 0; n < floor; n++)
{
for(int m = 0; m <= n; m++)
arrayA[n][m] = '#';
}
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 << arrayA[i][j];
}
cout << " ";
for(j = 0; j < floor + 1; j++) {
cout << arrayB[i][j];
}
cout << " ";
for(j = 0; j < floor + 1; j++) {
cout << arrayC[i][j];
}
cout << endl;
}
system("pause");
}
~Hanoi()
{
for (int i = 0; i < floor; i++)
{
delete []arrayA[i];
delete []arrayB[i];
delete []arrayC[i];
}
delete []arrayA;
delete []arrayB;
delete []arrayC;
}
private:
void hanoiShow(int n, char **A, char **B, char **C) {
if(n > 0)
{
1, A, C, B); hanoiShow(n -
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(D[i][0] == '#')
{
dc = i;
break;
}
}
for(j = 0; j < floor; j++) {
if(S[j][0] == '#')
{
sc = j - 1;
break;
}
}
if(sc == -1)
{
sc = floor - 1;
}
for(int k = 0; k < floor + 1; k++) {
S[sc][k] = D[dc][k];
D[dc][k] = '\0';
}
stepcount++;
Display();
}
int stepcount;
int floor;
char **arrayA;
char **arrayB;
char **arrayC; };
#endif
自定义头文件
#include "stdafx.h" #include "Hanoi.h"
七、程序调试与测试
在编译过程中发现错误
经查找之后发现没有对主函数main说明经改正后
运行结果
第一步
先输入要玩的层数
第二步
手动运行
八、结论
通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论: 1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化; 2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源(包括堆栈、软中断和存贮空间等)，并消耗大量处理时间。因此，可以考虑采用并行计算进行处理，但
3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。
九、总结
通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响，
也让我明白掌握了算法将会有助于提高软件的开发。