漢諾塔問題：遞歸算法的數學之美與 C 語言極簡實現

漢諾塔問題：遞歸算法的數學之美與 C 語言極簡實現

漢諾塔是遞歸教學的經典案例。三根柱子 A、B、C，A 上有 n 個盤子（小上大下），目標將所有盤子移至 C，規則：每次僅移一盤，大盤不得置於小盤上。遞歸解法將 n 盤問題分解為三個 n-1 盤子問題，代碼極其精簡。

遞歸邏輯推導

1. 將 A 上頂部 n-1 個盤子借助 C 移至 B（子問題：A→B，借助 C）
2. 將 A 上剩餘第 n 個盤子（最大）直接移至 C
3. 將 B 上 n-1 個盤子借助 A 移至 C（子問題：B→C，借助 A）

基例：n=1 時直接移動。

C 語言極簡實現（含完整註解）

#include 

void Hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        printf("FROM %c TO %c\n", from, to); // 基例：直接移動
        return;
    }
    Hanoi(n - 1, from, to, aux);   // 步驟 1：n-1 從 from 移到 aux，借助 to
    printf("FROM %c TO %c\n", from, to); // 步驟 2：第 n 個從 from 移到 to
    Hanoi(n - 1, aux, from, to);   // 步驟 3：n-1 從 aux 移到 to，借助 from
}

int main() {
    int n;
    printf("請輸入漢諾塔盤數: ");
    scanf("%d", &n);
    Hanoi(n, 'A', 'B', 'C');
    return 0;
}

數學性質與複雜度

• 移動次數 T(n) = 2^n - 1，指數級增長。n=64 時約 1.84×10¹⁹ 步，「世界末日」傳說由此而來。
• 時間複雜度 O(2^n)，空間複雜度 O(n)（遞歸棧深度）。
• 最優解唯一（對稱性下），任何最優解序列均對應此遞歸分解。

非遞歸實現思路（擴展）

利用棧模擬遞歸，或根據「奇數盤最小盤循環 A→C→B→A，偶數盤 A→B→C→A」的移動規律迭代生成步驟，可避免棧溢出，適合超大 n 場景。

總結

漢諾塔以 10 行代碼展現了遞歸「將大問題分解為相似子問題」的核心哲學。理解其參數角色互換（from/aux/to 輪換）是掌握遞歸參數化設計的關鍵一課。