GESP 8级《杨辉三角》的考纲要求是什么？

GESP 8级《杨辉三角》是 CCF 编程能力等级认证（C++）的官方考点，考频★★☆、难度★★☆。本页严格对照官方考纲逐条拆解要求，配有通俗讲解、必背重点、易错陷阱与考场真题，帮助中小学生零基础系统掌握。

GESP 8级《杨辉三角》怎么学？有哪些易错点？

学习《杨辉三角》建议四步：①读「通俗讲解」理解概念；②记「核心必背重点」；③避开「高频易错陷阱」；④用「真题演练」检验。本站为该考点提供 ASCII 图解、例题与历年真题，循序渐进即可通关 GESP 8级。

📌 杨辉三角

所属等级：GESP 8级｜难度：★★★ ｜关键词：杨辉三角

📝 考纲要求

掌握杨辉三角（又称帕斯卡三角形）的定义：从第 0 行开始，每行首尾为 1，中间每个数等于它上一行左上方与正上方两数之和；
能用二维数组递推实现杨辉三角，正确生成并输出前 n 行；
理解杨辉三角与组合数 C(n,k) 的关系：第 n 行第 k 个数恰好等于 C(n,k)，并能用它来求组合数；
了解滚动数组优化空间（只保留上一行）的基本思想。

📖 通俗讲解

💡 一句话理解杨辉三角是一个数字金字塔：每行首尾是 1，中间每个数 = 它头顶左上方 + 正上方两个数之和。它不只是数字游戏——第 n 行第 k 个数正好就是组合数 C(n,k)（从 n 个里选 k 个的选法数）。

杨辉三角从第 0 行开始：第 0 行是孤零零的 1；第 1 行是 1 1；往下每一行都比上一行多一个数，且最左、最右都是 1，中间每个数由“上一行相邻两个数相加”得到。这种“小推大”的方式叫递推，写程序时用一个二维数组就能轻松生成。

关键性质：把行号记为 i、列号记为 j（都从 0 开始），那么 C[i][j] = C[i-1][j-1] + C[i-1][j]，而且 C[i][j] 的值就等于组合数 C(i,j)。所以“画杨辉三角”和“算组合数”是同一件事，只是换个角度说。

🖼️ 图解 ①：杨辉三角前 6 行（行号 0~5）的数字金字塔

行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；第 2 行 2 = 1+1；第 3 行 3 = 1+2、3 = 2+1；第 4 行 6 = 3+3 ……

🖼️ 图解 ②：递推关系图（每个数 = 左上方 + 正上方）

          1            <-- 行0
        1   1          <-- 行1
      1   2   1        <-- 行2
    1   3   3   1      <-- 行3
  1   4   6   4   1    <-- 行4
         │   │
         └─6 = 3 + 3─┘      (第4行第2个 = 第3行第1个3 + 第3行第2个3)

递推式：C[i][j] = C[i-1][j-1] + C[i-1][j]
边界：  C[i][0] = 1，C[i][i] = 1

🔵 核心必背重点

✅ 必背

边界：每行第 0 个、第 i 个都是 1，即 C[i][0]=1、C[i][i]=1；
递推式：C[i][j] = C[i-1][j-1] + C[i-1][j]（j 从 1 到 i-1）；
与组合数关系：第 n 行第 k 个数 = C(n,k)，所以求 C(n,k) 就是输出第 n 行第 k 个；
对称性：C(n,k) = C(n,n-k)，对应三角左右对称；
滚动数组优化：只需上一行，可用一维数组从后往前更新，把 O(n²) 空间降到 O(n)。

🔑

记忆口诀：“首尾都是 1，中间头顶两数加；第 n 行第 k 个，就是组合 C(n,k)；空间不够滚动来救驾。”

🖼️ 滚动数组示意（一维数组 f，从后往前更新）

C++

// 只保留一行：f[j] 在第 i 轮更新后表示 C(i,j)
// 必须从后往前(j 递减)更新，否则会被新值覆盖
for (int i = 1; i <= n; i++) {
    for (int j = i; j >= 1; j--) {
        f[j] = f[j] + f[j-1];   // 等价于 C[i][j]=C[i-1][j]+C[i-1][j-1]
    }
}
// 结束后 f[k] 即为 C(n,k)

🔴 考试拉分难点

⚠️ 难点

行号/列号从 0 还是 1 开始：递推式 C[i][j]=C[i-1][j-1]+C[i-1][j] 依赖“从 0 开始”的约定，若题目从 1 开始，要小心偏移；
大数溢出：组合数增长极快，第 30 行附近就超过 int 范围，n 稍大应改用 long long 或对质数取模；
滚动数组更新方向：必须从后往前(j 递减)，否则 f[j-1] 已被本行新值覆盖，结果错误；
下标越界：数组开小了，或访问了 C[i-1] 当 i=0 时，都会越界。

🟡 高频易错陷阱

🚫 扣分坑点

忘记给首尾赋 1，导致中间数累加出 0+0=0；
用 int 存组合数溢出，应 long long；取模时忘了“每个加法都取模”；
滚动数组写成 for j=1..i（从前往后），把上一行旧值提前冲掉；
求 C(n,k) 时把“第 n 行”误当成“第 n 列”，行列写反；
用了禁用的 bits/stdc++.h，只用 iostream。

🧪 例题演练

例题 1（基础题）：二维数组递推生成杨辉三角前 n 行

题目：输入一个整数 n，用二维数组递推生成并输出杨辉三角的前 n 行（每行数字用空格隔开）。

C++

#include <iostream>
using namespace std;

const int N = 35;
long long C[N][N];   // C[i][j] 表示第 i 行第 j 个数

int main() {
    int n;
    cin >> n;          // 输入要输出的行数
    // 递推生成前 n 行
    for (int i = 0; i < n; i++) {
        C[i][0] = 1;          // 每行第一个是 1
        C[i][i] = 1;          // 每行最后一个是 1
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];  // 上一行两数之和
        }
    }
    // 输出前 n 行
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << C[i][j];
            if (j < i) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

输入 / 输出5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

例题 2（模拟真题）：用杨辉三角求组合数 C(n,k)（取模防溢出）

题目：输入 n、k，输出组合数 C(n,k)。说明：杨辉三角第 n 行第 k 个数正好就是 C(n,k)。由于组合数增长很快，这里对质数 MOD 取模避免溢出。

C++

#include <iostream>
using namespace std;

const int N = 1005;
const int MOD = 1000000007;   // 大质数，取模避免溢出
long long C[N][N];

int main() {
    int n, k;
    cin >> n >> k;
    // 递推打表：C[i][j] = C[i-1][j-1] + C[i-1][j]
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;          // 第 i 行第 0 个
        C[i][i] = 1;          // 对角线
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;  // 每次加法都取模
        }
    }
    // 第 n 行第 k 个数就是 C(n,k)
    cout << C[n][k] << endl;
    return 0;
}

输入 / 输出5 2 10

🚫 错误示范 cout << C[k][n]; —— 把行列写反了。杨辉三角里第 n 行第 k 个才是 C(n,k)，应写成 C[n][k]。