算法精粹：经典计算机科学问题的Python实现
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

本题共涉及3根立柱（以下称为“塔”），不妨将其标为A、B和C。塔A外面套有几个环形的圆盘。最大的圆盘位于底部，不妨将其称为圆盘1。圆盘1上方的其他圆盘标记为不断增大的数字，圆盘尺寸则不断减小。假定要移动3个圆盘，最大也是底部的圆盘就是圆盘1。第二大的圆盘2将放在圆盘1的上方。最小的圆盘3则放在圆盘2的上方。本题的目标是按以下规则把所有圆盘从塔A移动到塔C：

● 每次只能移动一个圆盘；

● 只有塔顶的圆盘才能被移动；

● 绝不能把大圆盘放在小圆盘的上面。

图1-7对本题给出了总体说明。

图1-7 本题的挑战是把3个圆盘从塔A移到塔C，每次移动一个圆盘，不允许把大圆盘压在小圆盘之上

栈是按照后进先出（LIFO）理念建模的数据结构。最后入栈的数据项会最先出栈。栈的两个最基本操作是压入（push）和弹出（pop）。压入操作是把一个新数据项放入栈中，而弹出操作则是移除并返回最后一次放入的数据项。在Python中用list类型作为底层存储，即可轻松对栈进行建模。具体代码如代码清单1-20所示。

代码清单1-20 hanoi.py

from typing import TypeVar, Generic, List
T = TypeVar('T')

class Stack(Generic[T]):
def __init__(self) -> None:
        self._container: List[T] = []

def push(self, item: T) -> None:
        self._container.append(item)

def pop(self) -> T:
return self._container.pop()

def __repr__(self) -> str:
return repr(self._container)

注意 上述Stack类实现了__repr__()方法，这样想要查看某个塔的状况就比较容易了。对Stack类调用print()时，输出的就是__repr__()的结果。

注意 正如本书引言中所述，本书通篇都会使用类型提示。从typing模块导入Generic，就能让Stack在类型提示时泛型化为某种类型。T = TypeVar('T')定义了任意类型T。T可以是任何类型。后续在求解汉诺塔问题时使用的Stack，就用到了类型提示，类型提示为Stack[int]类型，表示T应该填入int类型的数据。换句话说，该栈是一个整数栈。如果对类型提示还存在困惑，不妨阅读一下附录C。

栈是汉诺塔的完美表现。要把圆盘放到塔上，可以进行压入操作。要把圆盘从一个塔移到另一个塔，就可以先从第一个塔弹出再压入第二个塔上。

下面将塔定义为Stack，并把圆盘码放在第一个塔上，具体代码如代码清单1-21所示。

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

num_discs: int = 3
tower_a: Stack[int] = Stack()
tower_b: Stack[int] = Stack()
tower_c: Stack[int] = Stack()
for i in range(1, num_discs + 1):
    tower_a.push(i)

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

为了理解需要递归完成的情况，不妨看一个具体的例子。假设塔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）中的解释。

上一章目录下一章