课程设计
目录
1、概述.............................................................................................. 4
2、实验目的..................................................................................... 4
3、问题分析..................................................................................... 5
4、实验步骤..................................................................................... 5
5、流程图......................................................................................... 6
6、程序代码：................................................................................. 7
7、程序调试与测试....................................................................... 10
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的关系图，并进行分析。
五、流程图
六、程序代码：
#include <iostream.h>
#include <stdlib.h>
// Hanoi 塔
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)
{
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(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步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。
九、总结
通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开发。
第二篇：二阶汉诺塔
实验二：用状态空间搜索法解决二阶汉诺塔问题
一、实验目的：
解决汉诺塔问题；
掌握状态空间搜索法；
二、实验原理
我们可以用状态空间图表示法来求解问题。状态空间图是由节点以及节点间的连线所构成的图。节点对应问题的解决状态；连线对应状态转换操作，即算符。在二阶汉诺塔问题求解过程中，我们用Sk=(SK0，SK1)表示问题的状态，SK0表示盘A所在的柱号，SK1表示盘B所在的柱号。全部可能的状态有以下9种：
s0=(1,1) s1=(1,2) s2=(1,3)
s3=(2,1) s4=(2,2) s5=(2,3)
s6=(3,1) s7=(3,2) s8=(3,3)
问题的初始状态集合为s={s0}，目标状态集合为G={s4，s8}。算符分别用A（I,j）以及B（I,j）表示。A（I,j）表示把盘A从柱i移到柱j上。一用有12个算符，分别是：
A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2)
B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)
根据9中可能的状态和12中可能的算符,画出下列的状态空间图.
三、实验过程
根据实验原理，在纸上完成二阶汉诺塔的求解过程。并总结用状态图求解的一般思路。
四、主意事项
二阶的是最简单的，在移动的时候主意思维要清晰，不要盲目，以养成好习惯。