07141326汉诺塔-课程设计
春季儿童饮食-
汉诺塔课程设计
报
告
目
录
一、需求分析„„„„„„„„„„„„„„
(3)
二、概要设计„„„„„„„„„„„„„„
(4)
三、详细设计„„„„„„„„„„„„„„
(6)
四、测试与分析„„„„„„„„„„„„„
(7)
五、总结„„„„„„„„„„„„„„„„
(7)
1
/
8
六、附录：源程序清单„„„„„„„„„„
(8)
一、
需求分析
1
．
1
问题描述
汉诺塔
（又称河内塔）
问题是印度的一个古老的传说。
开天辟地的神勃拉玛
在一个庙里留下了三根金刚石的棒，第一根上面套
着
64
个圆的金片，最大的一
个在底下
，
其余一个比一个小，
依次叠上去，
庙
里的众僧不倦地把它们一个个地
从这根棒搬到另一根棒上，
规定
可利用中间的一根棒作为帮助，
但每次只能搬一
个，而且大的不
能放在小的上面。
这是一个著名的问题，
几乎所有的教材上都有这个问题。
由于条件是一次只
能移动
一个盘，且不允许大盘放在小盘上面，所以
64
个盘的移动次数
是：
2
/
8
18
，
44
6
，
744
，
073
，
709
，
551
，
615
这是一个天文数
字，
若每一微秒可能计算
(
并不输出<
/p>
)
一次移动，
那么也需要
几乎一百万年。
我们仅能找出问题的解决方法并解决较小
N
值时的汉诺塔，
但很
难用计算机解
决
64
层的汉诺塔。
后来，这个传说就演变为汉诺塔游戏
:
1.
有三根杆子
A
，
B
，
C
。
A
杆上有若干圆盘
2.
每次移动一块圆盘，小的只能叠在大的上面
3.
把所有圆盘从
A
杆全部移到
C
杆上
经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方
向移动圆盘：
如
3
阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C
此外，汉诺塔问题也是程序设计中的经典递归问题。
将
n
个盘子从
a
座移动到
c
座可以分解为以下
3
个步骤：
（
1
）
将
a
上
n-1
个盘借助
c
座先移到
b
座上。
（
2
）
把
a
座剩下的一个盘移到
< br>c
座上。
（
3
）
将
n-1
个盘从
c
座借助于
a
座移到
c
座上。
1
．
2
基本要求
（
1
）
输入的形式和输入值的范围：
输入圆盘的数量，类型为整型，大于零。
（
2
）
输出的形式：
运行结果为用字母表示移动盘子的方案，而并非是真正移动盘子。
(3)
程序所能达到的功能；
输入圆盘数量为定值时的移盘方案。
帮助我们更清晰的理解汉诺塔问题，
及递
归调用的应用。<
/p>
二、概要设计
分析问题，找出移动圆盘的正确算法。
将
n
个盘子从
a
座移动到
c
座可以分解为以下
3<
/p>
个步骤：
（
1
）
将
a
上
n-1
个盘借助
c
座先移到
b
座上。
（
2
）
把
a
座剩下的一个盘移到
< br>c
座上。
（
3
）
将
n-1
个盘从
c
座借助于
a
座移到
c
座上。
3
/
8
为了更清楚地描述算法，可以定义
一个函数
movedisc(n,a,b,c)
。该函数的
功能是：
将
N
个圆
盘从
A
杆上借助
C
杆移动到
B
杆上。
这样移动
N
个圆盘的工作
就可以按照以下过程进行：<
/p>
1) hanoi(n-1,a,c,b);
2)
将一个圆盘从
a<
/p>
移动到
b
上；
3)
hanoi(n-1,c,b,a)
；
重复以上过程，直到将全部的圆盘移动到位时为止。
递归运行的层次
递归工作栈状态
（
< br>n
值，
x
值，
< br>y
值，
z
值）
< br>
1
3
，
a
，
b
，
c
塔与圆盘的状态
a
b
c
分析说明
由
HanoiMove
调用
Hanoi
进
入第一层
递归，
入栈。
至
5
行，
因递归调用进下
一层
。
1
2
3
由第一层的语句行
5
进入第二层递归，
入栈，执行至行
5
。
2 <
/p>
2
，
a
，
c
，
b
3
，
a
，
b
，
c
3
1
，<
/p>
a
，
b
，
c
2
，
a
，
c
，
b
3
，
a
，
b
，
c
a
b
c
2
3
1
由第二层行
5
进入第三层递归，入栈。
执行行
3
，将
1
号盘由
a
移至
c
后从行
9
退出第三层递归，出栈。返回二层行
6
。
a
b
c
2
2
，
a
，
c
，
b
3
，
a
，
b
，
c
将
2
号盘由
a
移至
b
后，
从行
7
进入下
一层递归
，入栈。
3
2
a
b
c
1
1
，
c
，
a
，
b
3
2
，
a
，
c
，
b
3
，
a
，
b
，
c
将
1
号盘由
c
移至
b
后，
从行
9
退出第
三层，出栈。
返回到第二层的行
8
。
1
3
2
4
/
8