用 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 次,就能放心了。
