Java 練習題：楊輝三角打印（二維數組動態構建）

題目

打印楊輝三角，行數由用戶輸入決定。

數學規律

• 第 n 行有 n 個數字（行號從 1 開始）
• 每行首尾為 1
• 中間數字 = 上一行同位置 + 上一行前一位置：C(n,k) = C(n-1,k) + C(n-1,k-1)
• 本質是二項式係數：(a+b)ⁿ 展開係數

標準解法：二維數組構建 + 打印

import java.util.Scanner;

public class YangHuiTriangle {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入打印行數 (1-20): ");
        int rows = sc.nextInt();
        
        if (rows <= 0 || rows > 20) {
            System.out.println("行數範圍 1-20");
            return;
        }
        
        // 1. 定義二維數組（行數 x 行數，下三角區有效）
        int[][] triangle = new int[rows][rows];
        
        // 2. 構建楊輝三角
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    // 首尾為 1
                    triangle[i][j] = 1;
                } else {
                    // 中間 = 左上 + 正上
                    triangle[i][j] = triangle[i-1][j] + triangle[i-1][j-1];
                }
            }
        }
        
        // 3. 格式化打印（居中對齊）
        printTriangle(triangle, rows);
    }
    
    private static void printTriangle(int[][] triangle, int rows) {
        // 計算最後一行寬度用於居中
        String lastRowStr = formatRow(triangle[rows-1], rows);
        int maxWidth = lastRowStr.length();
        
        for (int i = 0; i < rows; i++) {
            String rowStr = formatRow(triangle[i], i+1);
            // 居中：前面補空格
            int padding = (maxWidth - rowStr.length()) / 2;
            System.out.println(" ".repeat(padding) + rowStr);
        }
    }
    
    private static String formatRow(int[] row, int len) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < len; j++) {
            sb.append(String.format("%-4d", row[j])); // 寬度 4 左對齊
        }
        return sb.toString();
    }
}

運行示例（輸入 6）

       1   
      1   1   
     1   2   1   
    1   3   3   1   
   1   4   6   4   1   
  1   5  10  10   5   1   

優化版：一維數組滾動覆蓋（空間 O(n)）

public class YangHuiOptimized {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt();
        
        int[] row = new int[rows]; // 只需一維數組
        
        for (int i = 0; i < rows; i++) {
            // 從右向左更新，避免覆蓋前一值
            for (int j = i; j >= 0; j--) {
                if (j == 0 || j == i) {
                    row[j] = 1;
                } else {
                    row[j] = row[j] + row[j-1]; // 當前值(上一行同列) + 左側值(上一行前列)
                }
            }
            // 打印當前行
            printRow(row, i+1, rows);
        }
    }
    
    private static void printRow(int[] row, int len, int totalRows) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < len; j++) {
            sb.append(String.format("%-4d", row[j]));
        }
        String rowStr = sb.toString();
        // 簡單居中
        System.out.println(" ".repeat((totalRows - len) * 2) + rowStr);
    }
}

進階：BigInteger 支持大行數（>30 行 int 溢出）

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class YangHuiBigInteger {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt();
        
        List row = new ArrayList<>();
        
        for (int i = 0; i < rows; i++) {
            // 從右向左構建
            for (int j = i; j >= 0; j--) {
                if (j == 0 || j == i) {
                    if (row.size() <= j) row.add(BigInteger.ONE);
                    else row.set(j, BigInteger.ONE);
                } else {
                    BigInteger val = row.get(j).add(row.get(j-1));
                    if (row.size() <= j) row.add(val);
                    else row.set(j, val);
                }
            }
            // 打印
            System.out.println(row.subList(0, i+1));
        }
    }
}

面試擴展題

1. 求第 n 行第 k 個數：直接計算組合數 C(n-1, k-1)，使用乘除法避免階乘溢出
2. 楊輝三角性質：每行和 = 2ⁿ⁻¹；對稱性；與二項式定理、組合數學、概率論緊密相關
3. 內存優化：一維數組逆序更新是經典技巧，同樣適用於 01 背包、編輯距離等 DP 優化
4. 異形三角形：萊布尼茨三角形、帕斯卡三角形模 p 變體（賽爾賓斯基三角形）

組合數直接計算公式（O(k) 時間 O(1) 空間）

public static long combination(int n, int k) {
    if (k > n - k) k = n - k; // 優化：C(n,k) = C(n,n-k)
    long result = 1;
    for (int i = 1; i <= k; i++) {
        result = result * (n - k + i) / i; // 先乘後除，保證整除
    }
    return result;
}

// 用法：第 5 行第 3 個數（索引從 1）= C(4,2) = 6
System.out.println(combination(4, 2)); // 6

核心收穫：楊輝三角是二維動態規劃入門經典。掌握二維構建→一維滾動優化→組合數直接計算三個層次，並理解「逆序更新」避免狀態覆蓋的通用技巧，可融會貫通於背包問題、LCS、編輯距離等 DP 優化。