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实现杨辉三角的完整思路。 “`