用 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 次,會比較放心。
