漢諾塔問題 Java 遞歸解法與移動次數公式推導

問題描述

16 個盤子從 A 塔移至 C 塔，借助 B 塔，規則：大盤不得壓小盤，每次移一個盤。

遞歸邏輯推導

設 f(n) 為移動 n 個盤子所需最少步數。

• f(1) = 1：直接移動。
• f(2) = 3：小→B，大→C，小→C。
• f(3) = 7：前2個→B (3步)，第3個→C (1步)，前2個→C (3步)。
• 規律：f(n) = 2*f(n-1) + 1。

通項公式

f(n) = 2^n - 1
// 證明：f(1)=1=2^1-1；假設 f(k)=2^k-1，則 f(k+1)=2(2^k-1)+1=2^(k+1)-1。

16 個盤子：2^16 - 1 = 65,535 步。

Java 遞歸實現

public class HanoiTower {
    private int moveCount = 0;
    
    public void solve(int n, char from, char aux, char to) {
        if (n == 1) {
            System.out.printf("Move disk 1 from %c to %c%n", from, to);
            moveCount++;
            return;
        }
        // 將 n-1 個從 from 移到 aux（借助 to）
        solve(n - 1, from, to, aux);
        // 將第 n 個從 from 移到 to
        System.out.printf("Move disk %d from %c to %c%n", n, from, to);
        moveCount++;
        // 將 n-1 個從 aux 移到 to（借助 from）
        solve(n - 1, aux, from, to);
    }
    
    public static void main(String[] args) {
        HanoiTower hanoi = new HanoiTower();
        hanoi.solve(3, 'A', 'B', 'C'); // 演示 3 個盤子
        System.out.println("Total moves: " + hanoi.moveCount); // 7
        
        // 16 個盤子僅計算步數（不打印）
        long moves16 = (1L << 16) - 1; // 2^16 - 1
        System.out.println("16 disks moves: " + moves16); // 65535
    }
}

迭代非遞歸實現（棧模擬）

public void solveIterative(int n, char from, char aux, char to) {
    // 奇數盤：最小盤按 A→C→B→A 循環；偶數盤：A→B→C→A
    // 此處略，核心思想：用棧保存 (n, from, aux, to, state)
}

關鍵理解點

1. 分治策略：將 n 個盤問題分解為兩個 n-1 子問題 + 1 步基礎移動。
2. 參數角色輪換：遞歸調用時 from, aux, to 位置交換，體現「借助」關係變化。
3. 指數增長：2^n - 1 步數說明問題複雜度為指數級，n=64 時步數超過宇宙壽命（傳說）。

掌握遞歸分解模式 solve(n, from, aux, to) = solve(n-1, from, to, aux) + move(n) + solve(n-1, aux, from, to)，即可解決漢諾塔及同類遞歸問題。