昆虫繁殖问题 #

1. 昆虫繁殖问题介绍
2. 昆虫繁殖问题分析
3. 昆虫繁殖问题的实现

收获 #

学完本节内容，可以更深刻了解递推思想的使用。

昆虫繁殖问题介绍 #

问题描述:
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。
假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。

昆虫繁殖问题分析 #

将问题进行拆解，发现有两组具有相关性的变量：（1）成虫 （2）卵
关于成虫的参数：成虫每过x个月产y对卵；
关于卵的参数：卵每2个月长成成虫；
分别建立关于成虫和卵的数量储存列表g[],f[]。可以由题递推出一个通项解的变换公式：

f[i]=y*g[i-x]
g[i]=g[i-1]+f[i-2]

昆虫繁殖问题的实现 #

python实现代码如下：

#定义f为卵的数量，g为虫的数量
x=1;y=2;z=8
g=[1]*(z+2)#定义储存虫在某个月的数量列表,进行初始化
f=[0]*(z+2)#定义储存卵在某个月的数量列表，进行初始化
g[1]=1
f[1]=0
for i in range(x+1,z+2):#月份从x开始，z结束 区间[x,z]->[x+1,z+1],range(x+1,z+2)
    f[i]=y*g[i-x] #第i-x月的成虫在x个月后产下y个卵
    g[i]=f[i-2]+g[i-1] #第i个月的成虫等于第i-1个月的成虫数加上第i-2个月的卵
print(g[z+1])

小结 #

结合昆虫繁殖问题的应用，进一步理解递推算法的思想
掌握昆虫繁殖问题的代码实现

习题 #

1. 习题1：尝试画出虫和卵的数量列表关联性
2. 习题2：求解120个月后的成虫数量