信息学奥赛一本通1312：【例3.4】昆虫繁殖-创新互联
ybt 1312：【例3.4】昆虫繁殖
附加条件：该题结果可以由long long类型表示
该题“每对成虫过x个月产y对卵”这句有误，实际应该为“每对成虫过x个月每个月产y对卵”，一本通书第五版P215这道题就是这样写的。OJ抄录时少了“每个月”三个字，导致理解困难。
【题目考点】 1. 递推 【解题思路】首先要理解题意
该题中指说的虫无论是题目还是结果，都是以“对”为单位的，不涉及“一对是两个”这种换算。
我们认为将虫子分为三种形态：卵，幼虫（不能产卵），成虫（可以产卵）
题目中每对卵要过2个月长成成虫，每对成虫过x个月每个月产y对卵这句话应该这样理解：
假设这句话中x为3，y为1，我们可以假定有以下具体场景
一对成虫在1月初产了一对卵，这对卵过2个月，在3月初变为一对幼虫，再过3个月（也就是x个月），在6月初变为一对成虫，这对成虫在6月初产了一对卵。
这对新的卵过了2个月在8月初变为幼虫，在11月初变为成虫，并产卵。
我们把不能产卵的虫称为幼虫，这样更方便理解。
设数组a与b，a[i]表示第i个月有多少对虫，b[i]表示第i个月出生的卵的数量。
- 现在初始状态下只有一对刚刚从卵变成的幼虫，要在x个月之后才能开始第一次产卵。
假设x是3，写出具体例子理解一下：
1月初有一对刚刚从卵变成的幼虫，3个月（也就是x个月后）在4月初这对幼虫变为成虫，并产卵。
幼虫在x个月后，也就是第x+1月才能开始产卵。那么前x个月只有一对虫，对所有i满足
1
≤
i
≤
x
1\le i\le x
1≤i≤x，有a[i]=1，b[i]=0。
- 类比兔子繁殖（斐波那契数列）问题中：当月的成年兔子可以分为上个月就已经是成年的兔子，和这个月刚刚成年的兔子。
考虑某个月的虫，可以分为上个月就已经有的虫（成虫或幼虫），和这个月刚刚从卵变成的幼虫。
第i个月的上个月的虫子数量为a[i-1]。
假设虫卵在第m月出生，那么这些卵会在第m+2月变为幼虫。反过来想，第i个月的刚刚从卵变成的幼虫，实际是第i-2月出生的虫卵。第i-2月出生的虫卵数量为b[i-2]，所以这部分幼虫的数量为b[i-2]。
因而有a[i] = a[i-1] + b[i-2]; - 假设第m月卵变为幼虫，那么第m+x月幼虫变为成虫。反过来想：第i月的成虫，最晚是在第i-x月从卵变为幼虫。第i-x月后再从卵变成的幼虫，在第i月必然是幼虫，不是成虫。。
第i-x月的成虫在第i月当然还是成虫，第i-x月的幼虫在第i月夜变成了成虫，第i个月的虫也不可能来自第i-x月之后变成的幼虫。因此第i个月的成虫就是第i-x月的成虫加幼虫，即第i-x月的总虫数量a[i-x]。
第i个月的产卵数量b[i]，为第i个月的成虫数量乘以y，即b[i] = a[i-x]*y。
题目从第1个月开始，求z个月后的虫子数量，即为求a[z+1] - 考虑结果可能的大小。假设x为1，y为20，a的递推式为
a
i
=
a
i
−
1
+
20
⋅
a
i
−
3
>
20
∗
a
i
−
3
a_i = a_{i-1}+20\cdot a_{i-3} >20*a_{i-3}
ai=ai−1+20⋅ai−3>20∗ai−3，那么当z为50时，求a[z+1]为
a
51
>
20
⋅
a
48
>
2
0
2
⋅
a
45
>
.
.
.
>
2
0
16
⋅
a
3
=
2
0
16
a_{51} >20\cdot a_{48} >20^2\cdot a_{45}>...>20^{16}\cdot a_{3} = 20^{16}
a51>20⋅a48>202⋅a45>...>2016⋅a3=2016，求这个数字的位数:
⌊
2
0
16
⌋
+
1
≈
23
\lfloor 20^{16} \rfloor + 1\approx 23
⌊2016⌋+1≈23。无法用int或long long类型表示。
实际上确实如此，如果输入数据为 1 20 50，将a与b的类型设为double，会得到结果约为 1.38 ∗ 1 0 24 1.38*10^{24} 1.38∗1024，和我们的估算是一致的。 - 只能说该题不够严谨，输入变量范围给定的不够准确。该题实际上如果将a与b的类型设为long long，是可以过的。
#includeusing namespace std;
int main()
{long long a[101], b[101];//a[i]:第i个月有多少对虫 b[i]:第i个月出生的卵的数量
int x, y, z;
cin >>x >>y >>z;
for(int i = 1; i<= x; i++)//前x个月只有第一对幼年虫
{a[i] = 1;
b[i] = 0;
}
for(int i = x + 1; i<= z + 1; i++)//求第z个月后，即第z+1个月
{b[i] = a[i-x]*y;
a[i] = a[i-1]+b[i-2];
}
cout<< a[z+1]<< endl;
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前题目：信息学奥赛一本通1312：【例3.4】昆虫繁殖-创新互联
文章来源：http://ybzwz.com/article/ddsijs.html
