用递归解汉诺塔问题

July 25, 2017

这里我默认读者具有基本的递归知识。

汉诺塔是根据一个传说形成的数学问题:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。
问:如何移?

来源:维基百科

3Blue1Brown 在 YouTube 上有个精彩的视频用动画讨论了这个问题,以及二进制计数解法,可以去瞧一瞧。本文主要探讨递归解法,该解法在知乎上也有很高质量的讨论。

这个问题初看很难用代码实现,但通过仔细观察(其实就是看解答啦),可以发现:

  1. 如果我们适当地忽略一些规则,允许几个盘可以一起移动,可以把 A 杆上的圆盘 N 分成两部分,最底层的 1 个圆盘 bottom 和上面的 N-1 个圆盘堆 top。
  2. 我们把 top 移到 B 杆(中转站),bottom 移到 C 杆(目的地),再把 top 移到 C 杆(目的地),即可解决问题。
  3. 再抽象一下,对于有两部分的圆盘堆移动到目的地,需要三个步骤:
    1. top:起始地 -> 中转站
    2. bottom:起始地 -> 目的地(此时的 bottom 是大盘,故不影响其他的盘的移动)
    3. top:中转站 -> 目的地

此时我们就可以给出这个递归的解法了。我们先定义一个函数 move(origin, destination)帮我们打印出步骤,接受两个参数原位置和目标位置。

def move(origin, destination):
    '''
    origin, destination: str
    Print out movement from origin to destination
    '''
    print('Move from %s to %s.' % (origin, destination))

现在定义解决问题的函数 hanoiTowerSolver(n, fr, to, spare),接受四个参数,盘数(N),起始地(A),目的地(C),中转站(B)。

def hanoiTowerSolver(n, fr, to, spare):
    '''
    n: int
    fr: str, the starting rod
    to: str, the destination rod
    spare: str, the rod other than 'fr' and 'to'
    Print out how to move n disks from the starting rod to the the destination rod.
    '''

这个函数达到最小规模 N = 1 的时候,我只要从起始地(fr)移到目的地(to)就好了。

def hanoiTowerSolver(n, fr, to, spare):
    '''
    n: int
    fr: str, the starting rod
    to: str, the destination rod
    spare: str, the rod other than 'fr' and 'to'
    Print out how to move n disks from the starting rod to the the destination rod.
    '''
    if n == 1:
        move(fr, to)

如果 N 不是 1,那么就意味着要移动有两部分的圆盘堆,上文提到:

……对于有两部分的圆盘堆移动到目的地,需要三个步骤:
top(N-1):起始地 -> 中转站
bottom(1):起始地 -> 目的地
top(N-1):中转站 -> 目的地

把这些步骤转换成代码,如下。

def hanoiTowerSolver(n, fr, to, spare):
    '''
    n: int
    fr: str, the starting rod
    to: str, the destination rod
    spare: str, the rod other than 'fr' and 'to'
    Print out how to move n disks from the starting rod to the the destination rod.
    '''
    if n == 1:
        move(fr, to)
    else:
        hanoiTowerSolver(n-1, fr, spare, to)
        hanoiTowerSolver(1, fr, to, spare)
        hanoiTowerSolver(n-1, spare, to, fr)

n = 5,测试结果如下:

Move from A to B.
Move from A to C.
Move from B to C.
Move from A to B.
Move from C to A.
Move from C to B.
Move from A to B.
Move from A to C.
Move from B to C.
Move from B to A.
Move from C to A.
Move from B to C.
Move from A to B.
Move from A to C.
Move from B to C.
Move from A to B.
Move from C to A.
Move from C to B.
Move from A to B.
Move from C to A.
Move from B to C.
Move from B to A.
Move from C to A.
Move from C to B.
Move from A to B.
Move from A to C.
Move from B to C.
Move from A to B.
Move from C to A.
Move from C to B.
Move from A to B.

源代码位于我的 GitHub 仓库中。