汉诺塔问题

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

关于这个问题，简单的分析一个3层的例子，有a、b、c三根柱子，其中a柱子放着三个盘子1，2，3，c是盘子移动的目的地，b是用来辅助移动的柱子：

• 将 1 从 a 柱子移动到 c
• 将 2 从 a 柱子移动到 b
• 将 1 从 c 柱子移动到 b
• 将 3 从 a 柱子移动到 c
• 将 1 从 b 柱子移动到 a
• 将 2 从 b 柱子移动到 c
• 将 1 从 a 柱子移动到 c

上面只是一个3层汉诺塔的问题，实际上我们要做的是找出规律，而不是尝试向更高层数推进，因为这个问题是比较复杂的，复杂度是O(2^n)，层数稍微高一点，推起来就很费事了。所以我们要先学会放弃，放弃跟踪递归全程的企图。那这里该怎么办呢？假设有 n 层盘子：

• 将前 n-1 层正确的移动到 b 柱子
• 将 n 移动到 c
• 将前 n-1 层的移动分解成将 n-1 移动到 c 和将 n-2 正确的移动到 b
• 以此类推，直到最后将第一层的盘子移动到 c

上面是思路，下面来具体分析一下：

• 将第 n 层的盘子移动到 c，此时 n 由 a -> c
• 接上，此时前 n-1 层由 a -> b
• 完成上述后，前 n-1 层的盘子在 b，那么此时 b 便成为了起源柱子，a 成为了辅助柱子，重复上述步骤

def move(n, a, b, c):
    if n == 1:
        print(a + '-->' + c)
    else:
        move(n - 1, a, c, b)
        print(a + '-->' + c)
        move(n - 1, b, a, c)


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

# 输出
a-->c
a-->b
c-->b
a-->c
b-->a
b-->c
a-->c

用递归写出来的程序通常比较简洁，但是如果不能想通其中的关键也比较容易一头雾水。递归问题的关键是结束条件和如何让问题规模缩小，在分析问题的时候不要陷入展开步骤的泥沼，不然很容易深陷其中不得解�