汉诺塔问题是一个简单的问题,它有一个简明易懂的递归解法,常常被用来当作递归的入门教程。前几天,有个水群里有人在想怎么写非递归的汉诺塔,然后写了用栈模拟的递归做法说它是非递归的……虽然倒也不是不能这么理解,但是显然,对于汉诺塔这种简单的问题,我们应该可以做得更好。

非递归算法

下面就是我的答案了。

def number_to_configuration(n, k):
    n = bin(n)[2:].rjust(k, '0')
    c = [[], [], []]
    f, t, v = 0, 1, 2  # from, to, via
    for i in range(k):
        if n[i] == '0':
            c[f].append(k-i)
            v, t = t, v
        else:
            c[t].append(k-i)
            v, f = f, v
    return c


k = 4
for n in range(2**k):
    print(number_to_configuration(n, k))

该算法的核心是 number_to_configuration,作用是把一个编号翻译成一个汉诺塔的布局。其中 k 控制一共有几个盘子。这个算法其实不是很难想,但是很奇怪的是我没有在网上找到完全一样的算法(维基百科上的非递归做法虽然思路和我一样,但是细节不同),所以还是写篇博客贴出来。

思路

核心思路是将局面表示为 $2^k$ 个数字,并快速将这些数字转换为局面。使用归纳法不难证明局面有 $2^k$ 种,并且我们可以给出一个算法(number_to_configuration)将数字转换为不重复的局面,所以局面和 $2^k$ 个数字一一对应。

对于一个局面 $N$ ,考虑其二进制形式,其中第 $i$ 位表示第 $i$ 个盘子是否已经「归位」。从高位(最高位为第 1 位)到低位(最低位为第 $k$ 位)扫描:

  1. 如果第 $i$ 位为 1,说明第 $i$ 大盘子已归位(从 from 移动到 to),把这个盘子放到 to 上。进而知道子问题 $N[i+1..k]$ 已经从 from 移动到了 via,接下来要解决的问题是将 $N[i+1..k]$ 从 via 移动到 to。
  2. 如果第 $i$ 位为 0,说明第 $i$ 大盘子尚未归位,把这个盘子放在 from 上。进而知道子问题 $N[i+1..k]$ 还在求解中(从 from 移动到 via),需要把 $N[i+1..k]$ 从 from 移动到 via。

翻译成代码就是第一节的小代码了。

另外,编号 $N$ 有个性质,从初始状态经过 $N$ 步移动将达到局面 $N$ ,这也是上面代码中最后循环的道理。

进一步

这个算法只解决了一个小问题:如何把编号翻译成局面。其实还可以进一步考虑:

  1. 如何把局面翻译成编号?
  2. 如何快速求得第 $n$ 步的动作(把哪个盘子移动到哪个柱子上)?

答:请读维基百科(逃)。