XP02-11-枚举、模拟笔记
2026-08-01 19:36:25
发布于：广东
一、算法的概念
- 什么是算法？
算法就是：
解决问题的方法。
同一个问题，可能有很多种解决方法。
比如要计算：
1 + 2 + 3 + ... + 100
方法一：从 1 开始一个一个加。
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
……
一直加到 100
方法二：使用公式。
(1 + 100) * 100 / 2 = 5050
这两个方法都能得到正确答案，所以它们都可以叫做算法。
但是它们的速度不一样：
一个一个加：步骤比较多
使用公式：步骤比较少
学习算法，就是学习：
怎样用更清楚、更快、更省空间的方法解决问题。
2. 算法不等于代码
很多同学刚开始会觉得：
算法就是代码。
其实更准确地说：
算法是想法，代码是把想法写出来。
例如“鸡兔同笼”这道题：
想法：假设鸡有 0 只、1 只、2 只……一个一个试。
代码：用 for 循环把这个想法写出来。
所以做题时不要一上来就急着敲代码。
更好的顺序是：
先想方法，再写代码。
3. 衡量方法的好坏：时间与空间
一个算法好不好，通常看两个方面：
方面 含义 简单理解
时间 程序要运行多久 快不快
空间 程序要用多少内存 占地方多不多
初学阶段，我们最常关注的是时间。
因为很多题目不是不会写，而是：
写出来能运行，但太慢了。
这种情况在比赛或测评网站中叫做：超时。
- 课堂例子：找一本书
假设桌上有 100 本书，你要找《数学练习册》。
方法一：
从第一本开始一本一本翻。
最坏情况下，可能要翻 100 本。
方法二：
如果这些书已经按科目排好，就可以先找数学区，再找练习册。
可能很快就能找到。
这说明：同一个问题，不同方法的速度可能差很多。
二、时间复杂度
- 一个语句记作 1 次
为了粗略估计程序运行时间，我们可以先简单规定：
一个普通语句执行一次，就记作 1 次。
例如：
int x = 10;
可以看作执行了 1 次。
再例如：
int a = 3;
int b = 5;
int c = a + b;
cout << c << endl;
这些语句的执行次数是固定的，不会因为输入数据变大而变得特别多。
- 一层循环
看下面代码：
for (int i = 1; i <= n; i++) {
cout << i << endl;
}
如果 n = 5，循环大约执行 5 次。
如果 n = 100，循环大约执行 100 次。
所以这段代码的运行次数和 n 差不多。
我们记作：O(n)
- 两层循环
看下面代码：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << i << " " << j << endl;
}
}
如果 n = 3：
i = 1 时，j 跑 3 次
i = 2 时，j 跑 3 次
i = 3 时，j 跑 3 次
总共：
3 * 3 = 9 次
如果是一般的 n，总次数大约是：
n * n 次
所以时间复杂度记作：O(n * n)
- O() 表示最大的花费时间
O() 可以理解为：
当数据变大时，程序最多大约要花多少时间。
常见时间复杂度：
复杂度 简单理解 常见代码
O(1) 固定次数 不循环，直接计算
O(n) 和 n 差不多 一层循环
O(n * n) n 乘 n 两层循环
注意：
时间复杂度不是精确数数，而是看大概增长速度。
例如：
for (int i = 1; i <= n; i++) {
cout << i << endl;
}
for (int i = 1; i <= n; i++) {
cout << i * 2 << endl;
}
这段代码大约执行 2n 次，但通常仍然记作：O(n)
因为最重要的是它和 n 成正比。
- 1000ms = 1s
题目中经常会写：
时间限制：1000ms
其中：
1000ms = 1s
一般可以粗略认为：
1 秒最多大约运行 10^8 次简单操作。
也就是：
100000000 次
这只是估计，不是绝对准确。
但它可以帮助我们判断：
我的方法会不会太慢？
6. 复杂度判断练习
练习一：
for (int i = 1; i <= n; i++) {
cout << i << endl;
}
答案：O(n)
练习二：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << i + j << endl;
}
}
答案：O(n * n)
练习三：
cout << "hello" << endl;
答案：O(1)
三、C++ 代码模板
- 基础代码模板
以后做题时，可以先写出下面的模板：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5; // 10^5
int a[N];
void solve() {
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
这个模板主要包含：
头文件
命名空间
数组
solve 函数
main 函数
多组数据处理
2. 数组定义细节
这两句代码：
const int N = 1e5;
int a[N];
表示：
定义一个大小为 100000 的整型数组。
其中：
1e5 = 10^5 = 100000
如果题目说：
n 最大是 100000
我们常写：
const int N = 1e5 + 10;
int a[N];
为什么要多加 10？
为了让数组稍微大一点，避免下标边界出错。
3. 数组下标提醒
C++ 数组下标默认从 0 开始。
例如：
int a[5];
可以使用：a[0], a[1], a[2], a[3], a[4]
但是在算法课中，为了让第几个数和下标更容易对应，有时会从 1 开始存：
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
这样第 1 个数放在 a[1]，第 2 个数放在 a[2]。
注意：
同一道题里，要统一使用一种下标习惯。
4. 多组数据处理
有些题目只有一组数据。
这时：
int t = 1;
表示只做一次。
有些题目有多组数据，输入第一行会给出 t。
例如：
3
……
……
……
表示有 3 组测试数据。
这时要把：
// cin >> t;
改成：
cin >> t;
完整写法：
int t = 1;
cin >> t;
while (t--) {
solve();
}
- 函数化解题
模板中有一个函数：
void solve() {
}
以后每道题的主要代码都写在 solve() 里面。
这样做的好处：
代码结构更清楚；
多组数据时更方便；
main 函数不容易写乱。
例如求两个数的和：
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
cout << a + b << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
四、枚举
- 枚举的概念
枚举就是：
把可能的情况一个一个试一遍。
如果一个问题暂时想不出公式，但答案可能的范围不大，就可以考虑枚举。
生活中的例子：
密码是 000 到 999。
如果不知道密码，可以从 000、001、002……一直试。
这就是枚举。
在代码中，枚举通常使用：
for
也就是用循环把可能情况一个一个列出来。
- 枚举的基本步骤
做枚举题时，可以按下面四步想：
第一步：枚举什么？
第二步：从哪里枚举到哪里？
第三步：怎样判断当前情况对不对？
第四步：找到答案后输出什么？
这四个问题想清楚，代码就容易写了。
- 枚举适合什么题？
如果题目满足下面特点，就可以考虑枚举：
答案范围不大；
可以一个一个试；
每次试的时候能判断对不对。
例如：
鸡有多少只？
兔有多少只？
鸡的数量不会无限大，它一定在 0 到总头数之间。
所以可以一个一个试。
- 练习：经典鸡兔同笼问题
题目：
一个笼子里有鸡和兔。
鸡有 2 条腿，兔有 4 条腿。
现在知道一共有 h 个头，f 条腿。
问鸡和兔分别有多少只？
输入格式：
h f
输出格式：
鸡的数量 兔的数量
如果没有答案，输出：
No
输入样例：
5 14
输出样例：
3 2
解释：
3 只鸡有 6 条腿
2 只兔有 8 条腿
一共 5 个头，14 条腿
5. 鸡兔同笼分析
我们不知道鸡和兔分别有多少只。
但是知道两个条件：
鸡的数量 + 兔的数量 = h
鸡的数量 * 2 + 兔的数量 * 4 = f
我们可以枚举鸡的数量。
假设鸡有 chicken 只，那么兔的数量就是：
h - chicken
因为总共有 h 个头，剩下的都是兔。
然后检查腿数是否正确：
chicken * 2 + rabbit * 4 == f
如果成立，说明找到了答案。
- 鸡兔同笼代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int h, f;
cin >> h >> f;
for (int chicken = 0; chicken <= h; chicken++) {
int rabbit = h - chicken;
if (chicken * 2 + rabbit * 4 == f) {
cout << chicken << " " << rabbit << endl;
return;
}
}
cout << "No" << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
- 代码拆解
枚举鸡的数量：
for (int chicken = 0; chicken <= h; chicken++)
为什么从 0 开始？
可能没有鸡，全部都是兔。
为什么枚举到 h？
最多所有头都是鸡，所以鸡最多有 h 只。
计算兔的数量：
int rabbit = h - chicken;
检查腿数：
if (chicken * 2 + rabbit * 4 == f)
找到答案后：
return 0;
表示这道题已经解决，直接结束 solve()。
如果循环结束还没找到答案：
cout << "No" << endl;
- 课堂练习：换一种枚举
鸡兔同笼也可以枚举兔的数量。
思路：
假设兔有 rabbit 只
鸡就有 h - rabbit 只
检查腿数是否等于 f
请尝试补全代码：
for (int rabbit = 0; rabbit <= h; rabbit++) {
int chicken = __________;
if (__________________________) {
cout << chicken << " " << rabbit << endl;
return;
}
}
参考答案：
for (int rabbit = 0; rabbit <= h; rabbit++) {
int chicken = h - rabbit;
if (chicken * 2 + rabbit * 4 == f) {
cout << chicken << " " << rabbit << endl;
return;
}
}
- 枚举小结
枚举的核心：
不会直接算，就把可能答案一个一个试。
但枚举不是乱试。
每次写枚举前都要问自己：
枚举谁？
范围是什么？
怎么判断？
答案怎么输出？
五、模拟
- 模拟的概念
模拟就是：
题目怎么说，程序就怎么做。
如果题目描述了一个过程，我们就按照这个过程一步一步写代码。
常见模拟题包括：
排队
报数
移动
计分
发牌
按规则变化
模拟题不一定需要复杂公式。
它最重要的是：
读懂规则，并且按顺序执行。
2. 模拟和枚举的区别
方法 重点 简单理解
枚举 试所有可能答案 一个一个试
模拟 按题目规则执行过程 一步一步演
例如：
枚举：鸡可能有 0 只、1 只、2 只……一个一个试。
模拟：老师说从 1 报数，遇到 3 的倍数拍手，程序就照着做。
3. 模拟题解题步骤
做模拟题时，可以按照下面步骤：
第一步：读规则。
第二步：找变量。
第三步：按顺序执行规则。
第四步：输出结果。
模拟题最常见的错误：
漏掉规则；
顺序写反；
变量忘记更新；
边界情况没有考虑。
4. 练习：报数游戏
题目：
有 n 个同学站成一排，从左到右编号为 1 到 n。
老师让大家从 1 开始报数。
如果某个同学报到的数字是 3 的倍数，就拍手一次；
否则就正常说出这个数字。
请输出每个同学应该做什么。
输入格式：
n
输出格式：
从 1 到 n，每个数字一行。
如果这个数是 3 的倍数，输出 clap。
否则输出这个数字。
输入样例：
7
输出样例：
1
2
clap
4
5
clap
7
5. 报数游戏分析
题目规则是：
从 1 报到 n。
如果当前数字是 3 的倍数，输出 clap。
否则输出当前数字。
我们需要一个变量 i 表示当前报到的数字。
判断 i 是否是 3 的倍数：
i % 3 == 0
其中 % 是取余。
例如：
6 % 3 = 0，说明 6 是 3 的倍数
7 % 3 = 1，说明 7 不是 3 的倍数
6. 报数游戏代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
if (i % 3 == 0) {
cout << "clap" << endl;
} else {
cout << i << endl;
}
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
- 用表格模拟过程
写模拟题之前，可以先用小数据演一遍。
当 n = 7：
当前数字 是否是 3 的倍数 输出
1 否 1
2 否 2
3 是 clap
4 否 4
5 否 5
6 是 clap
7 否 7
这样再写代码，就不容易漏规则。
- 课堂练习：拍手升级版
题目：
输入一个整数 n。
从 1 输出到 n。
如果数字是 3 的倍数，输出 clap。
如果数字是 5 的倍数，输出 jump。
如果数字既是 3 的倍数又是 5 的倍数，输出 clapjump。
否则输出这个数字。
输入样例：
16
部分输出：
1
2
clap
4
jump
clap
7
8
clap
jump
11
clap
13
14
clapjump
16
注意：
既是 3 的倍数又是 5 的倍数，要先判断。
因为 15 既满足：
15 % 3 == 0
也满足：
15 % 5 == 0
如果先判断 3 的倍数，就会直接输出 clap，漏掉 clapjump。
参考代码：
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 == 0) {
cout << "clapjump" << endl;
} else if (i % 3 == 0) {
cout << "clap" << endl;
} else if (i % 5 == 0) {
cout << "jump" << endl;
} else {
cout << i << endl;
}
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
- 模拟小结
模拟的核心：
按照题目规则一步一步执行。
做模拟题时，一定要注意：
规则顺序；
特殊情况；
变量变化。
六、本节课总结
- 算法
算法就是：
解决问题的方法。
同一个问题可以有不同算法。
我们会比较：
时间和空间。
2. 时间复杂度
时间复杂度用 O() 表示。
初学阶段先记住：
一个语句可以粗略记作 1 次。
一层循环通常是 O(n)。
两层循环通常是 O(n * n)。
还要记住：
1000ms = 1s
1s 最多大约运行 10^8 次简单操作
3. C++ 代码模板
以后做题可以先写：
void solve() {
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
- 枚举
枚举就是：
把可能情况一个一个试。
代表练习：
鸡兔同笼。
5. 模拟
模拟就是：
题目怎么说，程序就怎么做。
代表练习：
报数游戏。
有帮助，赞一个