最新消息:

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

App Inventor 少儿编程 1312浏览 0评论

第二节 关键性结论

 

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

汉诺塔问题的两种解法(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”。

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

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

 

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

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

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

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

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

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

 

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

 

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

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

 

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

(1)小盘子从出发点移动至相对缓冲区;

(2)大盘子从出发点移动至落脚点;

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

 

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

 

== 未完待续 ==

您必须 登录 才能发表评论!