C語言遞歸解決漢諾塔問題：經典分治演算法完整解析

編輯：關於C語言

漢諾塔是展示遞歸分治思想的教科書級範例。本文詳細解析 C 語言遞歸實作漢諾塔移動邏輯，包含演算法證明、步數計算、以及非遞歸改寫思路。

問題規則與遞歸策略

三根柱子：A(起始)、B(輔助)、C(目標)
n 個圓盤由大到小疊在 A 柱
每次僅能移動最上層圓盤
大圓盤不得置於小圓盤之上
目標：將所有圓盤移至 C 柱

遞歸分解邏輯：

將 n-1 個圓盤從 A 移至 B (以 C 為輔助)
將第 n 個(最大)圓盤從 A 移至 C
將 n-1 個圓盤從 B 移至 C (以 A 為輔助)

完整 C 語言實作

#include <stdio.h>

void hanoi(int n, char from, char aux, char to);

int main() {
    int n;
    printf("請輸入圓盤數量: ");
    scanf("%d", &n);
    printf("移動步驟 (共 %d 步):\n", (1 << n) - 1);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        printf("移動圓盤 %d: %c → %c\n", n, from, to);
        return;
    }
    hanoi(n-1, from, to, aux);      // 步驟 1
    printf("移動圓盤 %d: %c → %c\n", n, from, to);  // 步驟 2
    hanoi(n-1, aux, from, to);      // 步驟 3
}

遞歸深度與呼叫樹分析

n=3 時遞歸呼叫樹：

hanoi(3, A, B, C)
├── hanoi(2, A, C, B)
│   ├── hanoi(1, A, B, C) → A→C
│   ├── 移動圓盤 2: A→B
│   └── hanoi(1, C, A, B) → C→B
├── 移動圓盤 3: A→C
└── hanoi(2, B, A, C)
    ├── hanoi(1, B, C, A) → B→A
    ├── 移動圓盤 2: B→C
    └── hanoi(1, A, B, C) → A→C

數學歸納法證明最少步數

設 T(n) 為 n 圓盤最少移動步數：

基礎情況：T(1) = 1 = 2¹ - 1
遞歸關係：T(n) = 2·T(n-1) + 1
解得：T(n) = 2ⁿ - 1

n=64 時需 2⁶⁴-1 ≈ 1.84×10¹⁹ 步，若每秒一步需 5840 億年，印證傳說中世界末日時程。

非遞歸迭代解法

利用圓盤移動規律：

奇數圓盤：A→C→B→A 循環 (順時針)
偶數圓盤：A→B→C→A 循環 (逆時針)
最小圓盤每隔一步移動一次
其他圓盤唯一合法移動

void hanoi_iterative(int n) {
    char pegs[3] = {'A', 'B', 'C'};
    int total = (1 << n) - 1;
    int dir = (n % 2 == 1) ? 1 : -1;  // 奇數順時針，偶數逆時針
    int pos[64] = {0};  // 記錄各圓盤位置索引 0,1,2
    
    for (int step = 1; step <= total; step++) {
        if (step % 2 == 1) {  // 移動最小圓盤
            int p = 0;
            pos[p] = (pos[p] + dir + 3) % 3;
            printf("移動圓盤 1: %c → %c\n", pegs[(pos[p]-dir+3)%3], pegs[pos[p]]);
        } else {  // 移動其他圓盤
            // 找出唯一合法移動...
        }
    }
}

進階應用與變體

變體	特點	應用場景
四柱漢諾塔	最優解未知，Frame-Stewart 演算法	演算法研究
雙色漢諾塔	圓盤有顏色限制	約束優化問題
並行漢諾塔	多執行緒同時移動	分散式系統排程