引言
在印度,有这样一个古老的传说。在世界中心贝拿勒斯的圣庙里,一块黄铜板上插着3根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金盘,这就是所谓的汉诺塔(Tower of Hanoi)。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金盘到另一根针上:一次只移动一片,而且小片必在大片上面。当所有的金盘都从梵天穿好的那根针上移动到第三根针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽……
分析问题
什么是汉诺塔
总结如下:
有 A, B, C 三根柱子,A 柱上有 n(n > 1) 个金盘,金盘的尺寸由下到上依次变小。每次只能移动一片金盘,且大金盘不能位于小金盘之上,使得所有金盘都移动到 C 柱。
问:如何移?最少要移动多少次?
一个最简单的例子
当 n = 1 时,只需1步就能解决:A-->C
( A-->C 表示把 A 柱最上面的一个金盘移动到 C 柱,下同)
一个很简单的例子
当 n = 2 时,只需3步:
一个简单的例子
当 n = 3 时,用一张图来解决:
用语言表述如下:
1
2
3
4
5
6
7
|
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
|
共需7步
扩展到 n
当 n = 4, 5, 6 甚至 20 时,又该怎么办呢?
这个问题看起来很复杂,其实是有规律可循的
根据数学方法计算得出,移动 n 层的汉诺塔所需次数为
关于具体证明的讨论就不属于本文的范畴了
分析算法
可以用递归的思想来解决
将n个金盘从A柱移动到C柱可分解为以下三个步骤:
- 先将 A 柱上的 n-1 个金盘借助于 C 柱移到 B 柱上(把 C 看作临时柱)
- 这一步又可分解为以下三步:
- 将 A 柱上的 n-2 个金盘借助于 B 柱移到 C 柱上
- 将 A 柱上的第 n-1 个金盘移到 B 柱上
- 再将 C 柱上的 n-2 个金盘借助于 A 柱移到 B 柱上
- 然后将 A 柱上的最后一个金盘移到 C 柱上
- 再将 B 柱上的 n-1 金盘借助于 A 柱移到 C 柱上
是不是有点递归的意思了?
博主最近在学习 C 语言,所以试着用 C 来实现这个算法。代码如下
代码
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <stdio.h>
/* 汉诺塔问题,输入金盘的数量 n ,输出将 n 个金盘从 A 柱(借助 B 柱)移动到 C 柱 的过程 */
int counter = 0; /* 初始化计数器 */
void move(char x, char y)
/* 输出一次移动 */
{
printf("\n%c-->%c", x, y);
counter++;
}
void hanoi(int n, char one, char two, char three)
/* 汉诺塔的递归算法 */
{
if (n == 1)
{
move(one, three);
}
else
{
hanoi(n-1, one, three, two);
move(one, three); /* 把 two 看作临时柱 */
hanoi(n-1, two, one, three);
}
}
int main()
{
for(;;) /* 实现多次模拟 */
{
int n;
printf("汉诺塔层数:");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
printf("\n\n移动次数:%d\n\n", counter);
counter = 0; /* 重置计数器 */
}
}
|
Python
当然也少不了Python啦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
# 汉诺塔问题,输入金盘的数量 n ,输出将 n 个金盘从 A 柱(借助 B 柱)
# 移动到 C 柱 的过程
counter = 0 # 初始化计数器
def move(x, y):
'''输出一次移动'''
global counter
print(f"{x}-->{y}")
counter += 1
def hanoi(n, one, two, three):
'''汉诺塔的递归算法'''
if n == 1:
move(one, three)
else:
hanoi(n-1, one, three, two)
move(one, three)
hanoi(n-1, two, one, three)
while 1:
n = int(input("汉诺塔层数:"))
hanoi(n, 'A', 'B', 'C')
print(f"移动次数:{counter}\n")
counter = 0 # 重置计数器
|
结语
想起一句名言
算法 + 数据结构 = 程序
这是博主第一次真正认真学习算法,从此打开了新世界的大门(笑)
参考文献
[1]于延.C语言程序设计与实践[M].北京:清华大学出版社,2018(2019重印)