2.4　案例2：兔子问题与Fibonacci数列

【背景知识】

意大利数学家斐波那契（Fibonacci）在他的著作《计算之书》里提出了一个问题：“假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生下一对小兔，一年内没有发生死亡，那么一对刚出生的兔子，在一年内繁殖成多少对兔子？”由该繁衍规律得到的每个月兔子的数量组成了Fibonacci数列，也称为“兔子数列”，如图2.2所示。

Fibonacci数列增长速度非常快。19世纪中期的澳大利亚野兔成灾事件体现了真实版的“兔子数列”惊人的增长速度。当时英国人为了满足自己的狩猎爱好，把欧洲野兔引入澳大利亚。由于澳大利亚气候温暖、牧草丰富，为兔子提供了良好的生存条件，加上澳大利亚本土缺乏猛禽、黄鼠狼等兔子的天敌，兔子开启了斐波那契数列式的增长，当时澳大利亚的生态遭到了严重破坏，继而开始了人兔大战……

Fibonacci数列的前几项为1、1、2、3、5、8、13、21、34、55、89。仔细观察这个数列发现，第1项和第2项为1，此后每一项都是前2项的和。

在图2.2中，为什么从第3个月开始，每个月的兔子对数等于前两个月兔子对数之和？这是因为，每个月的兔子对数包括大兔子对数和小兔子对数，上个月每一对兔子无论是大兔子还是小兔子，到了这个月一定是大兔子；而上上个月每一对兔子无论是大兔子还是小兔子，到了这个月一定会生下一对小兔子。

【题目描述】

输入 n 值，输出Fibonacci数列的第 n 项，该数列前5项为1、1、2、3、5。

【输入描述】

输入占一行，为 n 的值，1≤ n ≤40。

【输出描述】

输出占一行，为Fibonacci数列第 n 项的值。

注意，Fibonacci数列增长速度非常快，第46项为1836311903，第47项就超出int型数据的取值范围了。

【题目分析】

可以采用递推方式递推出Fibonacci数列的每一项。如图2.3所示，用 f ₁ , f ₂ , f ₃ 表示连续的3项，每一轮递推， f ₃ = f ₁ + f ₂ ，就得出新的一项，然后更新 f ₁ 和 f ₂ 的值， f ₁ 更新为 f ₂ ， f ₂ 更新为 f ₃ ；下一轮循环，因为 f ₁ 和 f ₂ 的值已经更新了，所以再递推出 f ₃ ，又是新的一项。

在图2.3中， f ₁ , f ₂ , f ₃ 就像一只蠕虫的三节一样，蠕虫每一轮向前爬一格。爬一格后， f ₁ 就对应到之前 f ₂ 的位置， f ₂ 就对应到之前 f ₃ 的位置。

代码如下：

#include <iostream>
using namespace std;
int main( )
{
    int n;  cin >>n;
    int f1 = 1, f2 = 1, f3;                     // f1和f2的初始值均为1
    if(n == 1 or n == 2)  cout <<1 <<endl;
    else{
        for(int i=3; i<=n; i++){               // 递推出第3～n项
            f3 = f1 + f2;
            f1 = f2;                       // 这行代码不能和下面一行代码交换位置
            f2 = f3;
        }
        cout <<f3 <<endl;
    }
    return 0;
}

其实也可以用两个变量 f ₁ 和 f ₂ 实现Fibonacci数列的递推， f ₁ 和 f ₂ 表示连续的两项，如图2.4所示。为了递推出新的一项，有 f ₂ = f ₁ + f ₂ ，此后 f ₁ 要更新为之前 f ₂ 的值，所以要事先用临时变量 t 保存 f ₂ 的值，即 t = f ₂ ，最后才能把 t 的值赋给 f ₁ ，即 f ₁ = t 。这3条关键的代码不能交换顺序。

代码如下： WisuzwFLAhwi7yIJsdzz1kmikCtxH5VsZIk44uT8AKMpCd98jd3kQsnx/GO+mArU

#include <iostream>
using namespace std;
int main( )
{
    int n;  cin >>n;
    int f1 = 1, f2 = 1, t;                    // f1和f2的初始值均为1
    if(n == 1 or n == 2)  cout <<1 <<endl;
    else{
        for(int i=3; i<=n; i++){               // 递推出第3～n项
            t = f2;                 //这3行代码不能交换顺序
            f2 = f1 + f2;
            f1 = t;
        }
        cout <<f2 <<endl;
    }
    return 0;
}