帕斯卡三角形（Pascal’s Triangle）

帕斯卡三角形是一个经典的数学图形，由二项式系数组成，具有许多有趣的数学性质。

基本定义

帕斯卡三角形是一个无限的数字三角形，每个数字等于它上方两个数字之和。通常，三角形的顶点（第0行）是数字1。

结构示例

行0:        1
行1:      1   1
行2:    1   2   1
行3:  1   3   3   1
行4:1   4   6   4   1
行5:1   5  10  10   5   1
...

数学性质

1. 二项式系数：第n行的第k个数字等于组合数C(n,k) = n! / (k!(n-k)!)
2. 对称性：三角形关于中心线对称
3. 斐波那契数列：通过对角线相加可以得到斐波那契数列
4. 幂和：第n行的数字是(1+x)^n的展开系数
5. 递推关系：每个数字等于它上方两个数字之和

JavaScript实现帕斯卡三角形

方法1：二维数组实现

function generatePascalTriangle(numRows) {
    const triangle = [];
    
    for (let i = 0; i < numRows; i++) {
        triangle[i] = [];
        triangle[i][0] = 1; // 每行第一个元素为1
        
        for (let j = 1; j < i; j++) {
            // 当前元素等于上方两个元素之和
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
        
        if (i > 0) {
            triangle[i][i] = 1; // 每行最后一个元素为1
        }
    }
    
    return triangle;
}

// 使用示例
const triangle = generatePascalTriangle(5);
console.log(triangle);
/*
输出:
[
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1]
]
*/

方法2：生成器实现（惰性计算）

function* pascalTriangleGenerator() {
    let row = [1];
    while (true) {
        yield row;
        
        const nextRow = [1];
        for (let i = 0; i < row.length - 1; i++) {
            nextRow.push(row[i] + row[i + 1]);
        }
        nextRow.push(1);
        
        row = nextRow;
    }
}

// 使用示例
const pascal = pascalTriangleGenerator();

// 打印前5行
for (let i = 0; i < 5; i++) {
    console.log(pascal.next().value);
}

/*
输出:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
*/

方法3：特定行实现（优化空间）

function getPascalRow(rowIndex) {
    const row = [1];
    
    for (let i = 1; i <= rowIndex; i++) {
        // 使用从后向前更新避免覆盖
        for (let j = row.length - 1; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
        row.push(1);
    }
    
    return row;
}

// 使用示例
console.log(getPascalRow(4)); // 输出: [1, 4, 6, 4, 1]

方法4：组合数计算实现

function combination(n, k) {
    if (k > n - k) k = n - k; // 利用对称性减少计算量
    let result = 1;
    
    for (let i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    
    return result;
}

function generatePascalTriangleCombinations(numRows) {
    const triangle = [];
    
    for (let i = 0; i < numRows; i++) {
        const row = [];
        for (let j = 0; j <= i; j++) {
            row.push(combination(i, j));
        }
        triangle.push(row);
    }
    
    return triangle;
}

// 使用示例
const triangle = generatePascalTriangleCombinations(5);
console.log(triangle);
/*
输出:
[
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1]
]
*/

帕斯卡三角形的应用

1. 组合数学：计算组合数
2. 概率论：二项分布
3. 多项式展开：(a+b)^n的系数
4. 路径计数：网格中的路径数
5. 数据结构：某些数据结构的实现基础

帕斯卡三角形的可视化

function printPascalTriangle(numRows) {
    const triangle = generatePascalTriangle(numRows);
    const maxDigits = triangle[numRows - 1].toString().length;
    
    for (let i = 0; i < numRows; i++) {
        const spaces = ' '.repeat((maxDigits * (numRows - i - 1)) / 2);
        const row = triangle[i].map(num => num.toString().padStart(maxDigits)).join(' ');
        console.log(spaces + row);
    }
}

// 使用示例
printPascalTriangle(5);
/*
输出:
        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1
*/

性能分析

总结

帕斯卡三角形是一个数学上非常重要的结构，具有丰富的性质和应用。在JavaScript中实现帕斯卡三角形时，可以根据具体需求选择不同的实现方式：

1. 需要完整三角形时，使用二维数组实现
2. 需要惰性计算或无限生成时，使用生成器实现
3. 只需要特定行时，使用特定行实现
4. 需要精确数学计算时，使用组合数实现

帕斯卡三角形不仅是一个数学概念，也是算法设计中的重要工具，掌握它的实现和应用对于提升编程能力很有帮助。