L8.5 - 数学专题：杨辉三角的编程妙用（拓展）

一、杨辉三角是什么？

1. 数字金字塔

外观特点：
每一行数字左右对称，像金字塔一样逐层增加
第n行有n个数字，首尾都是1，中间数字=上层两数之和

示例（前5行）：

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

二、用C++生成杨辉三角

1. 二维数组生成法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> generatePascal(int n) {
    vector<vector<int>> triangle(n);
    for(int i=0; i<n; i++) {
        triangle[i].resize(i+1, 1); // 每行初始化为1
        
        // 从第三行开始计算中间数
        for(int j=1; j<i; j++) { 
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    return triangle;
}

// 打印结果
int main() {
    auto tri = generatePascal(5);
    for(auto& row : tri) {
        for(int num : row) 
            cout << num << " ";
        cout << endl;
    }
}

三、杨辉三角的编程妙用

1. 快速查组合数

秘密：第n行第k个数 = 从(n-1)个物品选(k-1)个的组合数 C(n-1, k-1)

应用示例：查C(4,2)=6

1
2
auto tri = generatePascal(5); // 生成前5行
cout << "C(4,2) = " << tri[4][2]; // 输出第5行第3个数 → 6

2. 多项式展开系数

二项式定理：
(a + b) ^ n的展开系数 = 杨辉三角第(n + 1)行

示例：
(a + b) ^ 3 = 1a³ + 3a²b + 3ab² + 1b³
对应杨辉三角第4行：1 3 3 1

四、趣味编程挑战

1. 打印圣诞树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void printChristmasTree(int height) {
    auto tri = generatePascal(height);
    for(auto& row : tri) {
        // 添加空格形成树形
        cout << string(height - row.size(), ' '); 
        for(int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

// 调用示例
printChristmasTree(5);

2. 数字金字塔游戏

1
2
3
4
5
6
7
8
9
10
// 判断用户输入的金字塔是否正确
bool checkPascal(vector<vector<int>> userInput) {
    for(int i=2; i<userInput.size(); i++) {
        for(int j=1; j<i; j++) {
            if(userInput[i][j] != userInput[i-1][j-1]+userInput[i-1][j])
                return false;
        }
    }
    return true;
}

五、核心知识点总结

内容 关键点 编程应用
生成方法 二维数组 + 递推公式 理解数组嵌套
组合数查询 行数-1，列数-1对应C(n,k) 快速数学计算
对称性应用 只计算前半部分 优化程序效率
动态规划思想 当前状态依赖前一个状态 算法思维训练