神奇的兔子序列

14天阅读挑战赛

1．问题分析

  不妨拿新出生的1对小兔子分析。

  第1个月，小兔子①没有繁殖能力，所以还是1对。

  第2个月，小兔子①进入成熟期，仍然是1对。

  第3个月，兔子①生了1对小兔子②，于是这个月共有2（1+1=2）对兔子。

  第4个月，兔子①又生了1对小兔子③，因此共有3（1+2=3）对兔子。

  第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤，因此共有5（2+3=5）对兔子。

  第6个月，兔子①②③各生下了1对小兔子，新生的3对兔子加上原有的5对兔子，这个月共有8（3+5=8）对兔子。

……

  为了让表达更清楚，可用图示分别表示新生兔子、成熟期兔子和生育期兔子，兔子的繁殖过程如图1-9所示。

  图1-9　兔子的繁殖过程

  这个数列有如下十分明显的特点：从第3个月开始，当月的兔子数 = 上月兔子数 + 当月新生兔子数，而当月新生兔子数正好等于上上月的兔子数。因此，前面相邻两项之和便构成后一项，换言之：

                当月的兔子数 = 上月兔子数 + 上上月的兔子数

  斐波那契数列如下：

1，1，2，3，5，8，13，21，34，…

  递归表达式如下：

  那么，该如何设计算法呢？

2．算法设计

首先按照递归表达式设计一个递归算法，见算法1-8。

//算法1-8 
int Fib1(int n){
    if(n==1||n==2)   
    return 1;
    return Fib1(n-1)+Fib1(n-2);
}
1
2
3
4
5
6

算法设计完之后，需要考虑如下3个问题。

● 算法是否正确？

● 算法复杂度如何？

● 算法能否改进？

3．算法验证分析

  上面需要考虑的第1个问题毋庸置疑，因为算法1-8是完全按照递推公式写出来的，所以正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需的基本操作次数，那么：

n=1 时，T(n)=1；
n=2 时，T(n)=1；
n=3 时，T(n)=3；//调用Fib1(2)和Fib1(1)并执行一次加法运算（Fib1(2)+Fib1(1)）
1
2
3

  因此，当n>2时需要分别调用Fib1(n−1)和Fib1(n−2)并执行一次加法运算，换言之：

n>2时，T(n)=T(n-1)+T(n-2)+1；
1

  递归表达式和时间复杂度T(n)的关系如下：

  由此可得：

  那么如何计算F(n)呢？方法有两种。

  其中一种是画出F(n)的递归树，如图1-10所示。观察图1-10，递归树的左侧从n每次递减1，直到2为止，左侧树高h1=n−1；递归树的右侧从n每次递减2，直到2或1为止，右侧树高h2=n/2。高度为h2的部分是满二叉树，这部分节点数为2h2−1，即2n/2−1，总节点数大于2n/2，每个节点都需要计算，时间复杂度是指数阶的。

  图1-10　F(n)的递归树

  另一种是求出斐波那契数列的通项公式：

  由于，因此这是一个指数阶的算法！

  算法1-8的时间复杂度属于爆炸增量函数，这在算法设计中是应当避开的，那么算法1-8能不能改进呢？

4．算法改进

  斐波那契数列中的每一项（开头的两项除外）是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值，时间复杂度会不会更低一些呢？不妨用数组试试看，见算法1-9。

//算法1-9 
int Fib2(int n){  
    int *F=new int[n+1];//定义一个长度为n+1的数组，空间尚未使用
    F[1]=1；
    F[2]=1;
    for(int i=3;i<=n;i++)
        F[i]=F[i-1]+F[i-2];
    return F[n];
}
1
2
3
4
5
6
7
8
9

  很明显，算法1-9的时间复杂度为О(n)。因为算法1-9仍然遵从F(n)的定义，所以正确性没有问题，但时间复杂度却从算法1-8的指数阶降到了多项式阶，算法效率有了重大突破！

  算法1-9使用了一个辅助数组记录中间结果，空间复杂度也为О(n)。其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此，我们可以采用迭代法进行算法设计，见算法1-10。

//算法1-10 
int Fib3(int n){
    if(n==1||n==2)   
         return 1;
    int s1=1; //用s1和s2记录前面的两项
    int s2=1;
    for(int i=3;i<=n;i++){
         int tmp=s1+s2;
         s1=s2;
         s2=tmp;
    }
    return s2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

  算法1-10使用了几个辅助变量进行迭代，时间复杂度为О(n)，但空间复杂度降到了О(1)。

  问题的进一步讨论：能不能继续降阶，使算法的时间复杂度更低呢？

  实质上，斐波那契数列的时间复杂度还可以降到对数阶О(logn)，有兴趣的读者可以查阅相关资料。想想看，把一个算法从指数阶降到多项式阶，再降到降到对数阶，这是一件多么振奋人心的事！

5．惊人大发现

  科学家经研究，在植物的叶、枝、茎等排列中发现了斐波那契数！例如，在树木的枝干上选一片叶子，记为数1，然后依序点数叶子（假定没有折损），直至数到与那片叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中，叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意为叶子的排列）比。多数植物的叶序比呈现为斐波那契数的比。例如，蓟的头部具有34条顺时针旋转和21条逆时针旋转的斐波那契螺旋，向日葵的种子的圈数与种子数、菠萝的外部排列等同样具有这样的特性，如图1-11所示。

图1-11　斐波那契螺旋（图片来自网络）

  观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们的花瓣数为斐波那契数：3，5，8，13，21，…，如图1-12所示。

图1-12　植物的花瓣数（图片来自网络）

  树木在生长过程中往往需要一些“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段时间（如一年）后长出一个新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年新生的枝在次年“休息”。这样，一株树木各个年份的枝丫数便构成斐波那契数列，这一规律就是生物学上著名的“鲁德维格定律”。

  这些植物懂得斐波那契数列吗？并非如此，它们只是按照自然规律才进化成这样。这似乎是植物排列种子的“优化方式”——能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5°，这个角度被称为“黄金角度”，因为它和整个圆周（360°）之比是黄金分割数0.618的倒数，而这种生长方式就导致斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89条，甚至144条。1992年，两位法国科学家通过对花瓣形成的过程进行计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列的规律长出花瓣。

  有趣的是，这样一个完全由自然数组成的数列，通项公式却是用无理数来表达的，而且当n趋向于无穷大时，斐波那契数列中的前一项与后一项的比值越来越逼近黄金分割数0.618：1÷1=1，1÷2=0.5，2÷3=0.666，…，3÷5=0.6，5÷8=0.625，…，55÷89=0.617977，…，144÷233=0.618025，…，46368÷75025=0.6180339886……

  越到后面，这些比值越接近黄金分割数：

  斐波那契数列起源于兔子数列，这个现实中的例子让我们真切地感到数学源于生活。在生活中，我们需要不断地透过现象发现数学问题，而不是为了学习而学习。我们学习的目的是满足自己对世界的好奇心，如果你能怀着这样一颗好奇心，或许世界会因你而不同！当斐波那契通过兔子繁殖告诉我们这种数学问题的本质——随着数列项的增加，前一项与后一项之比越来越逼近黄金分割数0.618时，我被彻底震撼，因为数学可以表达美，这是数学令我们叹为观止的地方。当数学创造出更多的奇迹时，我们会发现数学在本质上是可以回归自然的，这样的事例让我们感受到数学的美，就像黄金分割、斐波那契数列，它们如同大自然中的一朵朵小花，散发着智慧的芳香……