22 汉诺塔游戏

用递归来玩游戏吧

大纲

• 汉诺塔问题

• 把大象装冰箱

• 算法实现

汉诺塔游戏

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

把大象装冰箱

解决这个问题需要化繁为简的递归思想，把最底下的红色圆盘当作大象，上面四个圆盘当作门。

图中是最常见的五层汉诺塔，其实几层都是一样，这里设为n，冰箱门永远是汉诺塔上面的m=n-1层。那么问题来了，怎样把冰箱门打开？即：怎样把图中的1至4号串珠从A柱移动到B柱？这又变成了一道m层汉诺塔的问题(m=n-1)。你可以继续用把大象装冰箱分几步的思路去考虑m层汉诺塔的解法。推导下去最终就得到了一个两层汉诺塔该怎么移动的问题，

算法实现

只需要使用递归来执行，在极限条件下，如果只有一个圆盘，就直接从a移动到c，如果大于1个，则执行递归。

# 一共有n层圆盘，一开始在A柱上，目标是要放到C柱上，以B柱作为过度。
def hanoi(n,a,b,c):
    if n==1:
        print(a,'->',c)
    else:
        hanoi(n-1,a,c,b)  # 把冰箱门打开
        print(a,'->',c)    # 把大象放进C柱
        hanoi(n-1,b,a,c)  # 把冰箱门关上

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

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C