L8_03 杨辉三角

一、杨辉三角的定义

1.1 杨辉三角概述

杨辉三角（又称帕斯卡三角）是一个由数字排列成的三角形数阵。

1.2 杨辉三角的特点

• 第 n 行有 n 个元素
• 每行首尾元素都是 1
• 中间元素是上一行相邻两个元素之和
• 第 n 行第 k 个元素等于组合数 C(n-1, k-1)

1.3 杨辉三角示例

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
  1 6 15 20 15 6 1

二、杨辉三角的实现

2.1 生成杨辉三角

vector<vector<int>> generateYanghui(int numRows) {
    vector<vector<int>> triangle;
    
    for (int i = 0; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        
        for (int j = 1; j < i; j++) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
        
        triangle.push_back(row);
    }
    
    return triangle;
}

2.2 输出杨辉三角

void printYanghui(int numRows) {
    auto triangle = generateYanghui(numRows);
    
    for (int i = 0; i < numRows; i++) {
        // 打印空格
        for (int j = 0; j < numRows - i - 1; j++) {
            cout << " ";
        }
        
        // 打印数字
        for (int num : triangle[i]) {
            cout << num << " ";
        }
        cout << endl;
    }
}

2.3 获取第k行

vector<int> getRow(int rowIndex) {
    vector<int> row(rowIndex + 1, 1);
    
    for (int i = 1; i <= rowIndex; i++) {
        for (int j = i - 1; j > 0; j--) {
            row[j] = row[j] + row[j - 1];
        }
    }
    
    return row;
}

三、杨辉三角的性质

3.1 组合数性质

第 n 行第 k 个元素（从0开始）等于 C(n, k)

int getCombination(int n, int k) {
    vector<int> row = getRow(n);
    return row[k];
}

3.2 数字和性质

第 n 行所有数字之和等于 2^n

int getRowSum(int n) {
    return 1 << n; // 2^n
}

3.3 对称性

第 n 行第 k 个元素等于第 n 行第 n-k 个元素

bool isSymmetric(int n, int k1, int k2) {
    return k1 + k2 == n;
}

3.4 斜行和性质

从左上方到右下方的斜行和构成斐波那契数列

// 第k条斜行的和
int diagonalSum(int k) {
    // 第k条斜行的和 = Fibonacci(k+1)
    int a = 1, b = 1;
    for (int i = 2; i <= k + 1; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

四、杨辉三角的应用

4.1 二项式展开

// (a + b)^n 的展开系数就是杨辉三角第n行
vector<int> binomialCoefficients(int n) {
    return getRow(n);
}

4.2 路径计数

// 从(0,0)到(m,n)的路径数 = C(m+n, m)
long long countPaths(int m, int n) {
    return combination(m + n, m);
}

long long combination(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    k = min(k, n - k);
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

4.3 概率计算

// 计算二项分布概率
// P(X=k) = C(n, k) * p^k * (1-p)^(n-k)
double binomialProbability(int n, int k, double p) {
    long long c = combination(n, k);
    double prob = c * pow(p, k) * pow(1 - p, n - k);
    return prob;
}

// 计算二项分布累积概率
// P(X <= k) = Σ(C(n, i) * p^i * (1-p)^(n-i)) for i = 0 to k
double binomialCumulative(int n, int k, double p) {
    double result = 0;
    for (int i = 0; i <= k; i++) {
        result += binomialProbability(n, i, p);
    }
    return result;
}

4.4 整数分拆

// 利用杨辉三角计算整数分拆数
// p(n) = 不考虑顺序将n拆分成若干正整数之和的方法数

// 生成分拆数表
vector<int> generatePartitionNumbers(int maxN) {
    vector<int> p(maxN + 1, 0);
    p[0] = 1;
    
    for (int i = 1; i <= maxN; i++) {
        for (int j = i; j <= maxN; j++) {
            p[j] += p[j - i];
        }
    }
    
    return p;
}

五、杨辉三角的扩展

5.1 广义杨辉三角

// 广义杨辉三角，每个元素是上方k个元素之和
vector<vector<int>> generalizedYanghui(int numRows, int k) {
    vector<vector<int>> triangle;
    
    for (int i = 0; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        
        for (int j = 1; j < i; j++) {
            int sum = 0;
            for (int m = max(0, j - k + 1); m <= j; m++) {
                if (i - 1 >= 0 && m < triangle[i - 1].size()) {
                    sum += triangle[i - 1][m];
                }
            }
            row[j] = sum;
        }
        
        triangle.push_back(row);
    }
    
    return triangle;
}

5.2 模运算下的杨辉三角

// 计算模m下的杨辉三角
vector<vector<int>> modularYanghui(int numRows, int mod) {
    vector<vector<int>> triangle;
    
    for (int i = 0; i < numRows; i++) {
        vector<int> row(i + 1, 1);
        
        for (int j = 1; j < i; j++) {
            row[j] = (triangle[i - 1][j - 1] + triangle[i - 1][j]) % mod;
        }
        
        triangle.push_back(row);
    }
    
    return triangle;
}

5.3 大整数杨辉三角

// 使用高精度计算杨辉三角
vector<vector<string>> bigIntYanghui(int numRows) {
    vector<vector<string>> triangle;
    
    for (int i = 0; i < numRows; i++) {
        vector<string> row(i + 1, "1");
        
        for (int j = 1; j < i; j++) {
            row[j] = addStrings(triangle[i - 1][j - 1], triangle[i - 1][j]);
        }
        
        triangle.push_back(row);
    }
    
    return triangle;
}

string addStrings(string num1, string num2) {
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    
    string result;
    int carry = 0;
    
    for (int i = 0; i < max(num1.size(), num2.size()); i++) {
        int digit1 = i < num1.size() ? num1[i] - '0' : 0;
        int digit2 = i < num2.size() ? num2[i] - '0' : 0;
        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        result.push_back(sum % 10 + '0');
    }
    
    if (carry) result.push_back(carry + '0');
    reverse(result.begin(), result.end());
    
    return result;
}