文档介绍：1
目录
目录 1
摘要 2
一、背景知识 3
二、问题重述 3
三、算法分析 3
四、流程及程序设计 5
(1)、流程图 5
(2)、模块及其功能介绍 6
五、调试与算法复杂度分析 7
(1)、运行结果 n()、移动演示函数Hanoi::MoveShow() 等）
塔的盘子是字符串由（'=',' '）组成的
另外还有一些函数：Push函数的功能是放入盘子， pop函数的功能是取出盘子
重要函数的分析：
void Move(int n,int A,int B,int C)递归（这里的A，B，C是相对的，不等同外面定义的A塔，B塔，C塔）
{
if(n==1)//递归的终止条件
{
move(A,C);//将A塔上的最后一个盘子盘子直接移动到C塔
}
else{
Move(n-1,A,C,B);//将A塔上的n-1个盘子通过C塔移动到B塔
move(A,C);//将A塔上的最后一个盘子盘子直接移动到C塔
Move(n-1,B,A,C);//将B塔上的n-1个盘子通过A塔移动到C塔
}
}
7
五、调试与算法复杂度分析
(1)、运行结果(以4层Hanoi塔为类)
运行程序得到如下界面：
程序主界面
游戏的初始状态
当完成第一步时，A上第一个盘就移动到B上这时按任意键继续。如下：
8
第一步结束时状态
第二步结束时状态
︰
︰
︰
9
第十五步结束的状态
最后就完成了将A上所有的盘子移动到C盘上。
(2)、Hanoi塔问题复杂度分析
①时间复杂度
程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves（n），用迭代方法计算公式，得到结果moves(n)=2n-1。因此，hanoi函数的时间复杂度为O(2 n) 。
② 空间复杂度
从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间。如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是n，而塔3的容量是n－1，因此所需要的空间总数为3n－1。Hanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范围内，只能解决n值比较小（n<=30）的hanoi问题。对于这个较小的n值，堆栈在空间需求上的差别相当小，可以随意使用。
10
总结
计算机算法设计与分析和现代计算机技术的实际应用相结合，是我在本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的美观的运行结果界面以及另人兴奋的可用程序，都是一个很好的学****和锻炼的过程。使我们巩固了原有的理论知识，培养了我灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力。使我体会到自身知识和能力能在实际中的应用和发挥。通过学****我丰富了计算机操作经验，更增强了对 C++语言的使用技巧。
汉诺塔是个不错的数学游戏，由于问题的有趣，所以能很好地提高参与者地热情与兴趣。现在汉诺塔也被运用于很多智力游戏中，我们在玩手机游戏的时候，也会锻炼一下自己的脑力。汉诺塔也很好的体现了数学的递归思想。设计汉诺塔程序，充分了解汉诺塔问题的本质以及怎样移动盘子。认真看课本的方法，还能对平时上课的内容得到巩固和熟练。
11
参考文献
1 严蔚敏. 数据结构（C语言版）. 清华大学出版社. 2007
2 吴乃陵.,况迎辉. C++程序设计（第2版）. 高等教育出版社. 2007
3 王晓东. 计算机算法设计与分析（第三版）. 电子工业出版社. 2007
12
附录
#include<iostream>
#include<string>
using namespace std;
#include <>
#define MAX 10000
struct Stack{
string data;
Stack *next;
};
class Tower{
int floor;
int broad;
public:
Stack *top;
int Top;
Tower(int s