Java 遞歸解決漢諾塔問題：完整步驟與移動次數分析

問題描述

三根柱子 A、B、C。A 柱自下而上疊放 N 個圓盤（大在下、小在上）。規則：

1. 每次僅能移動一個圓盤。
2. 大盤不可置於小盤之上。

目標：將所有圓盤從 A 移至 C，求移動步驟與最少次數。

遞歸思維拆解

將問題分解為三步：

1. 將最上方 N-1 個盤從 A 借助 C 移至 B。
2. 將第 N 個（最大）盤從 A 移至 C。
3. 將 N-1 個盤從 B 借助 A 移至 C。

基礎情況：N=1 時直接移動。

Java 實作

package algorithm;

public class Hanoi {
    private static int moveCount = 0;

    public static void main(String[] args) {
        int n = 3; // 圓盤數
        System.out.println("=== 漢諾塔 N=" + n + " 移動步驟 ===");
        solve(n, 'A', 'B', 'C');
        System.out.println("總移動次數：" + moveCount);
        System.out.println("理論最少次數 (2^n - 1)：" + ((1 << n) - 1));
    }

    /**
     * @param n 圓盤數
     * @param from 起始柱
     * @param aux 輔助柱
     * @param to 目標柱
     */
    public static void solve(int n, char from, char aux, char to) {
        if (n == 1) {
            System.out.printf("第 %d 步：%c -> %c%n", ++moveCount, from, to);
            return;
        }
        solve(n - 1, from, to, aux); // 步驟 1
        solve(1, from, aux, to);     // 步驟 2
        solve(n - 1, aux, from, to); // 步驟 3
    }
}

執行輸出 (N=3)

=== 漢諾塔 N=3 移動步驟 ===
第 1 步：A -> C
第 2 步：A -> B
第 3 步：C -> B
第 4 步：A -> C
第 5 步：B -> A
第 6 步：B -> C
第 7 步：A -> C
總移動次數：7
理論最少次數 (2^n - 1)：7

數學分析

• 遞迴關係：T(n) = 2*T(n-1) + 1, T(1)=1
• 解得：T(n) = 2^n - 1
• 時間複雜度：O(2^n)，空間複雜度：O(n) 遞迴堆疊深度。

非遞迴替代方案（迭代法）

漢諾塔存在迭代規律：

1. 最小盤每隔一步移動一次，方向固定（N 奇數：A→C→B→A...；N 偶數：A→B→C→A...）。
2. 其餘步驟在合法移動中唯一確定。

適合無遞迴支援環境或超大 N（需大整數計數）。

總結

漢諾塔是遞迴教學的經典範例，完美展示「大問題分解為相同結構的子問題」的核心思想。理解其遞迴結構與數學歸納證明，有助於掌握分治法、樹遍歷等進階演算法。