一、算法的概念
1. 什么是算法？
算法就是：
解决问题的方法。
同一个问题，可能有很多种解决方法。
比如要计算：
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. 衡量方法的好坏：时间与空间
一个算法好不好，通常看两个方面：
方面 含义 简单理解
时间 程序要运行多久 快不快
空间 程序要用多少内存 占地方多不多
初学阶段，我们最常关注的是时间。
因为很多题目不是不会写，而是：
写出来能运行，但太慢了。
这种情况在比赛或测评网站中叫做：超时。
4. 课堂例子：找一本书
假设桌上有 100 本书，你要找《数学练习册》。
这说明：同一个问题，不同方法的速度可能差很多。
二、时间复杂度
1. 一个语句记作 1 次
为了粗略估计程序运行时间，我们可以先简单规定：
一个普通语句执行一次，就记作 1 次。
例如：
可以看作执行了 1 次。
再例如：
这些语句的执行次数是固定的，不会因为输入数据变大而变得特别多。
2. 一层循环
看下面代码：
如果 n = 5，循环大约执行 5 次。
如果 n = 100，循环大约执行 100 次。
所以这段代码的运行次数和 n 差不多。
我们记作：O(n)
3. 两层循环
看下面代码：
如果 n = 3：
i = 1 时，j 跑 3 次
i = 2 时，j 跑 3 次
i = 3 时，j 跑 3 次
总共：
3 * 3 = 9 次
如果是一般的 n，总次数大约是：
n * n 次
所以时间复杂度记作：O(n * n)
4. O() 表示最大的花费时间
O() 可以理解为：
当数据变大时，程序最多大约要花多少时间。
常见时间复杂度：
复杂度 简单理解 常见代码
O(1) 固定次数 不循环，直接计算
O(n) 和 n 差不多 一层循环
O(n * n) n 乘 n 两层循环
注意：
时间复杂度不是精确数数，而是看大概增长速度。
例如：
这段代码大约执行 2n 次，但通常仍然记作：O(n)
因为最重要的是它和 n 成正比。
5. 1000ms = 1s
题目中经常会写：
时间限制：1000ms
其中：
1000ms = 1s
一般可以粗略认为：
1 秒最多大约运行 10^8 次简单操作。
也就是：
100000000 次
这只是估计，不是绝对准确。
但它可以帮助我们判断：
我的方法会不会太慢？
6. 复杂度判断练习
答案：O(n)
答案：O(n * n)
答案：O(1)
三、C++ 代码模板
1. 基础代码模板
以后做题时，可以先写出下面的模板：
这个模板主要包含：
头文件
命名空间
数组
solve 函数
main 函数
多组数据处理
2. 数组定义细节
这两句代码：
表示：
定义一个大小为 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 开始存：
这样第 1 个数放在 a[1]，第 2 个数放在 a[2]。
注意：
同一道题里，要统一使用一种下标习惯。
4. 多组数据处理
有些题目只有一组数据。
这时：
int t = 1;
表示只做一次。
有些题目有多组数据，输入第一行会给出 t。
例如：
3
……
……
……
表示有 3 组测试数据。
这时要把：
// cin >> t;
改成：
cin >> t;
完整写法：
5. 函数化解题
模板中有一个函数：
以后每道题的主要代码都写在 solve() 里面。
这样做的好处：
代码结构更清楚；
多组数据时更方便；
main 函数不容易写乱。
例如求两个数的和：
四、枚举
1. 枚举的概念
枚举就是：
把可能的情况一个一个试一遍。
如果一个问题暂时想不出公式，但答案可能的范围不大，就可以考虑枚举。
生活中的例子：
密码是 000 到 999。
如果不知道密码，可以从 000、001、002……一直试。
这就是枚举。
在代码中，枚举通常使用：
for
也就是用循环把可能情况一个一个列出来。
2. 枚举的基本步骤
做枚举题时，可以按下面四步想：
第一步：枚举什么？
第二步：从哪里枚举到哪里？
第三步：怎样判断当前情况对不对？
第四步：找到答案后输出什么？
这四个问题想清楚，代码就容易写了。
3. 枚举适合什么题？
如果题目满足下面特点，就可以考虑枚举：
答案范围不大；
可以一个一个试；
每次试的时候能判断对不对。
例如：
鸡有多少只？
兔有多少只？
鸡的数量不会无限大，它一定在 0 到总头数之间。
所以可以一个一个试。
4. 练习：经典鸡兔同笼问题
题目：
一个笼子里有鸡和兔。
鸡有 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
如果成立，说明找到了答案。
6. 鸡兔同笼代码
7. 代码拆解
枚举鸡的数量：
为什么从 0 开始？
可能没有鸡，全部都是兔。
为什么枚举到 h？
最多所有头都是鸡，所以鸡最多有 h 只。
计算兔的数量：
检查腿数：
找到答案后：
表示这道题已经解决，直接结束 solve()。
如果循环结束还没找到答案：
8. 课堂练习：换一种枚举
鸡兔同笼也可以枚举兔的数量。
思路：
假设兔有 rabbit 只
鸡就有 h - rabbit 只
检查腿数是否等于 f
请尝试补全代码：
参考答案：
9. 枚举小结
枚举的核心：
不会直接算，就把可能答案一个一个试。
但枚举不是乱试。
每次写枚举前都要问自己：
枚举谁？
范围是什么？
怎么判断？
答案怎么输出？
五、模拟
1. 模拟的概念
模拟就是：
题目怎么说，程序就怎么做。
如果题目描述了一个过程，我们就按照这个过程一步一步写代码。
常见模拟题包括：
排队
报数
移动
计分
发牌
按规则变化
模拟题不一定需要复杂公式。
它最重要的是：
读懂规则，并且按顺序执行。
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. 报数游戏代码
7. 用表格模拟过程
写模拟题之前，可以先用小数据演一遍。
当 n = 7：
当前数字 是否是 3 的倍数 输出
1 否 1
2 否 2
3 是 clap
4 否 4
5 否 5
6 是 clap
7 否 7
这样再写代码，就不容易漏规则。
8. 课堂练习：拍手升级版
题目：
输入一个整数 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。
参考代码：
9. 模拟小结
模拟的核心：
按照题目规则一步一步执行。
做模拟题时，一定要注意：
规则顺序；
特殊情况；
变量变化。
六、本节课总结
1. 算法
算法就是：
解决问题的方法。
同一个问题可以有不同算法。
我们会比较：
时间和空间。
2. 时间复杂度
时间复杂度用 O() 表示。
初学阶段先记住：
一个语句可以粗略记作 1 次。
一层循环通常是 O(n)。
两层循环通常是 O(n * n)。
还要记住：
1000ms = 1s
1s 最多大约运行 10^8 次简单操作
3. C++ 代码模板
以后做题可以先写：
4. 枚举
枚举就是：
把可能情况一个一个试。
代表练习：
鸡兔同笼。
5. 模拟
模拟就是：
题目怎么说，程序就怎么做。
代表练习：
报数游戏。
