CC++ & Algorithm

C++杨辉三角形的应用

较难7
语言版本：C++Python
概述：用杨辉三角形快速计算组合数，并了解它在二项式展开和路径计数中的实际用途。

杨辉三角形的秘密武器：算组合、解展开、数路径

杨辉三角形看起来像一堆堆叠的数字三角形，但它可不是简单的数学游戏。它能直接帮我们算出“组合数”——比如从全班30个人中选5个人去参加比赛，有多少种选法？还能帮我们展开像 (a+b)^5 这样复杂的式子，甚至数出从学校到家有多少条最短路线。这篇文章会带你揭开杨辉三角形的真面目，并教你在C++中用它解决实际问题。

1. 杨辉三角形长什么样？怎么构造的？

先回忆一下杨辉三角形的样子（行数从0开始数）：

  • 第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，中间每个数等于它左上方数字加上正上方数字（即上一行前一个位置和同一位置的和）。比如第4行第2个数字6，等于它左上方3（第3行第1个）加上正上方3（第3行第2个）。用公式表示：
y[i][j] = y[i-1][j-1] + y[i-1][j]，其中 i 是行号（从0开始），j 是列号（从0到i）。

生活比喻：想象每个数字是一个小积木，它坐在两个肩膀（左上方和正上方）上，它们一个背一个，一层层往上叠。

2. 杨辉三角形与组合数：从“选人”问题说起

组合数 C(n, k) 表示从 n 个不同的物品中选出 k 个，有多少种选法（不考虑顺序）。例如，从5个好朋友中选2个一起去吃冰淇淋，有几种选择？答案是 C(5,2) = 10。

杨辉三角形的神奇之处在于：第n行第k个数（行和列都从0开始）正好等于 C(n, k)。比如第5行（行号5）的数字是 1 5 10 10 5 1，第2列（列号2）就是10，正好等于 C(5,2)。

生活中的例子：

  • 你手上有6种不同口味的棒棒糖，想选3种送给小伙伴，选法数 = C(6,3) = 杨辉三角形第6行第3个数 = 20。
  • 老师从10个班干部中选4个去参加培训，选法数 = C(10,4) = 第10行第4个数 = 210。

为什么它刚好对应？ 因为组合数的递推公式是 C(n, k) = C(n-1, k-1) + C(n-1, k)，这和杨辉三角形的构造规则一模一样！所以杨辉三角形就像组合数的“速查表”。

3. 二项式展开：让 (a+b)^n 不再可怕

你学过 (a+b)^2 = a^2 + 2ab + b^2 吗？其中系数1,2,1正好是杨辉三角形第2行。对于任意正整数 n，(a+b)^n 展开后，每一项的系数恰好是杨辉三角形第n行的数字。

例如：

  • (a+b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3，系数1,3,3,1对应第3行。
  • (a+b)^4 = 1*a^4 + 4*a^3*b + 6*a^2*b^2 + 4*a*b^3 + 1*b^4，系数1,4,6,4,1对应第4行。

生活应用：比如你买彩票，每张彩票中奖概率是p，不中奖概率是(1-p)，买n张彩票中奖k张的概率公式里就会用到组合数，其实就是二项式展开的系数。虽然有点复杂，但杨辉三角形可以帮你快速写出这些系数。

4. 路径计数：从学校到家有多少条最短路线？

假设你从网格的左上角（学校）走到右下角（家），每次只能向右或向下走（不能向左或向上），那么有多少种不同的走法？这个问题也和杨辉三角形有关！

例如，一个3×3的网格（有4行4个交叉点），从左上角（0,0）到右下角（3,3），需要向右走3步，向下走3步，共6步。任何一条路径其实就是从这6步中选出哪3步是向右的（剩下3步向下），走法数 = C(6,3) = 20。而这个数字正好是杨辉三角形第6行第3个数。

更直观的，你可以把网格的每个交点标上数字，表示从起点到该点的路径数。你会发现，这些数字构成的三角形就是杨辉三角形！比如下面这个网格（行和列从0开始）：

起点 (0,0): 1
(0,1): 1   (1,0): 1
(0,2): 1   (1,1): 2   (2,0): 1
(0,3): 1   (1,2): 3   (2,1): 3   (3,0): 1
(1,3): 4   (2,2): 6   (3,1): 4   (4,0): 1   (终点: 3,3? 其实这里斜着看)

实际上，把网格旋转45度，就得到了杨辉三角形。所以，杨辉三角形就是路径计数的数字表。

生活中的例子：你家和学校之间的街道是网格状的，你每天只走最短路线（不绕路），那么从家到学校有多少条不同的路线？答案就是杨辉三角形中的一个数。如果网格大小是 m×n（m条横向街区，n条纵向街区），总步数 = m+n，需要选出m步向右，走法数 = C(m+n, m)。

5. C++代码：用杨辉三角形快速计算组合数

我们平时计算组合数可以用阶乘公式 C(n,k) = n! / (k! * (n-k)!)，但阶乘增长极快，n=20时 20! 就已经超过64位整数的范围了，容易溢出。而用杨辉三角形只需要整数加法，只要数组大小够大，可以算到更大的n（比如n=34以内用 int 依然安全）。

下面是一段完整的C++代码，输入n和k，输出 C(n,k) 的值。

#include <iostream>
using namespace std;

int main() {
    int n, k;               // n:总数, k:选出的个数
    cout << "请输入n和k（要求 n >= k >= 0）：";
    cin >> n >> k;

    // 创建一个二维数组，存储杨辉三角形，行数为 n+1（第0行到第n行）
    int y[100][100] = {0};  // 假设n最大为99，足够大多数题目使用

    // 构造杨辉三角形
    for (int i = 0; i <= n; i++) {      // i:当前行号
        y[i][0] = 1;                   // 每行第一个数总是1
        y[i][i] = 1;                   // 每行最后一个数总是1
        for (int j = 1; j < i; j++) {  // 中间的数用递推公式
            y[i][j] = y[i-1][j-1] + y[i-1][j];
        }
    }

    // 输出结果
    cout << "C(" << n << ", " << k << ") = " << y[n][k] << endl;

    return 0;
}

运行示例：

请输入n和k（要求 n >= k >= 0）：5 2
C(5, 2) = 10

如果你输入 n=10, k=3，会得到 C(10,3)=120。这意味着从10个同学中选3个去打扫卫生，有120种不同的分组方式。

6. 新手常犯的错误

  1. 行和列的起始编号搞混：杨辉三角形中行和列都从0开始，第0行是1。如果问你第5行第3个数，你可能会误以为第1行是“1 1”而数错。记得：第0行只有1；第1行是“1 1”；第5行是“1 5 10 10 5 1”。

  2. 忘记初始化数组：代码中 int y[100][100] = {0}; 这一步很重要，否则某些编译器会随机赋值，导致结果奇怪。= {0} 表示将整个数组初始化为0。

  3. 数组下标越界：如果n=99，数组至少需要100行100列。如果n设为100，而数组只有 [100][100]，第100行（从0开始就是第100行，对应i=100）会访问 y[100]，超出范围。所以数组大小应至少是 n+1 行 n+1 列，这里为了安全设成 100，但n最大只能到99。

  4. 输入n和k时弄反顺序：cin >> n >> k; 如果输入“3 5”但 n < k，组合数 C(3,5) 没有意义。代码没有检查，结果会得到数组中的0（因为 y[3][5] 未赋值，初始是0）。最好加上判断：

    if (k < 0 || k > n) {
    cout << "输入错误：k应在0到n之间。" << endl;
    return 1;
}

  5. 用int存储导致溢出：虽然加法比阶乘安全，但杨辉三角形数字增长也很快。int 类型最大约21亿，n=34时第17个数字（约6亿）没问题，但n=35时第17个数字已经超过21亿（约10亿？实际上C(35,17)≈4.5e9，超出int范围）。如果n可能较大，建议用 long long 类型。可以在定义数组时用 long long y[100][100] = {0};。

7. 完整可运行示例（含错误检查）

下面给出一个更健壮的版本，包括输入检查和使用 long long 避免溢出。

#include <iostream>
using namespace std;

int main() {
    int n, k;               // n:总数, k:选出的个数
    cout << "请输入n和k（要求 n >= k >= 0）：";
    cin >> n >> k;

    // 检查输入合法性
    if (k < 0 || k > n) {
        cout << "错误：k必须在0到n之间！" << endl;
        return 1;           // 返回非0表示程序异常结束
    }

    // 使用 long long 防止数字过大时溢出（n最大可到66左右）
    long long y[100][100] = {0};   // 假设n≤99

    // 构造杨辉三角形
    for (int i = 0; i <= n; i++) {
        y[i][0] = 1;               // 行首
        y[i][i] = 1;               // 行尾
        for (int j = 1; j < i; j++) {
            y[i][j] = y[i-1][j-1] + y[i-1][j];
        }
    }

    cout << "C(" << n << ", " << k << ") = " << y[n][k] << endl;
    return 0;
}

运行示例：

请输入n和k（要求 n >= k >= 0）：30 15
C(30, 15) = 155117520

8. 相关指引

  • 动态规划入门：杨辉三角形的构造方法就是最简单的动态规划——把大问题拆成小问题，用递推解。如果你学会了它，后面学背包问题、最短路径就会更容易。
  • 二项式定理：杨辉三角形和组合数是二项式定理的核心。以后学概率（比如二项分布）、组合数学都会用到。
  • 大数计算：当n很大时，long long 也不够用，你可以用高精度数组（比如用vector表示大数）来存储杨辉三角形，这在竞赛题中很常见。
  • 帕斯卡三角形：杨辉三角形在西方被称为帕斯卡三角形，其实我国宋代数学家杨辉比帕斯卡早发现几百年。数学史也很有趣哦！

这下你学会了杨辉三角形的三个大招：算组合数、展开二项式、数路径。下次做数学题或编程题时，别忘了请出你的“万能数字表”！

（完）

例题精讲

1单选题

杨辉三角的第6行（行号从1开始）的数字依次是？

A1 5 10 10 5 1
B1 4 6 4 1
C1 3 3 1
D1 6 15 20 15 6 1
2判断题

使用一维数组迭代生成杨辉三角时，必须从后往前更新数组元素，否则会覆盖之前的值导致结果错误。

3填空题
补全函数，生成杨辉三角的前numRows行，并返回二维向量。
vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res;
    for (int i = 0; i < numRows; ++i) {
        vector<int> row(i + 1, 1);
        for (int j = 1; j < i; ++j) {
            row[j] = res[i-1][j-1] + ___;
        }
        res.push_back(row);
    }
    return res;
}
4单选题

杨辉三角中的每个数字对应什么数学概念？

A组合数C(n,k)
B排列数P(n,k)
Cn的k次方
D斐波那契数
5填空题
以下代码利用杨辉三角计算组合数C(n,k)（n和k非负且k≤n）。补全代码。
int combination(int n, int k) {
    vector<vector<int>> tri(n+1);
    for (int i = 0; i <= n; ++i) {
        tri[i].resize(i+1, 1);
        for (int j = 1; j < i; ++j) {
            tri[i][j] = tri[i-1][j-1] + tri[i-1][j];
        }
    }
    return ___;
}