P4750 兔子繁殖问题（入门）

解题思路

这个故事说的是一对"兔子夫妻"的家族壮大过程。年初的时候，围栏里只有 1 对小兔子。按照题目规定：小兔子只要长 1 个月就能变成大兔子，而大兔子每个月都会生出一对新的小兔子。我们要算出到年底（也就是第 12 个月底）一共有多少对兔子。

我们可以把每个月底围栏里的兔子对数记下来，看看规律：

• 第 1 个月底：只有年初那 1 对小兔子，共 1 对；
• 第 2 个月底：小兔子长成了大兔子，还没生宝宝，仍然只有 1 对；
• 第 3 个月底：大兔子生出一对小兔子，变成 2 对；
• 第 4 个月底：原来的大兔子又生一对，第 3 个月出生的小兔子也长大了，共 3 对。

你会惊喜地发现：从第 3 个月开始，每个月的对数 = 上个月的对数 + 上上个月的对数。这就是著名的斐波那契数列！用数学式子写就是 f(n) = f(n-1) + f(n-2)，其中 f(1) = 1，f(2) = 1。

为什么这个式子是"对"的呢？可以把问题反过来想：第 n 个月底的对数，等于"上个月底就已经在的对数"加上"这个月刚刚出生的小兔子对数"。而这个月出生的小兔子，正好是上上个月底那些兔子生出来的，数量就等于 f(n-2)。所以 f(n) = f(n-1) + f(n-2)。

这道题输入为空，我们只需要在程序里递归求出 f(12) 并输出即可。递归函数有两个"出口"：n 等于 1 或 2 时直接返回 1，其他情况就调用自己，把规模变小。最终到年底一共是 144 对兔子。

参考代码

// 兔子繁殖问题：年初1对小兔，小兔1个月长大成大兔，大兔每月生1对小兔，递归求到年底对数
#include <iostream>
using namespace std;

// 递归求第n个月底共有多少对兔子：f(n)=f(n-1)+f(n-2)
int f(int n) {
    if (n == 1) return 1;   // 第1个月底：只有年初那1对小兔子
    if (n == 2) return 1;   // 第2个月底：小兔刚长成大兔，还没生小兔，仍1对
    return f(n - 1) + f(n - 2);   // 上个月的总对数 + 这个月新出生的小兔对数
}

int main() {
    cout << f(12) << endl;   // 年初到年底正好12个月
    return 0;
}

复杂度分析

递归函数 f(n) 会调用 f(n-1) 和 f(n-2)，调用关系像一棵树一样向下展开，如果不做优化，总共大约要调用 2^n 次。这里 n 只有 12，2^12 = 4096 次，运行时间 O(2^n) 完全没问题。空间上，递归的最大深度是 n，也就是 12 层，占用 O(n) 的栈空间。程序最后输出 f(12) = 144，这就是到年底围栏里兔子的对数。