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