求个题目的算法。

来源：百度知道 编辑：UC知道 时间：2024/05/29 12:10:33
题目是有一对鸡，二个月成为大鸡，三个月后成为老鸡并可生出一对小鸡，接着就每个月都生出一对小鸡。而小鸡三个月后又可以生一鸡小鸡，求15个月后总共有几对小鸡？
麻烦把解题的思路和算法说清楚些，谢谢。

int f(int n) /* n为月份， 1月，2月，。。。。 */
{
if (n < 3)
return 1;
else
return f(n-1) + f(n-2);
}

函数f(15)的返回值即答案。

这里面图文并茂
http://blog.chinaunix.net/u/16292/showart_496723.html

t(n)表示第n个月有多少对鸡，要求出它，分成两部分。
首先，n-2那个月，有t(n-2)对鸡，这些鸡都是能生小鸡的，所以原封不动复制一份。
然后n-1那个月的鸡还在
所以t(n)=t(n-1)+t(n-2)，t(1)=1, t(2)=1
第15个月的小鸡都是第13个月的鸡生的，因为第14个月出生的鸡还不能生，到了第15个月也不是小鸡了。所以15个月后有t(13)对小鸡。
t(13)的数值可以从t(1),t(2)推算出来