理解汉诺塔的Python实现

Question

我明白用Python递归来解决汉诺塔问题的思路，但我不太明白我们是怎么写出这段Python代码的：

def hanoi(n,x,y,z):
    if n == 1:
        print(x, ' --> ',z)
    else:
        hanoi(n-1,x,z,y)
        print(x, ' --> ',z)
        hanoi(n-1,y,x,z)
hanoi(2,'SRC','TMP','TAG')

如果第一步是把(x-1)个盘子从源柱子移动到临时柱子，为什么我们要写hanoi(n-1,z,y)？为什么要把z和y调换位置呢？

谢谢！

Answer 1

你对变量的理解有些错误：

• n 是盘子的数量
• x 是第一个柱子
• y 是用来搬运的柱子
• z 是搬到的目标柱子

因为我们想要解决 hanoi(n, x, y, z)，我们可以这样做：

• 如果只有一个盘子要移动，那就完成了（也就是 n==1 的情况）
• 否则，我们需要把盘子从起始柱子（x）移动到目标柱子（z），中间要用到临时柱子（y）

具体步骤是，先把 n-1 个盘子从 x 移动到 y，这时用到 z（也就是 hanoi(n-1, x, z, y)），然后把最后一个盘子移动到 z，最后再把剩下的所有盘子（在 y 上的）移动到 z（目标柱子），这一步用 hanoi(n-1, y, x, z) 来完成。

---

这里有个动图来帮助理解：