模拟算法笔记(C++版)
一句话理解
> 模拟算法:照着题目的要求,一步一步用代码实现出来。
就像照着菜谱做菜——菜谱说“放盐”,你就放盐;菜谱说“翻炒3分钟”,你就等3分钟。不玩花哨,老老实实按规则来。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、什么是模拟?
模拟:把现实中的过程或题目描述的规则,用代码还原出来。
特点:
* 思路简单,不用想复杂的数学公式
* 按照题目给的步骤一步步写
* 考验的是细心和代码实现能力
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、经典例子
例子1:红绿灯
题目:一个红绿灯,红灯25秒,绿灯30秒,黄灯3秒。输入一个时间(秒),输出当前是什么灯。
思路:一个完整循环是25+30+3=58秒,看时间在循环的哪一段。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例子2:存钱罐
题目:小明每天往存钱罐里存5块钱,但每存3天就要打破罐子取出10块钱买零食。问第30天结束时,罐子里有多少钱?
思路:一天一天模拟,每天加5,每3天减10。
输出:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例子3:蜗牛爬井
题目:一口井10米深,蜗牛白天爬3米,晚上滑下2米。问第几天能爬出去?
思路:一天一天模拟,白天往上爬,如果到了井口就结束,晚上往下滑。
输出:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例子4:蛇形填数
题目:在5×5的格子里,从左上角开始,按顺时针方向(右→下→左→上→右...)填入1到25。
思路:用方向数组控制方向,撞墙或遇到填过的格子就转弯。
输出:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、写模拟题的小技巧
三步走:
1. 看懂规则:题目让你做什么?自己在纸上画一遍过程
2. 选好变量:想想要用哪些变量来记录状态
3. 翻译代码:把每一步规则写成代码
容易踩的坑:
容易错的地方 怎么办 边界条件 多试几个边界值,比如第1天、最后一天 数组越界 用if判断下标是不是在范围内 什么时候停 想清楚循环结束的条件 方向搞错 在纸上画图,用方向数组写清楚
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、总结
要点 内容 核心思想 用代码还原题目说的规则 优点 思路简单,不用想复杂公式 缺点 代码可能很长,容易少考虑情况 什么时候用 题目把规则说得很清楚,一步步做就行 注意什么 边界要小心,多测试几遍
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
记忆口诀
> 模拟就是照着做,一步一步别乱走
> 边界条件多想想,纸笔画图好帮手
> 循环结束要记牢,数组越界防得住