Java怎么實現楊輝三角

# Java怎么實現楊輝三角

## 一、楊輝三角簡介

楊輝三角（Pascal's Triangle）是二項式系數在三角形中的幾何排列，最早由中國南宋數學家楊輝在《詳解九章算法》中提出。它具有以下特征：

1. 第n行有n個數字
2. 每行首尾數字均為1
3. 從第三行開始，每個數等于它上方兩數之和

數學表達式為：C(n,k) = C(n-1,k-1) + C(n-1,k)

## 二、基礎實現方法

### 2.1 二維數組法

```java
public class YangHuiTriangle {
    public static void main(String[] args) {
        int rows = 10;
        int[][] triangle = new int[rows][];
        
        // 初始化每一行
        for (int i = 0; i < rows; i++) {
            triangle[i] = new int[i + 1];
            triangle[i][0] = 1;  // 行首為1
            triangle[i][i] = 1;   // 行尾為1
            
            // 計算中間元素
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }
        
        // 打印結果
        printTriangle(triangle);
    }
    
    private static void printTriangle(int[][] triangle) {
        for (int[] row : triangle) {
            for (int num : row) {
                System.out.printf("%4d", num);
            }
            System.out.println();
        }
    }
}

2.2 一維數組優化

public class YangHuiTriangleOptimized {
    public static void main(String[] args) {
        int rows = 10;
        int[] currentRow = new int[rows];
        
        for (int i = 0; i < rows; i++) {
            currentRow[i] = 1;  // 行尾置1
            
            // 從后往前計算避免覆蓋
            for (int j = i-1; j > 0; j--) {
                currentRow[j] += currentRow[j-1];
            }
            
            // 打印當前行
            for (int j = 0; j <= i; j++) {
                System.out.printf("%4d", currentRow[j]);
            }
            System.out.println();
        }
    }
}

三、進階實現方案

3.1 遞歸實現

public class YangHuiRecursive {
    public static void main(String[] args) {
        int rows = 10;
        for (int i = 0; i < rows; i++) {
            // 打印前導空格實現居中對齊
            printSpaces(2 * (rows - i - 1));
            
            for (int j = 0; j <= i; j++) {
                System.out.printf("%4d", calculate(i, j));
            }
            System.out.println();
        }
    }
    
    private static int calculate(int row, int col) {
        if (col == 0 || col == row) {
            return 1;
        }
        return calculate(row - 1, col - 1) + calculate(row - 1, col);
    }
    
    private static void printSpaces(int count) {
        for (int i = 0; i < count; i++) {
            System.out.print(" ");
        }
    }
}

3.2 使用BigInteger處理大數

import java.math.BigInteger;

public class YangHuiBigInteger {
    public static void main(String[] args) {
        int rows = 30;
        BigInteger[][] triangle = new BigInteger[rows][];
        
        for (int i = 0; i < rows; i++) {
            triangle[i] = new BigInteger[i + 1];
            triangle[i][0] = BigInteger.ONE;
            triangle[i][i] = BigInteger.ONE;
            
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1].add(triangle[i-1][j]);
            }
        }
        
        printBigTriangle(triangle);
    }
    
    private static void printBigTriangle(BigInteger[][] triangle) {
        int maxLength = triangle[triangle.length-1][triangle.length/2].toString().length();
        
        for (int i = 0; i < triangle.length; i++) {
            // 居中對齊
            System.out.print(" ".repeat((triangle.length - i - 1) * (maxLength + 1) / 2));
            
            for (BigInteger num : triangle[i]) {
                System.out.printf("%" + (maxLength + 1) + "s", num);
            }
            System.out.println();
        }
    }
}

四、性能對比與優化建議

4.1 時間復雜度分析

4.2 優化建議

1. 緩存計算結果：對于遞歸方法，可以使用備忘錄模式存儲已計算結果
2. 并行計算：對于超大三角，可以采用并行流處理
3. 格式化優化：根據數字位數動態調整輸出格式

五、實際應用場景

1. 組合數學：計算組合數C(n,k)
2. 概率統計：二項分布計算
3. 代數運算：多項式展開系數
4. 算法題目：常見編程面試題

六、擴展思考

1. 斜線方向求和：對角線上的數字具有斐波那契數列等特性
2. 三維楊輝三角：可以擴展到立體空間形成楊輝四面體
3. 質數標記：標記三角中的質數會出現有趣的圖案

七、完整示例代碼

import java.util.Scanner;

public class YangHuiComplete {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("請輸入要打印的行數：");
        int rows = scanner.nextInt();
        
        printYangHui(rows);
        printYangHuiFormatted(rows);
    }
    
    // 基礎打印方法
    public static void printYangHui(int rows) {
        int[][] triangle = new int[rows][];
        for (int i = 0; i < rows; i++) {
            triangle[i] = new int[i + 1];
            triangle[i][0] = triangle[i][i] = 1;
            
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }
        
        System.out.println("\n基礎楊輝三角：");
        for (int[] row : triangle) {
            for (int num : row) {
                System.out.printf("%6d", num);
            }
            System.out.println();
        }
    }
    
    // 帶格式化的美觀打印
    public static void printYangHuiFormatted(int rows) {
        int[][] triangle = new int[rows][];
        int maxNum = 0;
        
        // 先計算獲取最大數字用于格式化
        for (int i = 0; i < rows; i++) {
            triangle[i] = new int[i + 1];
            triangle[i][0] = triangle[i][i] = 1;
            
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                if (triangle[i][j] > maxNum) {
                    maxNum = triangle[i][j];
                }
            }
        }
        
        int numWidth = String.valueOf(maxNum).length() + 2;
        System.out.println("\n格式化楊輝三角：");
        
        for (int i = 0; i < rows; i++) {
            // 居中對齊
            System.out.print(" ".repeat(numWidth * (rows - i - 1) / 2));
            
            for (int num : triangle[i]) {
                System.out.printf("%" + numWidth + "d", num);
            }
            System.out.println();
        }
    }
}

通過本文介紹的多種實現方法，讀者可以根據不同場景需求選擇合適的實現方案。從基礎的二維數組到優化的遞歸算法，再到處理大數的方案，展示了Java實現楊輝三角的完整思路。 “`