29.汉诺塔

了解了递归的概念之后，本章我们来完成一个经典的递归算法问题—汉诺塔。汉诺塔（又称河内塔）问题源于印度一个古老的神话传说，如图29-1所示。大梵天创造世界时做了3根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命人把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在3根柱子之间一次只能移动一个圆盘。当所有的圆盘都从一根石柱上移到另外一根石柱上时，世界就将在一声霹雳中消灭。

图29-1 汉诺塔模型那么移动这些圆盘需要多少时间呢？这个我们之后再计算，现在先来看看如何用算法完成汉诺塔上圆盘的移动。汉诺塔用到了五大常用算法之一的分治法。在计算机科学中，分治法是一种很重要的算法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。下面我们就在Scratch中来完成汉诺塔这个游戏。先来创建3个列表，如图29-2所示。创建一个程序来给“list1”添加“圆盘”，这个程序是通过空格键来触发的，内容如图29-3所示。

图29-2 创建3个列表

图29-3 给“list1”添加“圆盘”的程序这里更改“重复执行10次”指令模块中的参数就能设定汉诺塔初始的“圆盘”数。当参数为1的时候表示只有一个“圆盘”。当只有1个“圆盘”时，移动就是将“list1”中的第1项移动到“list3”即可。而对于有2个“圆盘”的情况，则是要先将“list1”中的第1项移动到“list2”中，然后将“list1”中原来的第2项（由于此时“list1”中原来的第1项已经被移走，所以原来的第2项也是新的第1项）移动到“list3”中；最后将“list2”中的第1项移动到“list3”当中。如果再加一个“圆盘”，3个“圆盘”的汉诺塔又如何移动呢？我们还是先初始化一个3个“圆盘”的汉诺塔，如图29-4所示。

图29-4 初始化3个列表此时就需要用到分治法了，如果把第1个和第2个“圆盘”看成一个整体（暂时称为第一部分），那么3个“圆盘”的处理过程就是：先将“list1”中的第一部分移动到“list2”中；然后将“list1”中原来的第3项（由于此时“list1”中原来的第1部分已经被移走，所以原来的第2项也是新的第1项）移动到“list3”中；最后将“list2”中的第1部分对应的2个“圆盘”移动到“list3”中，而2个“圆盘”的移动我们之前已经实现了，整个过程可以通过表291来表示。表29-1 用分治法移动3个“圆盘”的过程

同理，4个“圆盘”的移动情况如表29-2所示。表29-2 用分治法移动4个“圆盘”的过程

5个、6个、7个……“圆盘”的情况都是类似的，这里就不往下列举了，下面来看看具体的程序。我们将最基本的移动“圆盘”的过程用函数来表示，创建函数如图29-5所示。

图29-5 创建新函数这里定义的函数（新的积木）为“移动 圆盘数量 从 列表x 到 列表y 通过 列表z”，表示从哪个列表到哪个列表，经过哪个列表，移动多少个“圆盘”，其中圆盘数量、列表x、列表y、列表z都是参数，分别表示有多少个“圆盘”、起始位置、目的位置以及过渡位置。由前面的描述我们能够大致写出函数的具体内容，如图29-6所示。

图29-6 新函数的具体内容由于在列表操作的指令模块中无法放置参数，所以这里还创建了一个移动单个“圆盘”的函数，如图29-7所示。

图29-7 创建移动单个“圆盘”的函数由程序能够看出，移动单个“圆盘”分为6种情况，1移到2、3，2移到1、3以及3移到1、2。有了移动单个“圆盘”的函数后，之前的汉诺塔函数就变为图29-8所示的内容。

图29-8 修改后的汉诺塔函数这个函数是由之前我们总结的移动规律得到的，假设要移动n个（变量“圆盘数量”的值）“圆盘”，n>1，那么首先就要将n-1个“圆盘”移动到过渡的列表中，然后将最后一个“圆盘”移动到目的位置，最后将n-1个“圆盘”移动到目的位置。这样我们就通过分治法利用递归完成了这个汉诺塔的移动，不过通过之前的例子我们知道，递归需要一个临界条件，而这里的临界条件就是n=1。当n=1时，说明是1个“圆盘”的情况，此时直接将“圆盘”移动到对应位置即可，修改后的函数如图29-9所示。

图29-9 再次修改汉诺塔函数可以将这个函数添加到最开始初始化几个列表的程序后面，如图29-10所示。这样当我们按下空格键时，就会直接开始移动汉诺塔中的“圆盘”了。

图29-10 将新函数添加到初始化列表的程序后面这里要注意函数中的参数。好，现在我们可以来说说移动金刚石柱子上的64个圆盘需要多少时间了。为此我们需要计算一下总共要移动多少步，我们创建一个变量“步数”。在初始化“list1”完成之后，将“步数”重新设为0，同时在每次移动“圆盘”的时候都将“步数”增加1，对应指令模块添加位置如图29-11、图29-12所示。

图29-11 添加变量“步数”的程序

图29-12 移动“圆盘”时计算“步数”的程序假设有n个圆盘，移动次数是f(n)。通过运行程序就能知道f(1)=1，f(2)=3，f(3)=7，f(4)=15，而f(64)=18446 744 073709 551 615。这个数我不是通过运行程序得出来的，如果每一步在Scratch中需要0.0001秒（实际比这个时间要长），那么约1.8×1019步就需要约1.8×1019秒，约等于3×1013分钟，约等于5×1011小时，大概是2×1010天，折合成年约5.8×107年，即58万个世纪，我的计算机运行得都报废了估计还没移完呢。这个数是通过总结前面移动次数的规律得来的， f(1)=1，f(2)=3，f(3)=7，f(4)=15，那么得到f(n)=2n-1。则n=64时，f(n)=264-1，就算真的移动一次圆盘只用0.0001秒，那完成移动金刚石柱子上的64个圆盘也需要58万个世纪。而如果是1秒移动一次的话，则需要5845.54亿年，我想那时地球早就不在了。