华为机试题37-统计每个月兔子的总数

题目描述：

有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。

例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。

一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？

数据范围：输入满足：1≤n≤31

解题思路：

利用递归或者动态规划都可以，动态规划效率更高，笔者选择的是递归方法。

假设第n个月的兔子总数为rabbit(n)，先来分析一下rabbit(n)是由哪些兔子构成的，肯定只有两部分构成，一部分兔子是第n-1个月的兔子总数rabbit(n-1)，一部分是第n-2个月的兔子总数rabbit(n-2)，这些兔子不论是老兔子还是两月份的中兔子，或是新兔子，在第n个月，都是老兔子，都能生，则rabbit(n)=rabbit(n-1)+rabbit(n-2).

了解这些后，写代码就很简单了

#include 
int rabbit(int n)
{
    if(n<3)
    {
        return 1;
    }
    else
    {
        return rabbit(n-1)+rabbit(n-2);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",rabbit(n));
    return 0;
}