漢諾塔演算法三種實作全解析：遞迴、模擬遞迴棧、數學規律迭代

問題引入

漢諾塔（Tower of Hanoi）源自印度古老傳說：三根柱子（A、B、C），A 柱自下而上疊放 N 個直徑遞減的圓盤。目標：將所有圓盤移至 C 柱，規則：一次僅能移動一個圓盤，且大盤不得置於小盤之上。最少移動次數為 2^N - 1。

實作一：經典遞迴解法

public void play_recursive(int n, char from, char aux, char to) {
    if (n == 1) {
        System.out.println(from + " -> " + to);
        return;
    }
    play_recursive(n - 1, from, to, aux);  // 將 n-1 個盤借助 to 移至 aux
    System.out.println(from + " -> " + to); // 移動第 n 個盤
    play_recursive(n - 1, aux, from, to);   // 將 n-1 個盤借助 from 移至 to
}

優點：程式碼極簡、邏輯清晰。
缺點：深度遞迴易導致 StackOverflowError（N > 1000 時風險大）。

實作二：非遞迴——手動模擬遞迴棧

核心思想：將遞迴呼叫的參數封裝為 Disk 物件（含狀態 status 與三柱標識），以自訂 Stack 替代系統呼叫棧。

public void play_non_recursive(int diskNum) {
    Stack stack = new Stack();
    stack.push(new Disk(diskNum, 'A', 'B', 'C'));
    Disk popDisk;
    while ((popDisk = stack.pop()) != null) {
        if (popDisk.status == 1) {
            System.out.println(popDisk.A + " -> " + popDisk.C); // 基礎情況：直接移動
        } else {
            // 反序壓入：對應遞迴的三步驟逆序入棧
            stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A, popDisk.C)); // 步驟3
            stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));                   // 步驟2
            stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C, popDisk.B)); // 步驟1
        }
    }
}

關鍵點：status 代表當前子問題規模；status==1 為終止條件。壓棧順序與遞迴呼叫順序相反（後進先出）。

實作三：非遞迴——依數學規律迭代

利用漢諾塔移動的確定性規律，無需棧結構，空間複雜度 O(1)。

核心規律

1. 最小圓盤（1 號）每隔一步移動一次，且移動方向固定：
   • N 為奇數：A → C → B → A（順時針）
   • N 為偶數：A → B → C → A（逆時針）
2. 非最小圓盤的唯一合法移動：在兩個非 1 號圓盤頂的柱子之間，將較小者置於較大者之上。

演算法流程

public void play_regular(int diskNum) {
    // 初始化三柱堆疊
    Stack_play_regular A = new Stack_play_regular('A');
    Stack_play_regular B = new Stack_play_regular('B');
    Stack_play_regular C = new Stack_play_regular('C');
    for (int i = diskNum; i > 0; i--) A.push(i);

    // 依奇偶排列三角順序
    Stack_play_regular[] towers = new Stack_play_regular[3];
    towers[0] = A;
    towers[1] = (diskNum % 2 == 0) ? B : C;
    towers[2] = (diskNum % 2 == 0) ? C : B;

    int minTower = 0; // 最小圓盤所在柱索引
    int moveCount = 0;
    for (int i = 0; i < (Math.pow(2, diskNum) - 1); ) {
        // 1. 移動最小圓盤
        Stack_play_regular src = towers[minTower];
        Stack_play_regular dst = towers[(minTower + 1) % 3];
        System.out.println(src.name + " -> " + dst.name);
        dst.push(src.pop());
        i++; minTower = (minTower + 1) % 3;

        // 2. 執行唯一合法的非最小圓盤移動
        Stack_play_regular t1 = towers[(minTower + 1) % 3];
        Stack_play_regular t2 = towers[(minTower + 2) % 3];
        if (t2.getTop() != -1 && (t1.getTop() == -1 || t1.showTopDisk() > t2.showTopDisk())) {
            System.out.println(t2.name + " -> " + t1.name);
            t1.push(t2.pop()); i++;
        } else if (t1.getTop() != -1 && (t2.getTop() == -1 || t1.showTopDisk() < t2.showTopDisk())) {
            System.out.println(t1.name + " -> " + t2.name);
            t2.push(t1.pop()); i++;
        }
    }
}

三種實作對比總結

延伸思考

• 四柱漢諾塔（Reve's Puzzle）最優解尚無通用公式，屬於開放問題
• 並行化漢諾塔：可將遞迴子問題分派至不同執行緒，但同步開銷大於計算收益
• 位運算解法：第 k 步移動的圓盤編號 = __builtin_ctz(k)（尾部零計數）