信息学奥赛一本通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，是可以过的。

【题解代码】 解法1：递推

#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】昆虫繁殖-创新互联
文章URL：http://dzwzjz.com/article/ddsijs.html