1.5 汉诺塔问题

三根立柱（以下称为“塔”）高高耸立，我们将其标记为A、B和C。甜甜圈形状的圆盘套在A塔上。最大的圆盘位于底部，将其称为圆盘1。圆盘1上方的其余圆盘逐渐变小并标有递增的数字。假如要移动三个圆盘，最大的圆盘（也就是底部的圆盘）是圆盘1。第二大的圆盘2将放在圆盘1的上方。最小的圆盘3则放在圆盘2的上方。我们的目标是将所有圆盘从A塔移动到C塔，并遵循以下规则：

□一次只能移动一个圆盘。

□只有塔顶的圆盘才可以被移动。

□大圆盘不能放在小圆盘的上面。

图1.7给出了总体说明。

1.5.1 对塔进行建模

栈是一种以后进先出（Last-In-First-Out, LIFO）概念为模型的数据结构，最后入栈的数据会最先出栈。试想一下老师在给一叠论文评分。放在顶部的论文是教师取出并进行评分的第一篇论文。栈的两个基本操作是压入（push）和弹出（pop）。压入是将新数据项放入栈中的操作，而弹出则是移除并返回最后一次放入的数据项的操作。Java标准库包括一个内置类Stack，它包含push()和pop()方法。

栈是汉诺塔的完美体现。要把圆盘放到塔上，可以执行压入操作。要将圆盘从一个塔移动到另一个塔，可以先从第一个塔中弹出圆盘再将圆盘压入第二个塔上。

下面将塔定义为Stack并把圆盘放到第一个塔上。

1.5.2 求解汉诺塔问题

如何求解汉诺塔问题呢？可以先考虑只需移动一个圆盘的情况。大家都知道该怎么做吧？实际上，移动一个圆盘是汉诺塔递归解决方案的基线条件。需要递归完成的是移动多个圆盘的情况。因此，有两种情况需要编写代码：移动一个圆盘（基线条件）和移动多个圆盘（递归情况）。

我们通过一个具体的例子来理解递归的情况。假设A塔上有三个圆盘（位于顶部、中间和底部），最终要把这三个圆盘都移动到C塔上。实际遍历一遍全过程有助于把问题讲清楚。首先可以将顶部圆盘移动到C塔，再将中间的圆盘移动到B塔，然后将顶部的圆盘从C塔移动到B塔。现在底部圆盘仍然在A塔上，而上面的两个圆盘在B塔上。现在已大致将两个圆盘从一个塔（A）移动到了另一个塔（B）。将底部圆盘从A塔移动到C塔其实就是基线条件（移动单个圆盘）。现在，可以按照从A塔到B塔的相同步骤将上面的两个圆盘从B塔移到C塔。将顶部圆盘移到A塔，中间圆盘移到C塔，最后将顶部圆盘从A塔移到C塔。

三个圆盘的示例包含一种简单的移动单个圆盘的基线条件和移动其他所有圆盘（在本例中为两个）的递归情况，并且使用第三个塔作为暂存塔。我们可以将递归情况分解为三个步骤：

1.将上面的n-1个圆盘从A塔移到B塔（暂存塔），使用C塔作为中转塔。

2.将最底层的圆盘从A塔移到C塔。

3.将n-1个圆盘从B塔移到C塔，使用A塔作为中转塔。

令人惊讶的是，这种递归算法不仅适用于三个圆盘，而且适用于任意数量的圆盘。将其编码为move()方法，让它负责将圆盘从一个塔移到另一个塔（给定第三个暂存塔）。

最后，辅助方法solve()将对要从A塔移到C塔的所有圆盘调用move()。调用solve()后，应该检查A、B和C塔以验证圆盘是否移动成功。

我们会发现圆盘移动成功了。在编写汉诺塔解决方案时，我们不必了解将多个圆盘从A塔移到C塔所需的每一步。在了解了移动任意数量圆盘的通用递归算法并完成编码后，剩下的工作就交给计算机去完成吧。这就是构思递归解法的威力：可以用抽象的方式思考解决方案，而无须在脑海中考虑每一个单独的步骤。

顺便提一下，随着圆盘数量的增加，move()方法的执行次数会呈指数级增长，因此无法解决64个圆盘的情况。向Hanoi的构造函数传递不同的参数，就可以尝试不同圆盘数量的情况。随着圆盘数量的增加，所需的步数呈指数级增长，这正是汉诺塔的传奇之处。关于汉诺塔传说更详细的信息可以从很多渠道进行了解，你也可以阅读更多关于递归解法背后的数学知识，参见Carl Burch在“About the Towers of Hanoi”中的解释（http://mng.bz/c1i2）。