汉诺塔

如果你已经完成递归的学习，那么你就已经准备好学习另一个多次递归真正产生效果的问题。它就是汉诺塔。 你将获得三个杆子和$n$‍个圆盘的一组装置，每个圆盘的大小不同。让我们将杆子分别命名为A、B和C，并将圆盘从1（最小的圆盘）开始编号至$n$‍（最大的圆盘）。开始时，所有$n$‍个圆盘都在杆子A上，从底部到顶部按顺序递减，因此圆盘$n$‍位于底部，圆盘1位于顶部。这是有$n=5$‍个圆盘时，汉诺塔的样子：

目标是将所有 $n$‍ 个圆盘从杆子 A 移动到 B：

听起来很简单，对吧？但实际上并不容易，因为你必须遵守两个规则：

你可能认为这个问题并不十分重要。 相反！ 传说在亚洲的某个地方（西藏、越南、印度 —— 选择你喜欢的互联网上的传奇），僧侣们正在解决包含64个圆盘的移动问题，所以故事发展成这样 —— 僧侣们相信，根据这两条规则，一旦他们完成将所有64个圆盘从杆子A移动到杆子B，世界就要终结。如果僧侣行动正确，我们会面临世界末日吗？

首先，让我们看看如何递归地解决问题。我们将从一个非常简单的案例开始：一个圆盘，即 $n=1$‍。 $n=1$‍ 是最基本情况。 你总是可以将圆盘 1 从杆子 A 移动到杆子 B，因为你知道下面的任何圆盘都会比 1 更大。 如果你愿意，可以将圆盘 1 从杆子 B 移动到杆子 C，或者从 杆子 C 移动到 杆子 A，或从任何杆子到任何杆子。 用一个圆盘解决汉诺塔问题有明显答案，它只需要移动一个圆盘一次。

两个圆盘怎么样？当 $n=2$‍ 时，如何解决这个问题？你可以通过三个步骤来完成。下面是它在开始时的样子：

首先，将圆盘 1 从杆子 A 移动到杆子 C：

请注意，我们使用杆子 C 作为备用，放置 圆盘 1 以便我们可以获得 圆盘 2。 现在，圆盘 2 —— 最底层的圆盘 —— 出现，将其移动到杆子 B：

最后，将 圆盘1 从 杆子C 移动到 杆子B：

这个解决方案需要三个步骤，再次将两个圆盘从 杆A 移动到 杆B 没有什么特别之处。你可以使用 杆A 作为备用杆子将它们从 杆B 移动到 杆C：将圆盘1从 杆B 移动到 杆A，然后将圆盘2从 杆B 移动到 杆C，最后将圆盘1从 杆A 移动到 杆C。你是否同意存在三步内将圆盘1和2从任何杆子移动到任何杆子的方法？（说“是”。）

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。