汉诺塔问题

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

分析

一股脑地考虑每一步如何移动很困难，我们可以换个思路。三根柱子依次为a、b、c柱，现在目的是将a柱圆盘移动到c柱。

先假设除最下面的盘子之外，我们已经成功地将上面的63个盘子移到了b柱，此时只要将最下面的盘子由a移动到c即可。

当最大的盘子由a移到c后，b上是余下的63个盘子，a为空。因此现在的目标就变成了将这63个盘子由b移到c。这个问题和原来的问题完全一样，只是由a柱换为了b柱，规模由64变为了63。因此可以采用相同的方法，先将上面的62个盘子由b移到a，再将最下面的盘子移到c……对照下面的过程，试着是否能找到规律：

1. 将b柱子作为辅助，把a上的63个圆盘移动到b上
2. 将a上最后一个圆盘移动到c
3. 将a作为辅助，把b上的62个圆盘移动到a上
4. 将b上的最后一个圆盘移动到c
5. ......
1
2
3
4
5

也许你已经发现规律了，即每次都是先将其他圆盘移动到辅助柱子上，并将最底下的圆盘移到c柱子上，然后再把原先的柱子作为辅助柱子，并重复此过程。

这个过程称为递归，即定义一组基本操作，这组操作将规模小一点（或大一点）的操作当做一个整体——无需关心它的细节，只当它已经完成了——然后执行剩下的操作。而在更小或更大的规模中也依此操作，直到规模达到预定值。

Python函数

在python中，我们可以用递归函数来计算汉诺塔问题的解决方案。

def move(n,a,b,c):
    if n == 1:
        print a, '-->', c
    else:
        move(n-1, a, c, b)
        move(1, a, b, c)
        move(n-1, b, a, c)
1
2
3
4
5
6
7

>>> move(3,'A','B','C')
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

>>> move(4,'A','B','C')
A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> 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

以 n=3 为例，我们来看看执行过程：

现在我们想想，这个函数为什么这么写？反推一下：

1. 当 n = 1 ，即 move(1,a,b,c) 时，移动过程是 A --> C ，所以函数可以是

   move(1, a, b, c)

2. 当 n = 2 ，即 move(2,a,b,c) 时，移动过程是 
   
   A --> B
   A --> C
   B --> C ，
   
   所以函数可以是

   move(1, a, c, b)         =       move(2-1, a, c, b)
   
   move(1, a, b, c)         =       move(1, a, b, c)
   
   move(1, b, a, c)         =       move(2-1, b, a, c)
   
3. 当 n = 3 ，即 move(3,a,b,c) 时，移动过程是
   
   A --> C
   A --> B
   C --> B
   A --> C
   B --> A
   B --> C
   A --> C ，
   
   所以函数可以是
   
   move(1, a, b, c)
   move(1, a, c, b)         =       move(3-1, a, c, b)
   move(1, c, a, b)
   
   move(1, a, b, c)         =       move(1, a, b, c)
   
   move(1, b, c, a)
   move(1, b, a, c)         =       move(3-1, b, a, c)
   move(1, a, b, c)

4. 当 n = 4 ，即 move(3,a,b,c) 时，移动过程是
   
   A --> B
   A --> C
   B --> C
   A --> B
   C --> A
   C --> B
   A --> B
   A --> C
   B --> C
   B --> A
   C --> A
   B --> C
   A --> B
   A --> C
   B --> C ，
   
   所以函数可以是
   
   move(1, a, c, b)
   move(1, a, b, c)
   move(1, b, a, c)
   move(1, a, c, b)         =       move(4-1, a, c, b)
   move(1, c, b, a)
   move(1, c, a, b)
   move(1, a, c, b)
   
   move(1, a, b, c)         =       move(1, a, b, c)
   
   move(1, b, a, c)
   move(1, b, c, a)
   move(1, c, b, a)
   move(1, b, a, c)         =       move(4-1, b, a, c)
   move(1, a, c, b)
   move(1, a, b, c)
   move(1, b, a, c)

5. 依次类推，当为n时，需要 2^n-1 步才能完成整个移动过程，而函数可以是

   move(n-1, a, c, b)
   move(1, a, b, c)
   move(n-1, b, a, 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

汉诺塔问题很有意思，通过递归函数可以简单清晰的将其表示出来，递归实际上就是用自己来定义自己。