主要内容 #

1. 兔子繁殖问题
2. 算法分析
3. 参考程序
4. 上台阶问题

1. 兔子繁殖问题 #

把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问第n个月后养殖场中共有多少对兔子。
第1个月：一对新兔子r1。用小写字母表示新兔子。
第2个月：还是一对新兔子，不过已经长大，具备生育能力了，用大写字母R1表示。
第3个月：R1生了一对新兔子r2，一共2对。
第4个月：R1又生一对新兔子r3，一共3对。另外，r2长大了，变成R2
第5个月：R1和R2各生一对，记为r4和r5，共5对。此外，r3长成R3。
第6个月：R1、R2和R3各生一对，记为r6～r8，共8对。此外，r4和r5长大。
……

2. 算法分析 #

把以上这些数排列起来：1，1，2，3，5，8，……，事实上，可以直接推导出来递推关系f(n)=f(n-1)+f(n-2):第n个月的兔子由两部分组成，一部分是上个月就有的老兔子f(n-1)，一部分是上个月出生的新兔子f(n-2)(第n-1个月时具有生育能力的兔子数就等于第n-2个月兔子总数)。根据加法原理，f(n)=f(n-1)+f(n-2)。
如下图所示，黑色的点表示具有繁殖能力的兔子，白色的点表示刚出生的兔子，不具有繁殖能力。

3. 参考程序 #

#include < iostream >
using namespace std;
int main(){
    int f0 = 1, f1 = 1, f2;
    int n;
    cin >> n;
    //前两个月结果都是 1
    if( n <= 2){
        cout << 1 << endl;
        return 0;
    }
    //从第三个月开始计算
    for(int i = 3; i <= n; ++i){
        f2 = f1 + f0;
        f0 = f1;
        f1 = f2;
    }
    cout << f2 << endl;
    return 0;
}