信息奥赛题解｜昆虫繁殖
🚀 题目浏览
【题目描述】
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 $X$ 个月后开始产卵，每月产 $Y$ 对卵，每对卵要过两个月长成成虫。
假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵( 过 $X$ 个月产卵)，问过 $Z$ 个月以后，共有成虫多少对？
$0 \le X \le 20,1 \le Y \le 20,X \le Z \le 50$
【输入】
$X,Y,Z$ 的数值。
【输出】
过 $Z$ 个月以后，共有成虫对数。
【输入样例】
1 2 8【输出样例】
37【原题链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1204
☘️ 题解分析
昆虫繁殖 问题是 算法初学者 在学习 递推专题 时，必定遇到的问题之一。此题对于初学者来说 难度较高，很容易出现题目推着推着，就把各种变量、下标搞混的情况。😵💫
博主在阅读其他人写的题解时，要么解释的非常潦草，难以理解；要么干脆只有代码，没有解释。💦
所以在对本题进行了一定的研究后，博主撰写了此篇题解，希望能在未来帮助更多的小伙伴弄懂本题的递推关系，最后能够手撕本题代码。🧑🏻💻
在博主看来本题的难点主要有 3 个：
- 第一，不知道如何表示「过了 z 个月」
- 第二，不知道如何得到递推方程
- 第三，推出来部分递推方程，却不知道如何设定边界条件，书写代码
首先解决 第一个问题，该如何表示「过了 z 个月」？能否用列表的方式，来清晰的表式每一个月的数据 ？
该问题的关键在于，我们如何表示刚开始的第一个月？是从 0 开始，还是 1 开始 ? 实际上，两种方式都可以的，列表的方式如下：
- 从 0 开始的月份下标，此时「过了 z 个月」，就对应 z 月（如过了 1 个月，就是从 0月 → 1 月）
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 | … | z 月 |
|---|---|---|---|---|---|---|---|
| 初始数据 |
- 从 1 开始的月份下标，此时「过了 z 个月」，对应的是 z + 1 月（如过了 1 个月，就是从 1月 → 2 月）
| 月份 | 1月 | 2月 | 3月 | 4月 | 5月 | … | z + 1月 |
|---|---|---|---|---|---|---|---|
| 初始数据 |
在本文中，博主选择从第一种方式，即月份下标从 0 开始（原因会在下文分析完问题二、三后阐述）
对于 第二个问题，我们需要通过 模拟 的方式来推出递推方程。
首先，以 $x = 1, y = 2, z = 4$ 的情况进行模拟，此条件表示的是：
- 过 $x = 1$ 个月，成虫开始产卵
- 每对成虫每次产 $y = 2$ 对卵
- 要求过 $z = 4$ 个月后，成虫的数量
因为要求解成虫数量，所以比较容易想到的方式是 创建两个数组，一个存储每个月的成虫总数量（数组 c 表示），另一个存储每个月卵的总数量（数组 r 表示）。
在第 0 个月 时，有 1 对成虫，0 对卵，所以 $c[0] = 1，r[0] = 0$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | ||||
| 每月卵总数量 r[i] | 0 |
过了 1 个月后（1月），成虫开始产卵，所以在 1 月份时，卵的数量为 2，成虫数量仍为 1，$c[1] = 1，r[1] = 2$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵总数量 r[i] | 0 | 2 |
过了 2 个月后（2月），此时 1 月产的卵没有长大为成虫，所以成虫数量仍为 1，并且在这个月，成虫又产生了 y = 2 对卵，则此时共有 4 对卵（2 对新产生的卵，2 对为 1 月份仅成长了 1 个月的卵），$c[2] = 1,r[2] = 4$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | ||
| 每月卵总数量 r[i] | 0 | 2 | 4 |
过了 3 个月后（3月），此时 1 月的卵成长为了成虫，成虫数量增加，所以 $c[3] = c[2] + r[3 - 2] = 3$；对于卵来说，此时有 2 只卵变成成虫，但是原先的 1 对成虫又产生了 2 只卵，所以 $r[3] = r[2] - 2 + 2 = 4$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | |
| 每月卵总数量 r[i] | 0 | 2 | 4 | 4 |
于是我们容易总结得到，成虫数量 $c[i] = c[i - 1] + r[i -2]$ （但是这其实是有问题的 ❌）
我们继续来看 4 月份，如果按照上面这种方式，那么 $c[4] = c[3] + r[4-2] = 8$。
但是仔细思考，2 月份的 4 对卵，已经有 2 对在 3 月份变成了成虫，实际上只有 2 对卵在 4 月份变成了成虫，正确的 $c[4] = c[3] + 2 = 6$ 才对。🤔
经过思考，我们发现上面公式里的 r[i-2]，不应该设成 2 个月前卵的总数量，因为如果是总数量，那么这些卵中有一部分来自于上个月，这部分卵在下一个月就会变成成虫，而不是等 2 个月后才变成成虫。💡
所以，更加合理的表示方式，应该是将「r 数组设置为每个月新增的卵的数量」。即每个月的成虫总数量 c[i]，应该等于 上个月成虫的总数量 c[i-1] + 上 2 个月新增的卵的数量 r[i-2]（其他时间产生的卵和 c[i] 的计算并没有关系）✅
这也是为什么很多题解中，选择设置 c为每月成虫总数量，但是 r 为每月新增 的卵的数量的原因。
这样设定变量含义，就能够得到正确的递推方程：
$$
c[i] = c[i - 1] + r[i - 2] ; r[i] = c[i -x] * y
$$
递推方程含义为（在 x 个月之后）：
每月成虫总数量 $c[i]$ = 上一个月成虫总数量 $c[i -1]$ + 上 2 个月新增的卵的数量 $r[i - 2]$
每月新增的卵的数量 $r[i]$ = 上 x 个月的成虫总数量 $c[i-x] * y$
在理解了这一步后，我们再重新来推一下这个表格：
在 0 - x-1 月，第一对成虫不产卵，$c[i] \equiv 1,r[i] \equiv 0$，即：
- 在第 0 月时，$c[0] = 1,r[0] = 0$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | ||||
| 每月卵新增数量 r[i] | 0 |
在 x 月，第一对成虫开始产卵，且产了 y 对卵，$c[x] = 1,r[x] = y$，即：
- 在第 1 月时，$c[1] = 1,r[1] = 2$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵新增数量 r[i] | 0 | 2 |
在 x+1 - z 月，递推关系满足上述递推方程，有：
- 在第 2 月时，$c[2] = c[1] + r[0] = 1,r[2] = c[2 - 1] * 2 = 2$
- 在第 3 月时，$c[3] = c[2] + r[1] = 3,r[3] = c[3 - 1] * 2 = 2$
- 在第 4 月时，$c[4] = c[3] + r[2] = 5,r[4] = c[4 - 1] * 2 = 6$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | 5 |
| 每月卵新增数量 r[i] | 0 | 2 | 2 | 2 | 6 |
按照样例中 $z=8$，我们也可以得到下表，样例答案 c[8] = 37 就是这样来的。
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 | 5月 | 6月 | 7月 | 8月 |
|---|---|---|---|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | 5 | 7 | 13 | 23 | 37 |
| 每月卵新增数量 r[i] | 0 | 2 | 2 | 2 | 6 | 10 | 14 | 26 | 46 |
下面，我们以 $x = 2,y=3,z = 4$ 为例，再次模拟。
首先，在 0 - x-1 月，第一对成虫是不产卵的，所以 $c[i] \equiv 1,r[i] \equiv 0$，即：
- 在第 0 月时，$c[0] = 1,r[0] = 0$
- 在第 1 月时，$c[1] = 1,r[1] = 0$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵新增数量 r[i] | 0 | 0 |
在 x 月，第一对成虫开始产卵，且产了 y 对卵，$c[x] = 1,r[x] = y$，即：
- 在第 2 月时，$c[2] = 1,r[2] = 3$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | ||
| 每月卵新增数量 r[i] | 0 | 0 | 3 |
在 x+1 - z 月，递推关系满足上述递推方程，有：
- 在第 3 月时，$c[3] = c[2] + r[1] = 1,r[3] = c[3 - 2] * 3 = 3$
- 在第 4 月时，$c[4] = c[3] + r[2] = 4,r[4] = c[4 - 2] * 3 = 3$
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 1 | 4 |
| 每月卵新增数量 r[i] | 0 | 0 | 3 | 3 | 3 |
至此，整道题目的逻辑关系基本理清。✅
在梳理完了递推关系后，我们尝试书写代码（这题对于初学者来说确实麻烦，但是 对逻辑思维是很好的锻炼）
我们从上面的过程入手，边界条件 就比较容易确定。显然，总过程分为 3 段，分别是 0-x-1月, x月, x+1-z 月，所以我们的程序也可以分为 3 段来写：
//模拟 0 - x - 1 月
for(int i = 0; i <= x - 1; i++){
c[i] = 1;
r[i] = 0;
}
//模拟 x 月
c[x] = 1;
r[i] = y;
//模拟 x + 1 - z 月
for(int i = x + 1; i <= z; i++){
c[i] = c[i - 1] + r[i - 2];
r[i] = r[i - x] * y;
}这样，我们就完成了本题的核心代码（恭喜 🎉🎉🎉）
其实，在对 $x$ 月的赋值时，也可以将其合并到第 3 段，但是这个合并操作要求 x > 1（因为第 3 段的 递推方程中包含 r[i - 2]，所以需要保证 i - 2 > 0）。为了代码逻辑更加清晰，博主采用了 3 段式。
当然，博主也看到有代码是月份从 1 开始的，这样的话，「过了 z 个月」就是 z + 1 月，最终输出的答案是 c[z + 1]，这样从 1 开始的下标就可以保证 2、3 段合并时 $i - 2 > 0$ 了，也是可以的。
在本文中，博主选择月份下标从 0 开始，这样「过了 z 个月」就是 z 月，比较容易记忆，大伙可以根据喜好自行选择。
🍉 PS：本题需要使用 long long 类型，int 类型不够用。
🧑🏻💻 C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 10;
ll c[N]; //c数组存储每个月成虫的总数量
ll r[N]; //r数组存储每个月新增的昆虫数量
ll x, y, z;
int main() {
cin >> x >> y >> z;
//模拟 0 - x - 1 月
for (int i = 0; i <= x - 1; ++i) {
c[i] = 1;
r[i] = 0;
}
//模拟 x 月
c[x] = 1;
r[x] = y;
//模拟 x + 1 - z 月
for (int i = x + 1; i <= z + 1; ++i) {
r[i] = c[i - x] * y;
c[i] = c[i - 1] + r[i - 2];
}
cout << c[z] << endl;
return 0;
}
