Java 實現漢諾塔算法：可視化遞歸移動過程完整代碼

漢諾塔問題介紹

漢諾塔是經典的遞歸算法問題：

• 目標：將第一根柱子上的所有盤子，借助第二根柱子，移動到第三根柱子
• 規則：一次只能移動一個盤子；大盤子不能放在小盤子上面
• 最優解步數：2^n - 1 (n 為盤子數量)

遞歸核心邏輯

移動 n 個盤子從 A 移到 C（借助 B）：

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

完整可視化實現代碼

import java.util.ArrayList;
import java.util.List;

public class HanoiTowerVisualization {
    public static int tiers = 4; // 盤子層數
    
    // 三根柱子，用 List 模擬棧結構（索引 0 為底部）
    private static List<String> peg1 = new ArrayList<>();
    private static List<String> peg2 = new ArrayList<>();
    private static List<String> peg3 = new ArrayList<>();
    
    // 柱子映射，用於打印時確定編號
    private static List<String>[] pegs = {peg1, peg2, peg3};

    public static void main(String[] args) {
        // 1. 初始化：在柱子1上放置盤子
        initPeg(peg1, tiers);
        
        System.out.println("=== 初始狀態 ===");
        printPegs();
        
        // 2. 執行漢諾塔算法
        hanoi(tiers, peg1, peg2, peg3);
        
        System.out.println("\n=== 最終狀態 ===");
        printPegs();
    }

    /**
     * 初始化柱子盤子
     * 盤子用 "^" 字符表示，寬度為 2*tiers-1，居中對齊
     */
    private static void initPeg(List<String> peg, int tiers) {
        StringBuilder builder = new StringBuilder();
        
        // 從底層到頂層（i 從 tiers 遞減到 1）
        for (int i = tiers; i > 0; i--) {
            builder.setLength(0); // 清空
            
            // 左側填充空格：(tiers - i) 個
            for (int k = 0; k < tiers - i; k++) builder.append(" ");
            
            // 盤子主體：2*i-1 寬度，奇數位放 "^"，偶數位放空格
            for (int j = 1; j <= 2 * i - 1; j++) {
                builder.append(j % 2 == 1 ? "^" : " ");
            }
            
            // 右側填充空格
            for (int k = 0; k < tiers - i; k++) builder.append(" ");
            
            peg.add(builder.toString());
        }
    }

    /**
     * 打印三根柱子當前狀態
     */
    private static void printPegs() {
        // 計算最大高度
        int maxHeight = Math.max(peg1.size(), Math.max(peg2.size(), peg3.size()));
        
        // 空層佔位符
        StringBuilder empty = new StringBuilder();
        empty.append("|");
        for (int i = 0; i < 2 * tiers - 1; i++) empty.append(" ");
        empty.append("|\t");
        
        // 從頂層向下打印（索引 maxHeight-1 到 0）
        for (int level = maxHeight - 1; level >= 0; level--) {
            for (int p = 0; p < 3; p++) {
                List<String> peg = pegs[p];
                if (level < peg.size()) {
                    System.out.print("|" + peg.get(level) + "|\t");
                } else {
                    System.out.print(empty);
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 漢諾塔遞歸核心方法
     * @param n 要移動的盤子數
     * @param from 源柱子
     * @param aux 輔助柱子
     * @param to 目標柱子
     */
    public static void hanoi(int n, List<String> from, List<String> aux, List<String> to) {
        if (n == 1) {
            moveTopDisk(from, to);
            return;
        }
        
        // 步驟1：將 n-1 個盤子從 from 移到 aux（借助 to）
        hanoi(n - 1, from, to, aux);
        
        // 步驟2：將第 n 個盤子從 from 移到 to
        moveTopDisk(from, to);
        
        // 步驟3：將 n-1 個盤子從 aux 移到 to（借助 from）
        hanoi(n - 1, aux, from, to);
    }

    /**
     * 移動頂部盤子並打印過程
     */
    private static void moveTopDisk(List<String> from, List<String> to) {
        // 彈出源柱子頂部盤子，壓入目標柱子
        String disk = from.remove(from.size() - 1);
        to.add(disk);
        
        // 確定柱子編號
        int fromNum = 0, toNum = 0;
        for (int i = 0; i < pegs.length; i++) {
            if (pegs[i] == from) fromNum = i + 1;
            if (pegs[i] == to) toNum = i + 1;
        }
        
        System.out.println("********** 移動步驟 **********");
        System.out.println("從 " + fromNum + " 號柱子 → " + toNum + " 號柱子");
        printPegs();
    }
}

運行效果示例（4層）

=== 初始狀態 ===
|      ^      |	|           |	|           |
|     ^ ^     |	|           |	|           |
|    ^ ^ ^    |	|           |	|           |
|   ^ ^ ^ ^   |	|           |	|           |

********** 移動步驟 **********
從 1 號柱子 → 2 號柱子
|           |	|      ^      |	|           |
|     ^ ^     |	|           |	|           |
|    ^ ^ ^    |	|           |	|           |
|   ^ ^ ^ ^   |	|           |	|           |
...

關鍵點解析

算法複雜度

• 時間複雜度：O(2^n) - 必須執行 2^n - 1 次移動
• 空間複雜度：O(n) - 遞歸調用棧深度

擴展思路

• 增加動畫延遲：Thread.sleep(500) 觀察每一步
• 統計移動次數：添加計數器驗證 2^n - 1 公式
• GUI 版本：使用 Swing/JavaFX 繪制圖形化界面
• 四柱漢諾塔：Frame-Stewart 算法優化

總結

漢諾塔是理解遞歸思想的經典案例。通過可視化輸出，可以直觀看到「大問題分解為子問題」的遞歸過程。代碼結構清晰，分離了算法邏輯與顯示邏輯，便於擴展和教學演示。