漢諾塔遞歸算法 Java 實現與思維圖解

問題描述

三根柱子 A、B、C。A 上有 N 個盤子（大在下、小在上）。目標：將所有盤子移至 C，規則：
1. 每次只能移動一個盤子；
2. 大盤子不能壓在小盤子上。

遞歸核心思想

將「移動 N 個盤子從 A 到 C」分解為三步：

1. 將上面 N-1 個盤子從 A 移到 B（借助 C）；
2. 將第 N 個（最大）盤子從 A 移到 C；
3. 將 N-1 個盤子從 B 移到 C（借助 A）。

子問題結構相同，遞歸終止條件：N=1 時直接移動。

完整 Java 代碼

public class HanoiTowerTest {
    public static void main(String[] args) {
        doTowers(4, 'A', 'B', 'C'); // 4 個盤子演示
    }

    public static void doTowers(int topN, char from, char inter, char to) {
        if (topN == 1) {
            System.out.println("移動盤子 1 從 " + from + " 到 " + to);
        } else {
            doTowers(topN - 1, from, to, inter); // 步驟 1：借助 to，將 N-1 從 from 移到 inter
            System.out.println("移動盤子 " + topN + " 從 " + from + " 到 " + to); // 步驟 2
            doTowers(topN - 1, inter, from, to); // 步驟 3：借助 from，將 N-1 從 inter 移到 to
        }
    }
}

執行流程圖解 (N=3)

移動盤子 1 從 A 到 C
移動盤子 2 從 A 到 B
移動盤子 1 從 C 到 B
移動盤子 3 從 A 到 C
移動盤子 1 從 B 到 A
移動盤子 2 從 B 到 C
移動盤子 1 從 A 到 C

總移動次數 = 2^N - 1。N=64 時需 1.84×10^19 次，傳說中世界末日前完成。遞歸深度 N，空間複雜度 O(N)，時間複雜度 O(2^N)。

進階：非遞歸迭代實現思路

• 利用棧模擬遞歸幀；
• 或採用「偶數盤子順時針、奇數盤子逆時針」移動規律（適合動畫演示）。

漢諾塔是遞歸思維的經典入門，掌握「大問題分解為相同結構的小問題」精髓，動態規劃、分治算法皆通此道。