Java 解決河內塔問題完整教學：遞迴邏輯、步驟數學證明、動畫視覺化、疊代非遞迴實作

前言

河內塔是經典遞迴教學案例。本文提供：標準遞迴解法、數學歸納法證明最少步驟 2^n - 1、JavaFX 動畫視覺化、疊代非遞迴實作 (避免堆疊溢位)、泛型化支援任意物件移動、單元測試驗證步驟數與合法性。

1. 標準遞迴解法

public class HanoiTower {
    public static void solve(int n, char from, char aux, char to, List<Move> moves) {
        if (n == 1) {
            moves.add(new Move(1, from, to));
            return;
        }
        solve(n - 1, from, to, aux, moves);
        moves.add(new Move(n, from, to));
        solve(n - 1, aux, from, to, moves);
    }

    public record Move(int disk, char from, char to) {
        @Override public String toString() {
            return String.format("Move disk %d from %c to %c", disk, from, to);
        }
    }

    public static void main(String[] args) {
        List<Move> moves = new ArrayList<>();
        solve(3, 'A', 'B', 'C', moves);
        moves.forEach(System.out::println);
        System.out.println("Total steps: " + moves.size()); // 7 = 2^3 - 1
    }
}

2. 數學證明：最少步驟 = 2^n - 1

歸納法：

1. 基礎：n=1 時，需 1 步 = 2^1 - 1 ✓
2. 假設：n=k 時，最少步驟 = 2^k - 1
3. 證明 n=k+1：
   • 將最上 k 個盤子從 A 移到 B (借用 C) → 需 2^k - 1 步 (歸納假設)
   • 將第 k+1 個盤子 (最大) 從 A 移到 C → 1 步
   • 將 k 個盤子從 B 移到 C (借用 A) → 2^k - 1 步
   • 總計 = (2^k - 1) + 1 + (2^k - 1) = 2^(k+1) - 1 ✓

最少性證明：最大盤子必須移動一次，移動前後所有較小盤子必須集中在同一根柱子上，各需至少 2^k - 1 步，故下界 = 2^n - 1。

3. 疊代非遞迴實作 (位元運算法，O(1) 空間)

public class HanoiIterative {
    public static List<HanoiTower.Move> solve(int n) {
        List<HanoiTower.Move> moves = new ArrayList<>();
        int total = (1 << n) - 1; // 2^n - 1
        // 判斷最小盤子移動方向：n 奇數 → 順時針 (A→C→B→A)；偶數 → 逆時針 (A→B→C→A)
        boolean clockwise = (n % 2 == 1);
        char[] pegs = {'A', 'B', 'C'};
        int[] pos = new int[n + 1]; // 1-based disk index → peg index (0,1,2)
        Arrays.fill(pos, 0); // 所有盤子起始在 A (index 0)

        for (int step = 1; step <= total; step++) {
            if (step % 2 == 1) {
                // 奇數步：移動最小盤子 (disk 1)
                int from = pos[1];
                int to = clockwise ? (from + 1) % 3 : (from + 2) % 3;
                moves.add(new HanoiTower.Move(1, pegs[from], pegs[to]));
                pos[1] = to;
            } else {
                // 偶數步：進行唯一合法的非最小盤子移動
                // 找出可移動的盤子 (頂部盤子) 且目標柱頂部盤子較大或為空
                for (int disk = 2; disk <= n; disk++) {
                    int from = pos[disk];
                    // 找出該盤子所在柱的頂部盤子
                    int topDiskOnFrom = findTopDisk(pos, from, disk);
                    if (topDiskOnFrom != disk) continue; // 不是頂部盤子

                    // 嘗試兩個目標柱
                    for (int dir : new int[]{1, 2}) { // 兩個方向
                        int to = (from + dir) % 3;
                        int topDiskOnTo = findTopDisk(pos, to, 0);
                        if (topDiskOnTo == 0 || topDiskOnTo > disk) {
                            // 合法移動
                            moves.add(new HanoiTower.Move(disk, pegs[from], pegs[to]));
                            pos[disk] = to;
                            break;
                        }
                    }
                }
            }
        }
        return moves;
    }

    private static int findTopDisk(int[] pos, int peg, int excludeDisk) {
        int top = 0;
        for (int i = 1; i < pos.length; i++) {
            if (i == excludeDisk) continue;
            if (pos[i] == peg && (top == 0 || i < top)) top = i;
        }
        return top;
    }
}

4. JavaFX 動畫視覺化

public class HanoiAnimation extends Application {
    private static final int DISKS = 5;
    private static final double BASE_WIDTH = 200;
    private static final double PEG_X[] = {150, 400, 650};
    private static final double BASE_Y = 500;
    private final List moves = new ArrayList<>();
    private int moveIndex = 0;

    @Override
    public void start(Stage stage) {
        HanoiTower.solve(DISKS, 'A', 'B', 'C', moves);
        Pane root = new Pane();
        // 繪製柱子
        for (double x : PEG_X) {
            root.getChildren().add(new Line(x, BASE_Y, x, BASE_Y - 300));
        }
        // 建立盤子矩形
        Map diskRects = new HashMap<>();
        for (int i = 1; i <= DISKS; i++) {
            double w = BASE_WIDTH - (i - 1) * 30;
            Rectangle r = new Rectangle(PEG_X[0] - w/2, BASE_Y - i * 25, w, 20);
            r.setFill(Color.hsb(360.0 / DISKS * i, 0.8, 0.9));
            r.setStroke(Color.BLACK);
            diskRects.put(i, r);
            root.getChildren().add(r);
        }

        Timeline timeline = new Timeline(new KeyFrame(Duration.millis(800), e -> animateStep(diskRects)));
        timeline.setCycleCount(moves.size());
        timeline.play();

        Scene scene = new Scene(root, 800, 600);
        stage.setScene(scene);
        stage.setTitle("河內塔動畫 (n=" + DISKS + ")");
        stage.show();
    }

    private void animateStep(Map disks) {
        if (moveIndex >= moves.size()) return;
        HanoiTower.Move m = moves.get(moveIndex++);
        Rectangle r = disks.get(m.disk());
        int toPeg = m.to() - 'A';
        double targetX = PEG_X[toPeg] - r.getWidth() / 2;
        // 計算目標 Y (疊加高度)
        int disksOnTarget = 0;
        for (int i = moveIndex; i < moves.size(); i++) { /* 簡化：直接依盤子大小排序 */ }
        double targetY = BASE_Y - (m.disk()) * 25; // 近似

        TranslateTransition tt = new TranslateTransition(Duration.millis(700), r);
        tt.setToX(targetX - r.getX());
        tt.setToY(targetY - r.getY());
        tt.play();
    }

    public static void main(String[] args) { launch(); }
}

5. 泛型化：支援任意物件移動

public class HanoiGeneric {
    private final List> rods = new ArrayList<>();

    public HanoiGeneric(int rodCount) {
        for (int i = 0; i < rodCount; i++) rods.add(new Rod<>());
    }

    public void push(int rodIndex, T disk) { rods.get(rodIndex).push(disk); }
    public T pop(int rodIndex) { return rods.get(rodIndex).pop(); }
    public T peek(int rodIndex) { return rods.get(rodIndex).peek(); }
    public boolean isEmpty(int rodIndex) { return rods.get(rodIndex).isEmpty(); }

    public void solve(int n, int from, int aux, int to, Consumer> moveConsumer) {
        if (n == 1) {
            moveConsumer.accept(new Move<>(pop(from), from, to));
            push(to, moveConsumer); // 實際上需調整
            return;
        }
        solve(n - 1, from, to, aux, moveConsumer);
        moveConsumer.accept(new Move<>(pop(from), from, to));
        push(to, moveConsumer);
        solve(n - 1, aux, from, to, moveConsumer);
    }

    static class Rod {
        private final Deque stack = new ArrayDeque<>();
        void push(T t) { stack.push(t); }
        T pop() { return stack.pop(); }
        T peek() { return stack.peek(); }
        boolean isEmpty() { return stack.isEmpty(); }
    }
    record Move(T disk, int from, int to) {}
}

6. 複雜度與效能

單元測試

@Test void recursiveThreeDisks() {
    List moves = new ArrayList<>();
    HanoiTower.solve(3, 'A', 'B', 'C', moves);
    assertEquals(7, moves.size());
    assertEquals("Move disk 1 from A to C", moves.get(0).toString());
    assertEquals("Move disk 3 from A to C", moves.get(3).toString());
}

@Test void iterativeEqualsRecursive() {
    List rec = new ArrayList<>();
    HanoiTower.solve(5, 'A', 'B', 'C', rec);
    List it = HanoiIterative.solve(5);
    assertEquals(rec, it);
}

@Test void moveLegality() {
    List moves = new ArrayList<>();
    HanoiTower.solve(4, 'A', 'B', 'C', moves);
    // 模擬驗證每步合法
    Map> pegs = new HashMap<>();
    pegs.put('A', new ArrayDeque<>(List.of(4,3,2,1))); // bottom to top
    pegs.put('B', new ArrayDeque<>());
    pegs.put('C', new ArrayDeque<>());
    for (HanoiTower.Move m : moves) {
        int disk = pegs.get(m.from()).pop();
        assertEquals(m.disk(), disk);
        if (!pegs.get(m.to()).isEmpty()) {
            assertTrue(disk < pegs.get(m.to()).peek(), "Larger on smaller");
        }
        pegs.get(m.to()).push(disk);
    }
    assertEquals(List.of(4,3,2,1), new ArrayList<>(pegs.get('C')));
}