汉诺塔论文
父亲节送什么礼物最好-
目
录
目
录
..........................
....................................1
摘
要
.
..................................................
..........2
一、背景知识
.........
..............................................3
二、问题重述
.....................
..................................3
三、算法分析
.....................
..................................3
四、流程及程序设计
.......
..........................................5
(1)
、流程图
.
....................................
..................5
(2)
、模块及其功能介绍
.
...............................
.............6
五、调试与算法复杂度分析
.......................................
....7
(1)
、运行结果
.
.............................
.......................7
(2)
、
H
ANOI
塔问题复杂度分析
..............................
..........9
总
结
..........................
.................................10
参考文献
.......................
...................................11
附
录
.
..................................................
.........12
1
摘
要
汉诺威塔是一款集娱乐与运算的智
力游戏，
它不仅能使人在休闲的时候放松
心情，而且还能在玩的
过程中不断的提高你的思维能力。
有三个柱子
A, B,
C
。
A
柱子
上叠放有
n
个盘子，每个盘子都比它下面的盘子
要小一点，
可以从上到下用
1, 2, ..., n
编号。
要求借助柱子
C
，
把柱子
A
上的所有的
盘子移动到柱子
B
上。移动条件为：
1
、一次只能移一个盘子
2
、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上
本文的主要算法是利用函数的递归调用算法。首先，想办法将
A
座上的前
n-1
个
盘借助
C
座移动到
B
< br>座上，然后将
A
组上的第
n
个盘移动到
C
座上。然后再
将
B
座上的
n-1
个盘借助
A
座移动到
C<
/p>
座上，此次移动也和第一次移动一样，
重复递归，直到最后一个盘
为止。
关键词：汉诺塔
递归思想
函数调用
数组
指针
2
一、背景知识
汉诺塔
（又称河内塔）
问题来自中东地区一个古老的传说：在世界刚被创
建的时候有一座钻石宝塔（塔
A),
其上有
64
个金碟。所有碟子按从大到小的次
序从塔底
堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔
B
和塔
C
）
。从世
界创始
之日起，
婆罗门的牧师们就一直在试图把塔
A
< br>上的碟子移动到塔
C
上去，
其间
借助于塔
B
的帮助。每次只能移动一个碟子，任何时候都不能把
一个碟子
放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。
19
世纪的法国大数学家鲁卡曾经研究过这个问
题，他正确地指出，要完成
这个任务，僧侣们搬动金盘的总次数（把
1
个金盘从某个塔柱转移到另
1
个
塔
柱叫做
1
次）为：
< br>18
，
446
，
744
，
073
，
709
，
551
，
615
次。假设僧侣们个个身
强力壮，每天<
/p>
24
小时不知疲倦地不停工作，而且动作敏捷快速，
1
秒钟就能移
动
1
个金盘，那么，完成这个任务也得花
5800
亿
年！
二、问题重述
有三个柱子
A, B, C
。
A
柱子上叠放有
n
个盘
子，
每个盘子都比它下面的盘子要
小一点，
可以从上到下用
1, 2, ..., n
编号。
要求借助柱子
C
，
把柱
子
A
上的所有的盘
子移动到柱子
B
上。移动条件为：
1
、一次只能移一个盘子；
2
、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。<
/p>
用计算机算法思想解决该问题，利用
C
++
实现其动态演示。
三、算法分析
设
A
上有
n
个盘子。
当
n=1
时，则将圆盘从
A
直接移动到
C
。
当<
/p>
n
大于等于
2
时
，移动的过程可分解为三个步骤：
第一步
把
A
上的
n-i
个圆盘移到
B
上；
第二步
把
A
上的一个圆盘移到
C
上；
第三步
把
B
上的
n-i
个圆盘移到
C
上；其中第一步和第三步是类同的。
为了更清楚地描述算法，用图示法描述如下：
将
N
个盘子从
A
杆上借助
C
杆移动到
B
杆上。这样移动
N
个盘子的工作
就可以按照以下过程进行：
①第一次调用递归
②将一个盘子从
A
< br>移动到
B
上；
3
③第二次调用递归
重复以上过程，直到将全部的盘子移动到位时为止。
由递归算法我们可以得到递推关系：
M(n)=2M(n-1)+1
当
n>1
时
M(n)=1
当
n=1
时
4
四、流程及程序设计
(1)
、流程图
开始
定义结构体数组
M
存
放盘号和塔座高度
程序初始化
输入要演示的盘块数
n
n<1||n>10
绘制塔座和盘块
n=10
调用递归函数
hanoi(
)
n= =1?
调用
move(
)
函数将
盘块从
A
移到
C
再将
A
的第
n
个盘块移到
C
将前
n-1
个盘块从<
/p>
A
移到
B
最后
将
B
上的
n-1
个盘移到
C
结
束
有上述流程图得出实现递归函数过程的流程图设计如下图所示：
5
开
始
n= =1?
将前
n-1
个盘块
从
A
座移到
B
座
将盘块从
A
座移到
C
座
再将
A
座的第<
/p>
n
个盘块移到
C
座
最后将
B
座上的
n-1
个盘块移到
C
座
结
束
(2)
、模块及其功能介绍
首先定义两个类
:
Tower
类（栈）
Hanoi
类（包含三个
Tower
类对象组成）
，程
序中大部份功能函数封装在这两个类中（包括：递归算法
Hanoi::Move(
)
、图形
显示函数
Hanoi::Ou
tlin()
、移动演示函数
Hanoi::MoveShow
()
等
）
塔的盘子是字符串由（
'=','
'
）组成的
另外还有一些函数：
Push
函数的功能是放入盘子，
pop
函数的功能是取出盘子
重要函数的分析：
void
Move(int n,int A,int B,int
C)
递归
（这里的
< br>A
，
B
，
C
是相对的，不
等同外面定义的
A<
/p>
塔，
B
塔，
C<
/p>
塔）
{
if(n==1)//
递归的终止条件
{
mo
ve(A,C);//
将
A
塔上的最后
一个盘子盘子直接移动到
C
塔
}
else{
Move(n-1,A,C,B);//
将
A
塔上的
n-1
个盘子通过
< br>C
塔移动到
B
塔
move(A,
C);//
将
A
塔上的最后一个盘子盘
子直接移动到
C
塔
Move(n-1,B,A,C);//
将
B
塔上的
n-1
个盘子通过
A
塔移动到
C
塔
}
}
6
五、调试与算法复杂度分析
(1)<
/p>
、运行结果
(
以
4
层
Hanoi
塔为类
)
运行程序得到如下界面：
程序主界面
游戏的初始状态
< br>当完成第一步时，
A
上第一个盘就移动到
B
上这时按任意键继续。如下：
7
第一步结束时状态
第二步结束时状态
︰
︰
︰
8
第十五步结束的状态
最后就完成了将
A
上所有的盘子移动到
C
盘上。
(2)
、
Hanoi
塔问题复杂度分析
①时间复杂度
程序所花时间正比于所
输出的信息行数目，而信息行的数目则等价于盘子
的移动次数。考察程序，设盘子移动次
数为
moves
（
n
< br>），用迭代方法计算公式，
得到结果
moves(n)=
2n-1
。因此，
hanoi
函数的时
间复杂度为
O(2 n)
。
② 空间复杂度
从每个塔上移走盘子
时是按照
LIFO
进行，因此可以把每个塔表示成一个堆
栈。
3
座塔在任何时候总共拥有的盘子都是<
/p>
n
个。如果使用链表形式的堆栈，只
需申
请
n
个元素所需要的空间。如果使用的是基于公式化描述的堆栈
，塔
1
和
塔
2
的容量都必须是
n
，
< br>而塔
3
的容量是
n
－
1
，
因此所需要的空间总
数为
3n
－
1
。
Hanoi
塔问题的复杂性是以
n<
/p>
为指数的函数，
因此在可以接受的范围内，
只能解
决
n
值比较小（
n<=30
）的
hanoi
问题。对于这个较小的
n
值，堆栈在空间需求
< br>上的差别相当小，可以随意使用。
9
总
结
计算机算法设计与分析和现代计算机技术的实际应用相结合，是我在本阶
段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思
路到运
行调试后的美观的运行结果界面以及另人兴奋的可用程序，都是一个很
好的学习和锻炼的
过程。使我们巩固了原有的理论知识，培养了我灵活运用和
组合集成所学过知识及技能来
分析、解决实际问题的能力。使我体会到自身知
识和能力能在实际中的应用和发挥。通过
学习我丰富了计算机操作经验，更增
强了对
C++
语言的使用技巧。
汉诺塔是个不错的数学游戏，由于问题的有趣，所以能很好地提高参与者
地
热情与兴趣。现在汉诺塔也被运用于很多智力游戏中，我们在玩手机游戏的
时候，也会锻
炼一下自己的脑力。汉诺塔也很好的体现了数学的递归思想。设
计汉诺塔程序，充分了解
汉诺塔问题的本质以及怎样移动盘子。认真看课本的
方法，还能对平时上课的内容得到巩
固和熟练。
10
参考文献
1
严蔚敏
.
数据结构（
C
语言版）
.
清华大学出版社
. 2007
2
吴乃陵
.,
况迎辉
. C++
程序设计（第
2
版）
.
高等教育出版社
. 2007
3
王晓东
.
计算机算法设计与分析（第三版）
.
电子工业出版社
. 2007
11