文档介绍：课程设计
2012年 12月 21日
目录
1、概述错误！未定义书签。
2、实验目的错误！未定义书签。
3、问题分析 2
4、实验步骤错误！未定义书签。
5、流程图 3
6、程序代码： 4
7、程序调试与测试 8
8、结论错误！未定义书签。
9、总结错误！未定义书签。
一、概述
数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问题的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程都有密切联系，具有独特的承上启下的重要位置。拥有《数据结构》这门课程的知识准备，对于学****计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。
二、实验目的
通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。
三、问题分析
任务：有三个柱子A,B,，每个盘子都比它下面的盘子要小一点，
可以从上到下用1,2,..., n编号。要求借助柱子B,把柱子A上的所有的盘子移动到柱子C 上。
移动条件为：1、一次只能移一个盘子；
2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。
分析：首先容易证明，当盘子的个数为n时，移动的次数应等于2W-1。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A±o 根据圆盘的数量确定柱子的排放顺序：若
n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACBo
按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1 在柱子A,则把它移动到B；
若圆盘1在柱了 B,则把它移动到C；若圆盘1在柱了 C,则把它移动到Ao
接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
反复进行(1) (2)操作，最后就能按规定完成汉诺塔的移动。
四、实验步骤
1、用C++或c语言设计实现汉诺塔游戏；，
2、让盘子数从2开始到7进行实验，记录程序运行时间和递归调用次数;
3、画出盘子数n和运行时间t、递归调用次数m的关系图，并进行分析。
五、流程图
六、程序代码:
ttinclude <iostream. h> ttinclude <stdlib. h>
// Hanoi 塔 class Hanoi
{
public:
Hanoi ()
(
cout〈〈"请输入你想玩的层数(1-20)：
input: cin >> floor;
if (floor < 1 || floor > 20)
cout〈〈"层数错误重新输入： goto input;
}
cout << endl;
* [floor];
*[floor];
*[floor];
arrayA = new char arrayB = new char arrayC = new char
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 HanoiShowO
(
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 << 〃；
i++)
i++