16-求解汉诺塔问题

1.5.2　求解汉诺塔问题

汉诺塔问题该如何求解呢？不妨想象一下只需移动一个圆盘的情况。做法大家都该知道吧！实际上，移动一个圆盘正是汉诺塔递归解决方案的基线条件。需要递归完成的是移动多个圆盘的情况。因此，要点就是有两种情况需要编写代码：移动一个圆盘（基线条件）和移动多个圆盘（递归情况）。

为了理解需要递归完成的情况，不妨看一个具体的例子。假设塔A上套有上、中、下3个圆盘，这3个圆盘最终都要被移到塔C上去。遍历一遍全过程或许有助于把问题讲清楚。首先可以把顶部圆盘移到塔C。再将中间圆盘移到塔B。然后可以将顶部圆盘从塔C移到塔B。现在底部圆盘仍在塔A，上面的两个圆盘则在塔B。现在已大致成功将两个圆盘从一个塔（A）移到了另一个塔（B）。把底部圆盘从A移到C其实就是基线条件（移动单个圆盘）。现在可以按照从A到B的相同步骤把两个上面的圆盘从B移到C。将顶部圆盘移到A，将中间圆盘移到C，最后将顶部圆盘从A移到C。

提示 　在讲述计算机科学的课堂上，常常可以见到用木柱和塑料圈制作的塔的小模型。大家可以用3支铅笔和3张纸制作自己的模型。这或许有助于将解决方案直观地呈现出来。

在上述3个圆盘的示例中，包含一种简单的移动单个圆盘的基线条件，以及一种移动其他所有圆盘（这里为两个）的递归情况，这里用到了第3个塔作为暂存塔。递归的情况可以被拆分为以下3步。

（1）将上层n−1个圆盘从塔A移到塔B（暂存塔），用塔C作为中转塔。

（2）将底层的圆盘从塔A移到塔C。

（3）将n−1个圆盘从塔B移到塔C，用塔A作为中转塔。

令人惊奇的是，这种递归算法不仅适用于3个圆盘的情况，还适用于任意数量的圆盘。下面将此算法编码成名为 hanoi() 的函数，该函数负责将圆盘从一个塔移到另一个塔，参数中给出第3个暂存塔。具体代码如代码清单1-22所示。

代码清单1-22　hanoi.py（续）

def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None:
    if n == 1:
        end.push(begin.pop())
    else:
        hanoi(begin, temp, end, n - 1)
        hanoi(begin, end, temp, 1)
        hanoi(temp, end, begin, n - 1)

调用 hanoi() 完成后，应该检查一下塔A、B和C的内容，验证是否所有圆盘都已移动成功。具体代码如代码清单1-23所示。

代码清单1-23　hanoi.py（续）

if __name__ == "__main__":
    hanoi(tower_a, tower_c, tower_b, num_discs)
    print(tower_a)
    print(tower_b)
    print(tower_c)

我们会发现应该已经成功了。在为汉诺塔解法编写代码时，不一定非要对将多个圆盘从塔A移到塔C所需的每一步都能理解。但逐渐弄懂移动任意数量圆盘的通用递归算法并完成编码后，剩下的工作就交给计算机去完成吧。这就是构想递归解法的威力：往往可以用抽象方式思考解法，而不用枯燥地在脑子里把每一步都搞定。

顺便提一下，随着圆盘数量的增加， hanoi() 函数的执行次数将会呈指数级增加，因此连64个圆盘的解法都会算不出来。可以修改一下 num_disc 变量，多试几个不同的圆盘数。随着圆盘数量的增加，所需移动步数将呈指数级增加，这正是汉诺塔的传奇之处。关于汉诺塔的传说的更详细信息在很多地方都能找到。读者若有兴趣了解有关此递归解法背后的数学原理，可参阅Carl Burch在“关于汉诺塔”（About the Towers of Hanoi）中的解释。