这周简单看看了 Python 的教程，忽然看到了这个汉诺塔，感觉很有意思，记下来

汉诺塔

首先科普一下这个小游戏

印度传说中，大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

据说。。当完成这个任务时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽

摘自百度百科

解决方案

首先我们给这三根柱子进行编号 A, B, C ，所处的位置就是 a, b, c 。现在我们用递归的思维来看这个问题：

如果a柱有n个圆盘，那么就可以看作a有1个底盘和(n - 1)个圆盘，那么这个问题的解决方案就是：

(n - 1)圆盘 A –> B

1底盘 A –> C

(n - 1)圆盘 B –> C

问题解决~

因为我们整体输出的结果都是 a --> c ，因此在执行第一步和第三步的时候，需要把调用三根柱子的参数改变一下，才能保持最后输出的结果是正确的

最后给出代码（这里以 n = 4 举例）

1
2
3
4
5
6
7
8
9
def hanoi(n, a, b, c):
    if n == 1:
        print a, '-->', c
        return 1
    hanoi(n - 1, a, c, b)
    print a, '-->', c
    hanoi(n - 1, b, a, c)

hanoi(4, 'A', 'B', 'C')

输出结果为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

写在最后

使用递归算出来移动次数应该是 f(n) = 2^n - 1 ，当 n = 64 时……算了，世界毁灭就毁灭了吧……

另外，在实际操作中，有一位美国学者发现了一种出人意料的解决方案：

首先将三根柱子按顺时针顺序排成品字型，把所有的圆盘按大小顺序放在A柱上，再根据圆盘的数量确定柱子的排放顺序：当n为偶数时，按顺时针方向依次摆放 A, B, C；当n为偶数，按顺时针方向依次摆放 A, C, B 。

按顺时针方向把圆盘1从现在的柱子移动到下一根柱子

接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上

反复进行操作，最终可以完成汉诺塔的移动