用递归思想完成汉诺塔

汉诺塔传说

汉诺塔源自一个古老的印度传说：在世界的中心贝拿勒斯的圣庙里，一块黄铜板上插着三支宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上穿好了由大到小的64片金片，这就是所谓的汉诺塔（Hanoi Tower）。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片从梵天穿好的金片上移到另一根针上时，世界末日就会来临，而梵塔、寺庙和众生也会随之灭亡......

猩球崛起里面猩猩玩 4 阶汉诺塔

递归思想

递归的核心思想是把规模大的问题转化为规模小的相似的子问题来解决。

当一个问题同时满足以下 2 个条件时，就可以使用递归的方法求解：

• 可以拆解为除了数据规模以外，求解思路完全相同的子问题；
• 存在终止条件。

用递归思想分解汉诺塔问题

相同子问题

• 第二大的金片，从第一根柱子移动到第二根柱子（留出第三根柱子）
• 最大的金片，从第一根柱子移动到第三根柱子
• 第二大的金片，从第二根柱子，移动到第三根柱子

终止条件

只有一个汉诺塔金片时，直接从第一根柱子，移动到第三根柱子

代码实现 Python

'''
n 代表几个金片
a,b,c 分别代表第一、二、三根柱子
'''
def move(n, a, b, c):
    if not str(n).isdigit() or n < 1:
        print("请输入正确的数字, 最少需要一个汉诺塔金片")
        return
    # 终止条件，如果只有一个汉诺塔，直接从x 移动到 c
    if(n == 1):
        print(a,"->",c)
        return
    # 次大的那个盘放在从 a 放在 b, （留出 c 的位置）
    move(n-1, a, c, b)
    # 最大的盘放在从a 放到 c
    move(1, a, b, c)
    # 之前放在 b 位置的盘，从b 移回 c 位置，完成最小单元的递归
    move(n-1, b, a, c)

测试，两片金片：

move(2, "a", "b", "c")

'''
结果:
a -> b
a -> c
b -> c
'''

测试，三片金片：

move(3, "a", "b", "c")

'''
结果:
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
'''

所以呢，这里有个规律，如果希望最优步数完成汉诺塔，那么：
如果是偶数片，第一步往第二根柱子走，
如果是奇数片，第一步往第三根柱子走。
要知道，猩球崛起里面的猩猩，20步就完成了4阶汉诺塔（最优解15步）。