兔子生崽问题

题目：

        兔子生崽问题。假设一对小兔的成熟期是一个月，即一个月可长成成兔，每对成兔每个月可以生一对小兔，一对新生的小兔从第二个月起就开始生兔子，试问从一对兔子开始繁殖，一年以后可有多少对兔子？

条件：

• 小兔成熟期为1个月；
• 每对成兔每个月可以生一对小兔子 ；
• 一对新生的小兔从第二个月起就开始生兔子；

分析：

第一个月： 1对初始兔子(未成熟)                   1对                           

第二个月： 1对初始兔子(成熟)                       1对

第三个月： 1对初始兔子(成熟) + 1对新兔子(初始兔子生)                2对

第四个月： 1对初始兔子(成熟)+1对兔子(3月新兔子成熟)+1对新兔子(初始兔子生)        3对

第五个月： 1对初始兔子(成熟)+1对兔子(3月成熟兔子)+1对兔子(4月新兔子成熟)+1对新兔子(初始兔子生)+1对新兔子(3月成熟兔子生)                      5对

第六个月： 1对初始兔子(成熟)+1对兔子(3月成熟兔)+1对兔子(4月成熟兔)+2对兔子(5月未成熟)+3对新兔子(初始兔子生，3月成熟兔生，4月成熟兔生)          8对

                                                              .............

月份	1	2	3	4	5	6	7	8	9
兔子数	1	1	2	3	5	8	13	21	34

我们不难观察出兔子数是一个菲波那切数列： 

设每个月有F(n)对兔子，那么第n个月的兔子对数可以表示为：

        F(n)=F(n−1)+F(n−2)

其中：

• F(n−1)表示上个月的兔子对数。
• F(n−2)表示两个月前的兔子对数，这些兔子会在本月繁殖出新的兔子。

初始条件为：

• 第一个月 F(1)=1 （只有一对小兔子）。
• 第二个月 F(2)=1 （还是一对兔子，因为只有原来的小兔子长大成为成兔，还没有新生兔子）。

接下来，我们可以逐月计算兔子对数：

• F(3)=F(2)+F(1)=1+1==2
• F(4)=F(3)+F(2)=2+1=3
• F(5)=F(4)+F(3)=3+2=5
• F(6)=F(5)+F(4)=5+3=8
• F(7)=F(6)+F(5)=8+5=13
• F(8)=F(7)+F(6)=13+8=21
• F(9)=F(8)+F(7)=21+13=34
• F(10)=F(9)+F(8)=34+21=55
• F(11)=F(10)+F(9)=55+34=89
• F(12)=F(11)+F(10)=89+55=144

因此，在一年（12个月）之后，将会有144对兔子。

cpp代码：

class Solution
public://递归int CountRbs(int month){if (month == 1 || month == 2)return 1;return CountRbs(month - 1) + CountRbs(month - 2);}//迭代int CountRbs_iteration(int month){vector<int> rabbits;rabbits.resize(month);rabbits[0] = 1;rabbits[1] = 1;for (int i = 2; i < month; i++){rabbits[i] = rabbits[i - 1] + rabbits[i - 2];}return rabbits[month - 1];}
};