杨辉三角——数字金字塔中的组合数秘密

杨辉三角是一个非常有趣的数字三角形。它看起来像一座金字塔，最顶上是一个1，下面每一行的数都等于它左上方和正上方两个数之和。这个三角形不仅好看，还藏着组合数的秘密。在数学竞赛和编程中，它经常被用来快速算出组合数、展开二项式、甚至解决概率问题。

什么是杨辉三角？

先看看它的模样：

规律很简单：

每一行的第一个和最后一个数字都是1。
中间的数字等于它左上方的数字加上它正上方的数字。例如第三行的2，等于它左上方的1加上正上方的1（即第二行的第一个1和第二个1）。

你可以把杨辉三角想象成一种“加法传递”：从山顶的1开始，数字像水一样沿着斜坡流下来，每次汇集时相加。

生活中的例子：假设你每天走路去上学，选择不同的路口组合。杨辉三角里的数字恰好代表从起点到某个路口有多少种不同的走法（类似“格点路径”）。虽然咱们不深入，但可以感受到它和“选择”“组合”有关。

杨辉三角与组合数

杨辉三角最酷的地方在于：里面的每一个数都对应一个组合数。
组合数通常写作 $C(n, k)$ 或 $\binom{n}{k}$ ，表示从 $n$ 个不同的东西中选出 $k$ 个的方法数（不考虑顺序）。

如果我们将杨辉三角的行号从0开始（最顶上一行是第0行），列号也从0开始（每行第一个是第0列），那么第 $n$ 行第 $k$ 列的数字就等于 $C(n, k)$ 。

举个例子：

第0行：只有一个数1，即 $C(0,0)=1$ 。
第1行：1 和 1，对应 $C(1,0)=1$ ， $C(1,1)=1$ 。
第2行：1 2 1，对应 $C(2,0)=1$ ， $C(2,1)=2$ ， $C(2,2)=1$ 。
第3行：1 3 3 1，对应 $C(3,0)=1$ ， $C(3,1)=3$ ， $C(3,2)=3$ ， $C(3,3)=1$ 。
第4行：1 4 6 4 1，第2个（k=2）是6，正好是 $C(4,2)=6$ 。想想看：从4个同学中选2个去参加活动，有多少种选法？答案是6种。杨辉三角直接告诉你了！

为什么？ 因为组合数有一个递推公式：
$C(n, k) = C(n-1, k-1) + C(n-1, k)$
这恰好就是杨辉三角的加法规律！所以杨辉三角是组合数最直观的“计算器”。

如何用C++生成杨辉三角？

我们可以用递推（也叫动态规划）的方法生成杨辉三角。用一个二维数组 dp[i][j] 表示第 $i$ 行第 $j$ 列的数字，然后按照规律填充。

递推公式：

边界：dp[i][0] = dp[i][i] = 1
中间：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

注意：二维数组的行和列都要足够大，而且我们只用到下三角部分（j ≤ i）。

下面是一个完整的C++程序，可以输出指定行数的杨辉三角。

#include <iostream>
#include <iomanip> // 用于格式化输出，让数字对齐
using namespace std;

void printYangHui(int n) {
    // 定义二维数组，n行n列，只使用下三角
    int triangle[n][n]; // 小心：用变长数组，n需要是编译期常量？这里n是函数参数，C++支持变长数组（VLA）是C99特性，但部分编译器不支持。更安全是用vector。
    // 为简化，我们直接用固定大小或动态分配，这里用VLA（大多数C++编译器如GCC支持，但标准C++不支持）。推荐用vector！但保留原题风格。
    
    // 填充杨辉三角
    for (int i = 0; i < n; i++) {            // i: 行号，从0到n-1
        triangle[i][0] = triangle[i][i] = 1; // 两端赋值1
        for (int j = 1; j < i; j++) {        // j: 列号，1到i-1（中间部分）
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 左上+正上
        }
    }

    // 打印输出，让三角形居中显示
    for (int i = 0; i < n; i++) {
        // 打印前导空格，使每行大致居中
        for (int space = 0; space < n - i - 1; space++) { // space: 空格变量名
            cout << "  "; // 每两个空格相当于一个数字占位宽度
        }
        // 打印当前行的所有数字
        for (int j = 0; j <= i; j++) {
            cout << setw(4) << triangle[i][j]; // setw(4)让每个数字宽度为4，右对齐
        }
        cout << endl; // 换行
    }
}

int main() {
    int rows = 6; // rows: 要打印的行数
    cout << "杨辉三角前" << rows << "行:" << endl;
    printYangHui(rows);
    return 0;
}

运行结果（假设终端支持VLA）：

杨辉三角前6行:
          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

注意：上面代码用了变长数组（VLA），这在C++标准中不是必需的，但很多竞赛环境（如GCC）支持。更标准的写法是用 vector<vector<int>>。不过作为入门学习，理解逻辑更重要。

常见错误与注意事项

数组下标越界：在填充中间部分时，循环条件 for (int j = 1; j < i; j++) 容易写成 j <= i，这样当 j == i 时会访问 triangle[i-1][i]，而该位置未定义，导致越界。记住边界已经单独赋值了，中间部分只到 i-1。
忘记初始化边界：必须把 triangle[i][0] 和 triangle[i][i] 先赋值为1。有些新手会直接用递推公式处理所有元素，结果得到垃圾值。
输出格式不整齐：使用 setw() 时要注意每个数字宽度一致，否则三角形会歪。空格数量也要计算正确：n - i - 1 个“双空格”对应一个数字宽度的缩进。
用 int 数据溢出：杨辉三角的数字增长很快，比如第20行的中间数已经超过6万，第30行超过1.5亿。如果行数较大（比如n=35），int可能溢出。可以用 long long 或更大类型。
变长数组的编译器支持问题：部分C++编译器（如MSVC）不支持VLA，会报错。建议在写竞赛题时，要么用固定大小的大数组（如 int triangle[50][50]），要么用 vector。这里给出一个更通用的版本（推荐）：

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

void printYangHui(int n) {
    // 使用vector，动态创建二维数组，每个元素初始为0
    vector<vector<int>> triangle(n);
    for (int i = 0; i < n; i++) {
        triangle[i].resize(i + 1); // 第i行有i+1个元素
        triangle[i][0] = triangle[i][i] = 1; // 两端赋值1
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    // 打印（略，与之前相同）
    for (int i = 0; i < n; i++) {
        for (int space = 0; space < n - i - 1; space++) cout << "  ";
        for (int j = 0; j <= i; j++) {
            cout << setw(4) << triangle[i][j];
        }
        cout << endl;
    }
}

完整可运行示例

我们将上面的改进版代码整合成一个完整的、可直接拷贝运行的示例。其中使用了 vector，适合所有C++环境。

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

// 函数：打印杨辉三角的前n行
void printYangHui(int n) {
    // 创建一个二维vector，每一行长度不同
    vector<vector<int>> triangle(n);
    for (int i = 0; i < n; i++) {            // i: 行号
        triangle[i].resize(i + 1);            // 第i行有i+1个数字
        triangle[i][0] = 1;                   // 第一个数字为1
        triangle[i][i] = 1;                   // 最后一个数字为1
        for (int j = 1; j < i; j++) {        // j: 列号，从1到i-1
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 左上+正上
        }
    }

    // 打印输出
    for (int i = 0; i < n; i++) {
        // 打印前导空格，使三角形居中
        for (int space = 0; space < n - i - 1; space++) {
            cout << "  ";
        }
        // 打印当前行的所有数字
        for (int j = 0; j <= i; j++) {
            cout << setw(4) << triangle[i][j];
        }
        cout << endl;
    }
}

int main() {
    int rows = 6; // rows: 用户指定打印的行数
    cout << "杨辉三角前" << rows << "行:" << endl;
    printYangHui(rows);
    return 0;
}

杨辉三角——数字的“金字塔”