费波拉切数列是一个经典的数学问题,在好多笔试题中会有出现,斐波拉切的数列是这样的:【1 1 2 3 5 8 13 21 …】由于它过于经典，我们就不再费神去讨论它。我们将这个数列映射到兔子的问题上可以这样描述：有一对兔子，一岁后性成熟，之后每年生一对小兔子，小兔子亦然。{插入：“5+8=13”的理解方式：我们将8看作去年的兔子基数，将5看作是具备生育能力的自然兔子增长率较容易。}
但是最近见到了一个这样的版本：有一对大兔子，每年生一对小兔子，小兔子三年后性成熟，之后每月生一对小兔子。求N年后的兔子对数。{我们假设首年为第一年，求的是第N年年末的兔子数目。}
很明显这个问题为大家挖了一个陷阱： 大兔子和小兔子的生育能力是不一样的， 首先我们先从宏观角度来考虑要认清楚这其实是一个斐波拉切数列问题的变种，与经典问题进行比较的话需要把问题细化分解一下， 大兔子先和小兔子分开考虑，直觉告诉我们先考虑大兔子是比较简单的，但无论从哪个方面入手先要搞清楚的是要如何解决这个问题，关于斐波拉切数列是有现成的公式的，但是在编程题内我们都是用循环穷举出第N年的兔子数目，我们并不想把它纯数学化现在只考虑穷举循环这条路径。
斐波拉切问题一个很好的切入点是考虑每个时间节点的增长数，我们将增长数搞清楚再加上本年度的兔子基数就很容易可以解决问题。在考虑增长数的时候我们才将本问题细化到大兔子和小兔子这两个拥有不同生育能力的种群。（1）对大兔子来说其生育能力很稳定，每年增加一对。【但事实上大兔子的生育能力才是我们不能把这个问题直接转化为斐波拉切数列问题的关键，现在我们将其进行隔离能达到反而能更好地理解这个问题】（2）小兔子较为复杂，一是要考虑其性成熟的情况，二者要注意其增长模式是以月为单位的。在考虑其增长模式时，要注意一下时间节点：在前三年中小兔子仅为大兔子直系所生的三对兔子，在第三年这个时间节点上大兔子的大阿哥和大格格（贵圈好乱）达到性成熟之后我们将以月为单位讨论这个问题而每月增加的数目其实是在3年即36个月之前的兔子基数（在考虑基数时我们不去考虑大兔子却需要考虑大兔子的直系子女）决定的。这样我们的问题其实就基本上解决了。
我们先将时间定格到年这个单位，其前三年的数值模式为1 2 3三年之后我们要细化到月，在第37个月，其增长的数字为36个月前的兔子基数1。这样可以递推得到本月应该增加的小兔子数。将大兔子和小兔子的增长模式进行整合后可以得到最总结果：第N个月的小兔子数目=第（N-1）个月的兔子数目加上第（N-36）个月的小兔子数目。
现在我们讨论一下关于存储的问题，从解决此题目的角度来讲因为其计算跨度达到36个月则我们需要的最小空间为36个单位，因为是做查询比较多，这里用数组是最合适的，但是这样也有缺点：无法记录中间结果。如果使用面向对象类的语言，这里建议使用诸如ArrayList之类的对象或容器进行存储。
说了这么多该总结一下了：本问题求解可以分为两大块【1】初始阶段（小兔子还没有性成熟的阶段，类似于斐波拉切数列问题的前两个1）该阶段的兔子数列模式为{1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3}【2】迭代增长阶段，我们姑且称之为真正的斐波拉切阶段：初始值设置好之后就可以利用公式斐波拉切和他的兔子
斐波拉切和他的兔子 迭代计算具体月份的兔子数目即可。当然我们这里仅仅考虑的是小兔子生育小兔子的问题并没有将我们分解出的大兔子及大兔子所产生的直系子女考虑进来。加入进来之后我们要做一个判断，如果是年初的那个月份除了有斐波拉切和他的兔子
斐波拉切和他的兔子之外我们还要加入大兔子所生产的直系子女一对，另外所有的兔子总和数都要加上1表示大兔子的对数。整个计算过程可以用以下伪代码表示：
Cin >> N //表示具体月份
If(N<=36){ //表示出于初始阶段
Return (int)((N-1)/12) +2;
}else{ //表示进入了真正的斐波拉切迭代阶段
Int A[36]= {1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3};
int i=0;
for(i=0;i
i=i6;
if(i>=1){
a[i]+=a[i-1]; //普通模式
}else{
a[i]+=a[36]+1; //i=0的时候这里是年初的第一个月所以要加1
}
}
Return a[i]+1; //这里的加1是加的老兔子的对数
}
问题解决了但是着这样真的是最优的吗？
现在考虑一下我们的时间都是以月份为计数单位的，但是题目其实仅要求返回年末的兔子数目，我们对月份的考虑仅仅是为了满足我们对斐波拉切数列的计算模式的依赖，如果我们将这个月份加以整合以年为单位进行考虑的时候又会怎么样的？
我们为了避免麻烦还是将大兔子及大兔子的直系子女分出来考虑，在前三年兔子总对数分别为2,3,4。在第四年年初大兔子会生一对小兔子，首对小兔也会生一对，那么年内的增长模式到底是个什么情况呢，我们不妨把前七年的兔子数目列举一下：2,3,4,5+12，6+12*2；7+12*3；第七年的兔子数开始步入复杂计算模型，我们将第七年的十二个月分开进行考虑：第一到第十二月的新增兔子数分别为：4+1,5,6,7,8,9,10,11,12,13,14,15。总增加数为（4+15）*12/2+1=115,
这种方式比较复杂，而且每三年会更换一次增长模式，可惜的是我们仅从存储的年份及年份内的兔子增长数是很难判定下一阶段的兔子增长模式的，所以由于此方法过于复杂，我放弃，大家如果谁有兴趣可以试一下。
二、进阶考虑：
如果在此问题的基础之上加入死亡率与兔子寿命的限制将会怎么样呢？
我们假设小兔子抵抗力比较低每年新增的兔子会有20%的折损（出现半只时采用四舍五入的方式计算）一只兔子最多活10年。
首先考虑折损这个问题，在我们之前的算法基础之上并不是很难实现，但是一只兔子活十年这件事情就会让我们很郁闷，这里可以我们可以提供两种方式解决【1】记录每一年的兔子数目做一个二维数组当算法运行到十年以上时每一次都要减去十行之前对应的兔子总数表示兔子已死，这样我们的算法空间复杂度变为了至少为36*10；【2】但是用面向对象的语言时可以为兔子建立对象类，每次判断兔子的数目时检测一下其年龄（但是这种无论是时间复杂度还是空间复杂度都会比第一种方法高出很多，但有一点就是算法设计起来简单）。也算是用计算机弥补我们智商缺陷的一种方式。 |
|
收藏
淘帖
踩
