2.1　汉诺塔问题

相传，印度教的天神汉诺在创造地球时建了一座神庙，神庙里竖有3根宝石柱子，柱子由一个铜座支撑。汉诺将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔（见图2.1），即所谓的汉诺塔（又称河内塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则：

图2.1　汉诺塔

（1）每次只能移动一个盘子。

（2）盘子只能在3根柱子上来回移动，不能放在他处。

（3）在移动过程中，3根柱子上的盘子必须始终保持大盘在下，小盘在上。

天神说：“当这64个盘子全部移到第三根柱子上时，世界末日就要到了。”这就是著名的汉诺塔问题。

图2.1　汉诺塔

用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个求解该数学模型的算法。从实际问题中抽象出一个数学模型的实质，其实就是要用数学的方法抽取其主要的、本质的内容，最终实现对该问题的正确认识。

汉诺塔问题是一个典型的用递归方法来求解的问题。递归是计算学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。当然，要求这些子问题比原问题简单一些，且在结构上与原问题相同。

根据递归方法，可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问题能够解决，则可以先将63个盘子移动到第二根柱子上，再将最后一个盘子直接移动到第三根柱子上，最后又一次将63个盘子从第二根柱子移动到第三根柱子上，这样则可以解决64个盘子的汉诺塔问题。依次类推，63个盘子的汉诺塔求解问题可以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问题又可以转化为61个盘子的汉诺塔求解问题，直到1个盘子的汉诺塔求解问题。再由1个盘子的汉诺塔的求解求出2个盘子的汉诺塔，直到解出64个盘子的汉诺塔问题。

现在的问题是当n=64时，即有64个盘子时，需要移动多少次盘子？要用多少时间？按照上面的算法，n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。于是

因此，要完成汉诺塔的搬迁，需要移动盘子的次数为

264-1=18 446 744 073 709 551 615

如果每秒移动一次，一年有31 536 000 s，则僧侣们一刻不停地来回搬动，也需要花费大约5 849亿年的时间。这个时间大大超过了科学家们推测的地球的寿命（大约100亿年，已存活46亿年）。

假定计算机以每秒1 000万个盘子的速度进行搬迁，也需要花费大约58 490年的时间。

就这个例子，读者可以了解到理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。

下面用Raptor代码对该问题的求解算法进行描述，如图2.2和图2.3所示。

图2.2　汉诺塔问题的main子图

图2.3　汉诺塔问题的move子程序