一、算法的概念
1. 什么是算法？
算法就是：
同一个问题，可能有很多种解决方法。
比如要计算：
方法一：从 1 开始一个一个加。
方法二：使用公式。
这两个方法都能得到正确答案，所以它们都可以叫做算法。
但是它们的速度不一样：
学习算法，就是学习：
2. 算法不等于代码
很多同学刚开始会觉得：
其实更准确地说：
例如“鸡兔同笼”这道题：
所以做题时不要一上来就急着敲代码。
更好的顺序是：
3. 衡量方法的好坏：时间与空间
一个算法好不好，通常看两个方面：
方面 含义 简单理解 时间 程序要运行多久 快不快 空间 程序要用多少内存 占地方多不多
初学阶段，我们最常关注的是时间。
因为很多题目不是不会写，而是：
这种情况在比赛或测评网站中叫做：
4. 课堂例子：找一本书
假设桌上有 100 本书，你要找《数学练习册》。
方法一：
最坏情况下，可能要翻 100 本。
方法二：
可能很快就能找到。
这说明：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、时间复杂度
1. 一个语句记作 1 次
为了粗略估计程序运行时间，我们可以先简单规定：
例如：
可以看作执行了 1 次。
再例如：
这些语句的执行次数是固定的，不会因为输入数据变大而变得特别多。
2. 一层循环
看下面代码：
如果 n = 5，循环大约执行 5 次。
如果 n = 100，循环大约执行 100 次。
所以这段代码的运行次数和 n 差不多。
我们记作：
3. 两层循环
看下面代码：
如果 n = 3：
总共：
如果是一般的 n，总次数大约是：
所以时间复杂度记作：
4. O() 表示最大的花费时间
O() 可以理解为：
常见时间复杂度：
复杂度 简单理解 常见代码 O(1) 固定次数 不循环，直接计算 O(n) 和 n 差不多 一层循环 O(n * n) n 乘 n 两层循环
注意：
例如：
这段代码大约执行 2n 次，但通常仍然记作：
因为最重要的是它和 n 成正比。
5. 1000MS = 1S
题目中经常会写：
其中：
一般可以粗略认为：
也就是：
这只是估计，不是绝对准确。
但它可以帮助我们判断：
6. 复杂度判断练习
练习一：
答案：
练习二：
答案：
练习三：
答案：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、C++ 代码模板
1. 基础代码模板
以后做题时，可以先写出下面的模板：
这个模板主要包含：
2. 数组定义细节
这两句代码：
表示：
其中：
如果题目说：
我们常写：
为什么要多加 10？
3. 数组下标提醒
C++ 数组下标默认从 0 开始。
例如：
可以使用：
但是在算法课中，为了让第几个数和下标更容易对应，有时会从 1 开始存：
这样第 1 个数放在 a[1]，第 2 个数放在 a[2]。
注意：
4. 多组数据处理
有些题目只有一组数据。
这时：
表示只做一次。
有些题目有多组数据，输入第一行会给出 t。
例如：
表示有 3 组测试数据。
这时要把：
改成：
完整写法：
5. 函数化解题
模板中有一个函数：
以后每道题的主要代码都写在 solve() 里面。
这样做的好处：
例如求两个数的和：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、枚举
1. 枚举的概念
枚举就是：
如果一个问题暂时想不出公式，但答案可能的范围不大，就可以考虑枚举。
生活中的例子：
这就是枚举。
在代码中，枚举通常使用：
也就是用循环把可能情况一个一个列出来。
2. 枚举的基本步骤
做枚举题时，可以按下面四步想：
这四个问题想清楚，代码就容易写了。
3. 枚举适合什么题？
如果题目满足下面特点，就可以考虑枚举：
例如：
鸡的数量不会无限大，它一定在 0 到总头数之间。
所以可以一个一个试。
4. 练习：经典鸡兔同笼问题
题目：
输入格式：
输出格式：
如果没有答案，输出：
输入样例：
输出样例：
解释：
5. 鸡兔同笼分析
我们不知道鸡和兔分别有多少只。
但是知道两个条件：
我们可以枚举鸡的数量。
假设鸡有 chicken 只，那么兔的数量就是：
因为总共有 h 个头，剩下的都是兔。
然后检查腿数是否正确：
如果成立，说明找到了答案。
6. 鸡兔同笼代码
7. 代码拆解
枚举鸡的数量：
为什么从 0 开始？
为什么枚举到 h？
计算兔的数量：
检查腿数：
找到答案后：
表示这道题已经解决，直接结束 solve()。
如果循环结束还没找到答案：
8. 课堂练习：换一种枚举
鸡兔同笼也可以枚举兔的数量。
思路：
请尝试补全代码：
参考答案：
9. 枚举小结
枚举的核心：
但枚举不是乱试。
每次写枚举前都要问自己：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、模拟
1. 模拟的概念
模拟就是：
如果题目描述了一个过程，我们就按照这个过程一步一步写代码。
常见模拟题包括：
模拟题不一定需要复杂公式。
它最重要的是：
2. 模拟和枚举的区别
方法 重点 简单理解 枚举 试所有可能答案 一个一个试 模拟 按题目规则执行过程 一步一步演
例如：
3. 模拟题解题步骤
做模拟题时，可以按照下面步骤：
模拟题最常见的错误：
4. 练习：报数游戏
题目：
输入格式：
输出格式：
输入样例：
输出样例：
5. 报数游戏分析
题目规则是：
我们需要一个变量 i 表示当前报到的数字。
判断 i 是否是 3 的倍数：
其中 % 是取余。
例如：
6. 报数游戏代码
7. 用表格模拟过程
写模拟题之前，可以先用小数据演一遍。
当 n = 7：
当前数字 是否是 3 的倍数 输出 1 否 1 2 否 2 3 是 clap 4 否 4 5 否 5 6 是 clap 7 否 7
这样再写代码，就不容易漏规则。
8. 课堂练习：拍手升级版
题目：
输入样例：
部分输出：
注意：
因为 15 既满足：
也满足：
如果先判断 3 的倍数，就会直接输出 clap，漏掉 clapjump。
参考代码：
9. 模拟小结
模拟的核心：
做模拟题时，一定要注意：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、本节课总结
1. 算法
算法就是：
同一个问题可以有不同算法。
我们会比较：
2. 时间复杂度
时间复杂度用 O() 表示。
初学阶段先记住：
还要记住：
3. C++ 代码模板
以后做题可以先写：
4. 枚举
枚举就是：
代表练习：
5. 模拟
模拟就是：
代表练习：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
