汉诺塔问题的两种解法(2)

第二节 关键性结论

通过反复实践与观察，我们发现了解决汉诺塔问题的思路。无论圆盘的数量有多少，我们都可以把它们当作2个盘子来处理。假设共有N个圆盘，我们把它们想象为两个圆盘，其中一个圆盘是整个塔的塔底——最大的那个盘子，如图6所示，左边那个绿色的盘子就是塔底；另一个圆盘是其余所有的盘子，即，N-1个盘子。这里我们需要发挥一点想象力，即，把一组连续排列的盘子想象为一个盘子。这样一来，多个盘子的问题就转化为2个盘子的问题。用同样的思路来分解这N-1个盘子，这样持续的分解下去，多圆盘的问题最终转化为2个圆盘的问题。

图6 将塔底以外的所有圆盘想象成一个盘子

在上一节中，我们在解决3个盘子的问题时，顺便解决了2个盘子的问题，我们可以回顾一下。在图5中，第1~3步完成了两个盘子的移动——上面的2个小盘子从S移动到B，同样，第5~7步又将两个小盘子从B移动到了T。

两个盘子的解法非常简单，只需3步：

1. 小盘子从“出发点”移动到“缓冲区”；

2. 大盘子从“出发点”移动到“落脚点”；

3. 小盘子再从“缓冲区”移动到“落脚点”。

注意上面的出发点、缓冲区及落脚点都加标了引号，为了表明它们是相对的，以区别于绝对的起点S、绝对的缓冲区B以及绝对的终点T。为了区分两个含义不同的缓冲区，我们称带引号的缓冲区为相对缓冲区。针对图5中的第1~3步而言，出发点为S，相对缓冲区为T，落脚点为B；而对于第5~7步来说，出发点是B，相对缓冲区为S，落脚点为T。

我们引入两套不同的名称（起点、缓冲区、终点与出发点、相对缓冲区、落脚点），是为了在移动盘子的过程中，清晰地表达盘子的运动路径，这些概念将有助于我们将物理问题转化为程序问题。

以图6中的8个盘子为例，我们用逆向推演的方法找到问题的解，即，从最后一步开始，推演到起始的第一步。如图7所示，要想将图6中假想的两个盘子移动到终点T，那么下一步必须将起点S处的绿盘子移动到终点T，然后再将假想的盘子（N-1=7个）从缓冲区B移动到终点T。在后续的说明中，我们将直接使用S、B、T替代“起点S”、“缓冲区B”及“终点T”。

图7 将多圆盘问题转化为两个圆盘问题

为了将中间的7个盘子移动到T，把B上的7个盘子分解为两组，上面的6个盘子为一组，将它们移动至S，塔底的第7个盘子为另一组，移动至T。如图8所示。

图8 继续将多圆盘问题转化为双圆盘问题

下一步该做什么呢？我猜你已经迫不及待地想上手操作了。是的，将S上的6个盘子分为两组，上面5个盘子为一组，从S移动到B，塔底的棕色盘子为另一组，从S移动到T，移动结果如图9所示。

图9 逆向推演盘子的移动过程

接下来的操作我想你已经清楚了，将剩余的5个盘子再分为两组，以此类推，直到所有盘子都移动到T，如图10所示，其中的图③是真正的两个盘子，此时无需再借用想象力，直接将塔尖的小盘子移动到B，将塔底的大盘子移动到T，最后再将小盘子从B移动到T，任务结束。

图10 将全部盘子移动到终点T

在上述过程中，我们一直在运用两个盘子的移动策略：

（1）小盘子从出发点移动至相对缓冲区；

（2）大盘子从出发点移动至落脚点；

（3）小盘子再从相对缓冲区移动到落脚点。

上述推演并没有解决移动N个盘子的问题，但是它将N个盘子的问题转化为N-1个盘子的问题，继而又将N-1个盘子的问题转化为N-2个盘子的问题，直到最后转化为2个盘子的问题。显然，我们已经有了移动两个盘子的办法，因此，剩下的问题是，如何从N走到2，这需要借助于程序来说明。

== 未完待续 ==