用 Python 和 C 语言来写解汉诺塔的程序。每一个都会输出把 3 个圆盘从左侧柱子移到右侧柱子的步骤。思路在汉诺塔的算法里已经说明,所以这里以代码和运行方法为主来介绍。

用 Python 的递归来解

这是最基本的形式。把“把上面的 n−1 个圆盘移开 → 移动圆盘 n → 把 n−1 个圆盘移回来”原样写成函数。

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # 把上面的n-1个圆盘移开
    moves.append((n, src, dst))         # 移动圆盘n
    hanoi(n - 1, via, dst, src, moves)  # 把n-1个圆盘移回来


moves = []
hanoi(3, "左", "右", "中间", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"第{i}步:把{disc}从{src}移到{dst}")
print(f"一共{len(moves)}步")

保存成名为 hanoi.py 的文件,用 python3 hanoi.py 运行,会输出下面的内容。

第1步:把1从左移到右
第2步:把2从左移到中间
第3步:把1从右移到中间
第4步:把3从左移到右
第5步:把1从中间移到左
第6步:把2从中间移到右
第7步:把1从左移到右
一共7步

改变 hanoi(3, ...) 里的 3,不管几个圆盘都能解。不过步数是 2ⁿ−1 次,所以 20 个圆盘约 100 万步,30 个圆盘约 10 亿步,马上就会变成庞大的数量。Python 的递归深度有上限(默认约 1000 层),但汉诺塔的递归深度是圆盘个数加 1 层,所以在碰到问题之前,步数就已经多得过分了。

用 Python 不用递归来解

把用手解时的步骤(解法的文章里的两条规则)原样写成循环的形式。柱子用 0(左)、1(中间)、2(右)的编号来处理。

def hanoi_loop(n):
    names = ["左", "中间", "右"]
    pegs = [list(range(n, 0, -1)), [], []]  # 从下到上
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # 1绕行的顺序
    pos = 0  # 1所在的柱子(order的第几个)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # 奇数步:把1朝定好的方向移到相邻的一根柱子
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # 偶数步:在没有放1的两根柱子里,把小的移到大的上面
            a, b = [p for p in range(3) if p != order[pos]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
        pegs[b].append(pegs[a].pop())
        moves.append((pegs[b][-1], names[a], names[b]))
    return moves


for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
    print(f"第{i}步:把{disc}从{src}移到{dst}")

输出和递归的形式完全一样,都是 7 步。已确认 1~10 个中的任意圆盘数,都会得出和递归形式相同的步骤。

用 Python 从二进制直接求出

这是不用顺着前面的步骤走,直接算出第 m 步该做什么的形式。式子的含义在算法的文章里有说明。

def hanoi_bits(n):
    for m in range(1, 2 ** n):
        disc = (m & -m).bit_length()     # 末尾0的个数+1
        src = (m & (m - 1)) % 3
        dst = ((m | (m - 1)) + 1) % 3
        yield disc, src, dst


print(list(hanoi_bits(3)))

运行后会输出 [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]。每组是(圆盘,起点柱子,终点柱子),和上面的 7 步相同。这个式子会给出圆盘是奇数个时从 0 号柱子移到 2 号柱子、偶数个时从 0 号柱子移到 1 号柱子的步骤,所以想把偶数个圆盘移到右侧时,要把 1 号和 2 号柱子互换着使用。

用 C 语言的递归来解

用 C 语言写,形式也和 Python 一样。

#include <stdio.h>

static int count = 0;

void hanoi(int n, const char *src, const char *dst, const char *via) {
    if (n == 0) return;
    hanoi(n - 1, src, via, dst);
    count++;
    printf("第%d步:把%d从%s移到%s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "左", "右", "中间");
    printf("一共%d步\n", count);
    return 0;
}

保存成名为 hanoi.c 的文件,用 cc -o hanoi hanoi.c 编译,再用 ./hanoi 运行,会输出和 Python 递归形式相同的 7 步,以及“一共7步”。字符串里用了中文,所以请把文件保存为 UTF-8。

写的时候容易卡住的地方

  • 弄错参数的顺序:第 1 次调用要把“辅助柱”和“终点”互换,第 2 次要把“起点”和“辅助柱”互换。这里弄错了,就会出现违反规则的步骤。
  • 忘了停止条件:如果不在 n == 0(或 n == 1)时停下来,就会一直调用下去。
  • 验证方法:把得出的步骤套到盘面上,确认有没有把大圆盘放在小圆盘上的步骤,以及步数是不是 2ⁿ−1 次,就能放心了。