汉诺塔问题

汉诺塔问题：相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在 A 杆自下而上、由大到小按顺序放置64个金盘(如下图)。
游戏的目标：把 A 杆上的金盘全部移到 C 杆上，并仍保持原有顺序叠好。
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于 A、B、C 任一杆上。

解法：
考虑两个盘的情况：

1. A 杆上有 2 个盘，先将 A 杆最上面的盘从 A 经过 C 杆移动到 B 杆
2. 然后将下面的盘从 A 杆移到 C 杆
3. 再将 B 杆上的盘子移动到 C 杆

考虑 n 个盘的情况：

1. 将 A 杆上面的 n-1 个盘子从 A 杆上经过 C 杆移动到 B 杆
2. 然后将第 n 个盘从 A 杆移到 C 杆
3. 再然后 B 杆上的 n-1 个盘子移到 C 杆

汉诺塔移动次数的递推式：h（x） = 2 h（x-1） + 1

# 汉诺塔函数定义：将n个盘子从a经过b移动到c
def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n - 1, a, c, b)
        print("moving %s from %s to %s" % (n, a, c))
        hanoi(n - 1, b, a, c)
if __name__ == '__main__':
    hanoi(5, "a", "b", "c")