【GESP】C++八级考试大纲知识点梳理 (1) 计数原理：加法与乘法

GESP C++八级考试大纲正式进入了组合数学的领域。作为八级的第一条考点，计数原理是整个排列组合、概率论乃至后续很多算法（如动态规划）的基石。

（1）掌握计数原理。包括加法原理和乘法原理。

计数原理听起来很高大上，其实核心就是解决“有多少种方法”这类问题。无论是日常生活中的穿衣搭配，还是算法中的路径统计，都离不开这两个基本原理。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

---

一、两个核心原理

解决计数问题，最关键的第一步是判断：这件事情是分情况完成的，还是分步骤完成的？

1.1 加法原理 (Rule of Sum) —— 分类计数

如果完成一件事有 $n$ 类不同的方案：

• 第一类方案有 $m_1$ 种方法；
• 第二类方案有 $m_2$ 种方法；
• …
• 第 $n$ 类方案有 $m_n$ 种方法。

那么完成这件事的总方法数 $N$ 为各类方法数之和：

\[N = m_1 + m_2 + \dots + m_n\]

核心关键词：“分类”、“或者”

• 分类：每一类方案都能独立完成整件事。选了第一类里的某种方法，事情就做完了，不需要再看第二类。
• 互斥：各类方案之间没有重复（交集为空）。

例子： 从北京去上海，可以选择坐飞机或者坐高铁。

• 飞机有 5 个航班；
• 高铁有 10 个班次。

那么从北京去上海的方法总数 = $5 + 10 = 15$ 种。 （你不可能既坐这趟航班又坐那趟高铁，选定一个，行程就结束了。）

---

1.2 乘法原理 (Rule of Product) —— 分步计数

如果完成一件事需要分 $n$ 个步骤：

• 做第 1 步有 $m_1$ 种方法；
• 做第 2 步有 $m_2$ 种方法；
• …
• 做第 $n$ 步有 $m_n$ 种方法。

那么完成这件事的总方法数 $N$ 为各步骤方法数之积：

\[N = m_1 \times m_2 \times \dots \times m_n\]

核心关键词：“分步”、“先…后…”、“并且”

• 分步：每一步都不能独立完成整件事，必须把所有步骤都做完，事情才算做完。
• 独立：前一步的选择虽然影响结果，但不影响后一步的可选数量（通常情况下）。

例子： 中午点套餐，需要先选主食，再选饮料。

• 主食有 3 种（汉堡、炸鸡、披萨）；
• 饮料有 4 种（可乐、雪碧、果汁、咖啡）。

那么搭配一个完整套餐的方法总数 = $3 \times 4 = 12$ 种。 （只选主食不选饮料，套餐没点完。）

---

二、通过对比来记忆

维度	加法原理 (分类)	乘法原理 (分步)
完成方式	任何一类方法都能独立完成任务	必须经过所有步骤才能完成任务
逻辑关系	“或者” (Or)	“并且” / “先…后…” (And)
计算法则	求和 ($+$)	求积 ($\times$)
例子	只有 1 张票，去动物园或游乐园	去动物园，先看猴子，再看大象

---

三、经典应用举例

3.1 路径问题

从 A 地到 C 地，必须经过 B 地。

• A 到 B 有 3 条路；
• B 到 C 有 2 条路。

问：从 A 到 C 有多少种走法？

分析： 这是一个典型的分步过程。

1. 第一步：从 A 走到 B（3 种选法）；
2. 第二步：从 B 走到 C（2 种选法）。 两步缺一不可，所以用乘法原理。

\[\text{总数} = 3 \times 2 = 6 \text{ 种}\]

---

3.2 衣服搭配

小明有：

• 上衣：红、黄、蓝 (3 件)
• 裤子：黑、白 (2 条)
• 鞋子：运动鞋、皮鞋 (2 双)

问：小明如果要穿戴整齐（上衣+裤子+鞋子），有多少种搭配？

分析： 穿戴整齐需要分三步：

1. 选上衣 (3 种)
2. 选裤子 (2 种)
3. 选鞋子 (2 种) 必须都选好才算“穿戴整齐”，用乘法原理。

\[\text{搭配总数} = 3 \times 2 \times 2 = 12 \text{ 种}\]

变式：如果不要求穿鞋子，只需要上衣和裤子呢？ \(3 \times 2 = 6 \text{ 种}\)

---

3.3 简单的排列数预告

问：有 A, B, C 三位同学排成一排照相，有多少种排法？

分析：

• 第 1 个位置：可以在 A, B, C 中任选 1 人，有 3 种选择；
• 第 2 个位置：剩下 2 人中任选 1 人，有 2 种选择；
• 第 3 个位置：只剩 1 人，只有 1 种选择。

这三个位置必须都站好人，照相才完成，所以是分步。

\[\text{总数} = 3 \times 2 \times 1 = 6 \text{ 种}\]

这也就是我们后面要讲的全排列，即 $3! = 6$。

---

四、程序题举例

在编程解题中，计数原理通常直接对应着代码的控制结构。深刻理解这一点，能帮助我们快速把数学思路转化为代码。

4.1 加法原理与分支/并列逻辑

当我们需要统计的合法方案分布在互不干扰的几个类别中时，我们在代码中通常是分别计算每一类的数量，最后累加。

场景：我们要从甲、乙两地选一个地方去旅游。

• 去甲地的方案记录在数组 A 中（共 A.size() 种）；
• 去乙地的方案记录在数组 B 中（共 B.size() 种）。

// 方案总数 = 甲地方案数 + 乙地方案数
int total_ways = 0;

// 第一类：选择去甲地
for (int i = 0; i < A.size(); i++) {
    total_ways++; 
}

// 第二类：选择去乙地
for (int i = 0; i < B.size(); i++) {
    total_ways++;
}

// 核心体现：total = m + n

或者在递归/DFS搜索中：

int dfs(int step) {
    if (step == target) return 1;
    // 下一步可以选择向左走，或者向右走
    // 总方案数 = 向左走的方案数 + 向右走的方案数
    return dfs(step + 1, "left") + dfs(step + 1, "right");
}

4.2 乘法原理与嵌套循环

这是编程中最常见的组合计数模式。每一个嵌套的循环代表一个步骤，循环的次数代表该步骤的选择数。

场景：你有 3 件上衣（shirts）和 2 条裤子（pants），输出所有穿搭方案。

int shirts = 3;
int pants = 2;
int total_combinations = 0;

// 步骤 1：选上衣
for (int i = 1; i <= shirts; i++) {
    // 步骤 2：选裤子
    for (int j = 1; j <= pants; j++) {
        // 只有两步都走到了，才算一种有效方案
        total_combinations++;
        // cout << "方案: 上衣" << i << " + 裤子" << j << endl;
    }
}

// 核心体现：total = 3 * 2 = 6

推广： 如果是 $N$ 个步骤，往往就需要 $N$ 层循环（或者递归深度为 $N$）。每一层循环的迭代次数相乘，就是总的时间复杂度或方案总数。这解释了为什么全排列的时间复杂度是 $O(N!)$，子集枚举是 $O(2^N)$ —— 本质都是乘法原理。

---

五、总结

掌握计数原理是学习排列组合的第一步。遇到题目时，请默念口诀：

• 分类相加：这一步做完，事就成了吗？成了 $\rightarrow$ 加法。
• 分步相乘：这一步做完，事还没成，得接着做下一步 $\rightarrow$ 乘法。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号