3.3　汉诺塔

汉诺塔问题是程序设计中的经典递归问题。

汉诺塔（又称河内塔）游戏是一个非常著名的益智游戏玩具，现在市面上卖的这个玩具外形如图3-15所示，这个游戏是从一个古老的传说演化而来。

图3-15

3.3.1　古老的传说

相传在印度的贝纳雷斯，有座大寺庙，寺庙中有一块红木板，上面插着三根钻石棒，在盘古开天地，世界刚创造不久之时，神勃拉玛便在其中一根钻石棒上，放了64枚纯金的金片（圆盘），最大的圆盘在最底下，其余一个比一个小，依次叠上去。有一个叫婆罗门的门徒，不分日夜的向这座寺庙赶路，抵达后，就尽力将64枚纯金的圆盘移到另一根钻石棒上，在移动过程中，一次只能移动一个圆盘，且圆盘在放到钻石棒上时，大的不能放在小的上面。可利用中间的一根钻石棒作为辅助移动用。等到婆罗门完成这项工作，寺庙和婆罗门本身都将崩溃，世界将在一声霹雳中毁灭。

那么，世界毁灭会在哪一天呢？

经过计算，需要移动圆盘的次数是一个天文数字18,446,744,073,709,551,615（64个圆盘需要移动的次数为2的64次方）。假设1微秒进行一次移动，也需要约60万年的时间！当移动一个圆盘需花1秒钟时，完成所有圆盘的移动需要近6000亿年！何况移动一个圆盘的时间肯定不止1秒。

离世界毁灭还早得很，人们就根据这个传说演变成汉诺塔游戏，这个游戏的规则是：

将左侧柱子中从小到大放置的8个圆盘移到右侧的圆柱上。

每次只能移动一个圆盘。

小的圆盘只能放在大的圆盘之上。

可以借助另一个圆柱进行辅助移动。

那么，这个游戏该怎么玩呢？

假设有8个圆盘，如图3-16所示，将A柱中的最小圆盘移到C柱，再将A柱中第2个圆盘移到B柱。

图3-16

接下来该怎么办呢？又该怎么移动其余的圆盘呢？

3.3.2　从两个盘考虑

如图3-16所示的8个圆盘，移动起来就很麻烦，更别说64个圆盘的移动了。那么，我们先将问题简化一下，从两个圆盘开始考虑。即将A柱中的两个圆盘移到C柱，这个问题就简单了，如图3-17所示，共分3步即可完成任务：

图3-17

（1）从A柱将小圆盘移到B柱。

（2）从A柱将下方大圆盘移到C柱。

（3）从B柱将小圆盘移到C柱，完成。

好，两个圆盘的移动通过3步就解决了，那么如果要从A柱移动3个圆盘到C柱又该怎么办呢？

由于已经知道将两个圆盘移动到另一个柱子时需要3个步骤，因此，这时就可以不再考虑两个圆盘的移动了。

这时，可考虑将两个圆盘的移动看作一个整体，即A柱的3个圆盘中上面的两个圆盘看作为一个圆盘，下方最大圆盘作为一个圆盘，则3个圆盘的移动又可化解为两个圆盘的移动。这样，只需要3个步骤就可完成移动，如图3-18所示。

图3-18

在图3-18中有以下3步：

（1）将A柱中的小圆盘（由上方两个圆盘组成）移到B柱。

（2）将A柱中的大圆盘（最下方的圆盘）移到C柱。

（3）将B柱中的小圆盘（由上方两个圆盘组成）移到C柱，完成。

在上面的第（1）步和第（3）步中，是将两个圆盘打包移动的。但是，按规则一次只允许移动一个圆盘，这里只是假想一次移动两个圆盘，在实际移动过程中，第（1）步和第（3）步中的每一步最终还是必须分解为3个步骤。

因此，如图3-19所示，在第（1）步中将上面的两个圆盘从A柱移到B柱时，需借助C柱作为辅助柱来进行移动。而在第（3）步中将B柱中的两个圆盘移到C柱时，需借助A柱作为辅助来进行移动。

图3-19

将各动作分解后，可以看出，将3个圆盘从A柱移动到C柱时需要7步（第（1）步分解为3个步骤，第（3）步分解为3个步骤，再加上第（2）步中的1个步骤）。

3.3.3　找出递归结构

经过上面的推算可看出，3个圆盘的移动需要7步，那么移动4个圆盘呢？

与3个圆盘类似，对于4个圆盘也可分为3个大的步骤，如图3-20所示。

图3-20

（1）将A柱中的小圆盘（由上方3个圆盘组成）移到B柱。

（2）将A柱中的大圆盘（最下方的圆盘）移到C柱。

（3）将B柱中的小圆盘（由上方3个圆盘组成）移到C柱，完成。

接着第（1）步、第（3）步需要移动3个圆盘，移动的步骤分别为7步，则将4个圆盘从A柱移动到C柱需要7＋1＋7＝15步。

对比图3-18和图3-20可以看出，如果不考虑第（1）步和第（3）步移动圆盘的数量，这两个图完全一样。也就是说，不管移动多少个圆盘，其实，移动的操作相似。

既然解决问题时具有相似步骤，并且可逐步缩减问题规模，就可考虑使用递归算法来求解。通过上面对移动3个圆盘和4个圆盘时的分析，可总结出汉诺塔的递归结构，对于移动n个圆盘的汉诺塔，可分解为3步，如图3-21所示。

图3-21

（1）移动（n－1）个圆盘。

（2）移动第n个圆盘。

（3）移动（n－1）个圆盘。

而“移动（n－1）个圆盘”又可继续分解，直至分解到只剩一个圆盘时，直接移动到目标柱为止。

根据图3-21所示的递归结构，可将汉诺塔问题的递归求解法分解为以下步骤。

（1）如果只有一个圆盘，则把该圆盘从A棒移动到C棒，完成任务。

（2）如果圆盘数量n＞1，移动圆盘的过程可分为3步。

（1）将A棒上的n－1个圆盘移到B棒上。

（2）将A棒上的一个圆盘移到C棒上。

（3）将B棒上的n－1个圆盘移到C棒上。

3.3.4　实现程序

将递归结构找出来以后，编写递归程序就很简单了，下面的代码就是用C语言编写的实现汉诺塔的递归程序。

在以上程序中，函数hanoi()是一个递归调用的函数。这个函数共有4个参数，第1个参数表示要移动的圆盘数量，第2～4个参数表示移动的源位置、临时位置、目标位置。例如，以下调用hanoi()函数的形式：

表示有h个圆盘要从A柱移到C柱，B柱作为临时辅助用的柱。

在递归调用时，需要搞清楚每次移动圆盘的源位置和目标位置。例如，若要将h个圆盘从A柱移到C柱，则需要将（h－1）个圆盘先从A柱移到B柱（借助C柱作为临时辅助），完成这个操作需按以下方式调用hanoi()函数：

接着将第h个圆盘从A柱移到C柱。

然后将临时放在B柱的（h－1）个圆盘移到C柱（借助A柱作为临时辅助），这时需按以下方式调用hanoi()函数：

执行以上程序，当输入4个圆盘时，移动圆盘的过程如图3-22左图所示，共需15次可完成任务。当输入6个圆盘时，移动圆盘的过程如图3-22右图所示，共需要63次可完成任务。

图3-22

3.3.5　究竟需要移动多少次

根据我们前面手工推算移动次数，以及图3-22所示计算机程序运行得出的移动次数，可发现当需要移动的圆盘数量为1、2、3、4、5、6……时，移动圆盘的次数分别为：

可以看出，圆盘数量按自然数序列递增，但移动次数却呈接近倍数的方式递增：

按上面列表中计算的移动次数，每次都是在上一次移动次数的基础上乘以2再加1，如果要直接计算移动n个圆盘需要多少次移动，就需要逐个推算。其实，仔细分析上面的列表，可发现如下规律：

这样，当要移动64个圆盘，就需要：