首页分享【信息奥赛题解】昆虫繁殖（详细分析题解 & C++ 代码）

【信息奥赛题解】昆虫繁殖（详细分析题解 & C++ 代码）

来源：萌宠菠菠乐园时间：2025-05-11 08:33

昆虫繁殖问题【题目名称】昆虫繁殖【题目描述】

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 X X X 个月后开始产卵，每月产 Y Y Y 对卵，每对卵要过两个月长成成虫。

假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵( 过 X X X 个月产卵)，问过 Z Z Z 个月以后，共有成虫多少对？

0 ≤ X ≤ 20 , 1 ≤ Y ≤ 20 , X ≤ Z ≤ 50 0 le X le 20,1 le Y le 20,X le Z le 50 0≤X≤20,1≤Y≤20,X≤Z≤50

【输入】

X , Y , Z X,Y,Z X,Y,Z 的数值。

【输出】

过 Z Z Z 个月以后，共有成虫对数。

【输入样例】

1 2 8 1 【输出样例】

37 1 【原题链接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1312

【题目分析】

昆虫繁殖 问题是算法初学者在学习 递推专题 时，必定遇到的问题之一。此题对于初学者来说 难度较高，很容易出现题目推着推着，就把各种变量、下标搞混的情况。‍

博主在阅读其他人写的题解时，发现这些题解要么解释的非常潦草，难以理解；要么干脆只有代码，没有解释。

所以在对本题进行了一定的研究后，博主撰写了此篇题解，希望能在未来帮助更多的小伙伴弄懂本题的递推关系，最后能够手撕本题代码。‍

在博主看来本题的难点主要有 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 x=1,y=2,z=4 的情况进行模拟，此条件表示的是：

过 x = 1 x = 1 x=1 个月，成虫开始产卵每对成虫每次产 y = 2 y = 2 y=2 对卵要求过 z = 4 z = 4 z=4 个月后，成虫的数量

因为要求解成虫数量，所以比较容易想到的方式是 创建两个数组，一个存储每个月的成虫总数量（数组 c 表示），另一个存储每个月卵的总数量（数组 r 表示）。

在第 0 个月 时，有 1 对成虫，0 对卵，所以 c [ 0 ] = 1 ， r [ 0 ] = 0 c[0] = 1，r[0] = 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 c[1] = 1，r[1] = 2 c[1]=1，r[1]=2

月份0月1月2月3月4月每月成虫总数量 c[i]11每月卵总数量 r[i]02

过了 2 个月后（2月），此时 1 月产的卵没有长大为成虫，所以成虫数量仍为 1，并且在这个月，成虫又产生了 y = 2 对卵，则此时共有 4 对卵（2 对新产生的卵，2 对为 1 月份仅成长了 1 个月的卵）， c [ 2 ] = 1 , r [ 2 ] = 4 c[2] = 1,r[2] = 4 c[2]=1,r[2]=4

月份0月1月2月3月4月每月成虫总数量 c[i]111每月卵总数量 r[i]024

过了 3 个月后（3月），此时 1 月的卵成长为了成虫，成虫数量增加，所以 c [ 3 ] = c [ 2 ] + r [ 3 − 2 ] = 3 c[3] = c[2] + r[3 - 2] = 3 c[3]=c[2]+r[3−2]=3；对于卵来说，此时有 2 只卵变成成虫，但是原先的 1 对成虫又产生了 2 只卵，所以 r [ 3 ] = r [ 2 ] − 2 + 2 = 4 r[3] = r[2] - 2 + 2 = 4 r[3]=r[2]−2+2=4

月份0月1月2月3月4月每月成虫总数量 c[i]1113每月卵总数量 r[i]0244

于是我们容易总结得到，成虫数量 c [ i ] = c [ i − 1 ] + r [ i − 2 ] c[i] = c[i - 1] + r[i -2] c[i]=c[i−1]+r[i−2] （但是这其实是有问题的 ❌）

我们继续来看 4 月份，如果按照上面这种方式，那么 c [ 4 ] = c [ 3 ] + r [ 4 − 2 ] = 8 c[4] = c[3] + r[4-2] = 8 c[4]=c[3]+r[4−2]=8。

但是仔细思考，2 月份的 4 对卵，已经有 2 对在 3 月份变成了成虫，实际上只有 2 对卵在 4 月份变成了成虫，正确的 c [ 4 ] = c [ 3 ] + 2 = 6 c[4] = c[3] + 2 = 6 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 c[i] = c[i - 1] + r[i - 2]r[i] = c[i -x] * y c[i]=c[i−1]+r[i−2]r[i]=c[i−x]∗y
递推方程含义为（在 x 个月之后）：

每月成虫总数量 c [ i ] c[i] c[i] = 上一个月成虫总数量 c [ i − 1 ] c[i -1] c[i−1] + 上 2 个月新增的卵的数量 r [ i − 2 ] r[i - 2] r[i−2]

每月新增的卵的数量 r [ i ] r[i] r[i] = 上 x 个月的成虫总数量 c [ i − x ] ∗ y c[i-x] * y c[i−x]∗y

在理解了这一步后，我们再重新来推一下这个表格：

在 0 - x-1 月，第一对成虫不产卵， c [ i ] ≡ 1 , r [ i ] ≡ 0 c[i] equiv 1,r[i] equiv 0 c[i]≡1,r[i]≡0，即：

在第 0 月时， c [ 0 ] = 1 , r [ 0 ] = 0 c[0] = 1,r[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 c[x] = 1,r[x] = y c[x]=1,r[x]=y，即：

在第 1 月时， c [ 1 ] = 1 , r [ 1 ] = 2 c[1] = 1,r[1] = 2 c[1]=1,r[1]=2 月份0月1月2月3月4月每月成虫总数量 c[i]11每月卵新增数量 r[i]02

在 x+1 - z 月，递推关系满足上述递推方程，有：

在第 2 月时， c [ 2 ] = c [ 1 ] + r [ 0 ] = 1 , r [ 2 ] = c [ 2 − 1 ] ∗ 2 = 2 c[2] = c[1] + r[0] = 1,r[2] = c[2 - 1] * 2 = 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 c[3] = c[2] + r[1] = 3,r[3] = c[3 - 1] * 2 = 2 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 c[4] = c[3] + r[2] = 5,r[4] = c[4 - 1] * 2 = 6 c[4]=c[3]+r[2]=5,r[4]=c[4−1]∗2=6 月份0月1月2月3月4月每月成虫总数量 c[i]11135每月卵新增数量 r[i]02226

按照样例中 z = 8 z=8 z=8，我们也可以得到下表，样例答案 c[8] = 37 就是这样来的。

月份0月1月2月3月4月5月6月7月8月每月成虫总数量 c[i]111357132337每月卵新增数量 r[i]0222610142646

下面，我们以 x = 2 , y = 3 , z = 4 x = 2,y=3,z = 4 x=2,y=3,z=4 为例，再次模拟。

首先，在 0 - x-1 月，第一对成虫是不产卵的，所以 c [ i ] ≡ 1 , r [ i ] ≡ 0 c[i] equiv 1,r[i] equiv 0 c[i]≡1,r[i]≡0，即：

在第 0 月时， c [ 0 ] = 1 , r [ 0 ] = 0 c[0] = 1,r[0] = 0 c[0]=1,r[0]=0在第 1 月时， c [ 1 ] = 1 , r [ 1 ] = 0 c[1] = 1,r[1] = 0 c[1]=1,r[1]=0 月份0月1月2月3月4月每月成虫总数量 c[i]11每月卵新增数量 r[i]00

在 x 月，第一对成虫开始产卵，且产了 y 对卵， c [ x ] = 1 , r [ x ] = y c[x] = 1,r[x] = y c[x]=1,r[x]=y，即：

在第 2 月时， c [ 2 ] = 1 , r [ 2 ] = 3 c[2] = 1,r[2] = 3 c[2]=1,r[2]=3 月份0月1月2月3月4月每月成虫总数量 c[i]111每月卵新增数量 r[i]003

在 x+1 - z 月，递推关系满足上述递推方程，有：

在第 3 月时， c [ 3 ] = c [ 2 ] + r [ 1 ] = 1 , r [ 3 ] = c [ 3 − 2 ] ∗ 3 = 3 c[3] = c[2] + r[1] = 1,r[3] = c[3 - 2] * 3 = 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 c[4] = c[3] + r[2] = 4,r[4] = c[4 - 2] * 3 = 3 c[4]=c[3]+r[2]=4,r[4]=c[4−2]∗3=3 月份0月1月2月3月4月每月成虫总数量 c[i]11114每月卵新增数量 r[i]00333

至此，整道题目的逻辑关系基本理清。✅

在梳理完了递推关系后，我们尝试书写代码（这题对于初学者来说确实麻烦，但是对逻辑思维是很好的锻炼）

我们从上面的过程入手，边界条件 就比较容易确定。显然，总过程分为 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; } 123456789101112131415

这样，我们就完成了本题的核心代码（恭喜）

其实，在对 x x 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 i - 2 > 0 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; ++i) { r[i] = c[i - x] * y; c[i] = c[i - 1] + r[i - 2]; } cout << c[z] << endl; return 0; } 1234567891011121314151617181920212223242526272829303132

在这里插入图片描述