漢諾塔演算法詳解與 C 語言實作完整指南

漢諾塔問題：經典遞迴演算法的典範

漢諾塔（Tower of Hanoi）是電腦科學中最著名的遞迴問題之一，源自一個古老的印度傳說。遊戲規則簡單卻極具啟發性：有三根柱子（A、B、C），A 柱上堆疊著 n 個大小不一的圓盤，大盤在下、小盤在上。目標是將所有圓盤從 A 柱移動到 C 柱，過程中必須遵守「大盤不得置於小盤之上」且「每次只能移動一個圓盤」的規則。

核心邏輯：分治與遞迴思維

解決漢諾塔的關鍵在於「分治策略」。無論圓盤數量多少，核心步驟始終只有三步：

1. 將 A 柱上方的 n-1 個圓盤借助 C 柱移動到 B 柱；
2. 將 A 柱剩下的最大圓盤（第 n 個）直接移動到 C 柱；
3. 將 B 柱上的 n-1 個圓盤借助 A 柱移動到 C 柱。

這種將大問題分解為相同結構的子問題，直到基本情況（n=1 直接移動）的思維，正是遞迴演算法的精髓所在。移動次數呈指數增長，公式為 2ⁿ - 1，這也說明了為何圓盤數稍多即極難人工完成。

C 語言完整實作碼

以下是標準的遞迴實作，包含使用者輸入圓盤數並輸出每一步移動指令：

#include <stdio.h>

void Hanoi(int count, char from, char aux, char to) {
    if (count == 1) {
        printf("FROM %c TO %c\n", from, to);
    } else {
        Hanoi(count - 1, from, to, aux);      // 步驟 1：n-1 個從 from 移到 aux
        printf("FROM %c TO %c\n", from, to);  // 步驟 2：第 n 個從 from 移到 to
        Hanoi(count - 1, aux, from, to);      // 步驟 3：n-1 個從 aux 移到 to
    }
}

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

程式碼關鍵點解析

• 函式參數設計：Hanoi(count, from, aux, to) 中 from、aux、to 分別代表起始柱、輔助柱、目標柱，遞迴呼叫時參數順序交換體現「借助」關係的動態變化。
• 終止條件：count == 1 時直接輸出移動指令，避免無限遞迴。
• 時間複雜度：O(2ⁿ)，空間複雜度（遞迴堆疊深度）O(n)。

延伸應用與變體

漢諾塔不只是教學範例，其遞迴結構廣泛應用於磁碟排程、資料備份策略、甚至類神經網路架構設計。若需優化，可改用非遞迴迭代法（利用堆疊模擬）或位元運算直接計算第 k 步移動，適合嵌入式系統或即時性要求高的場景。

總結

漢諾塔以極簡規則展現遞迴之美，是理解分治法、遞迴終止條件、堆疊溢位風險的最佳切入點。掌握其 C 語言實作，不僅能強化演算法思維，更能為後續學習樹狀結構遍歷、動態規劃等進階主題打下堅實基礎。