斐波那契数列介绍

Q：斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？
A：因为斐波那契数列在数学和生活以及自然界中都非常有用。
1.　斐波那契数列 概念引入

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

数学上，斐波那契数列以递归的形式进行定义：
F0=0 F1=1 Fn=Fn−1+Fn−
先搞懂经典算法再说吧；
还有几种，以后发达了，在搞懂。
观察数列可得，除了第一项和第二项，所有的数列的值都是前一项和前一项的前一项的加和，转换成函数也就是f(n) = f(n-1) + f(n-2)

 int f1(int n) {
        if(n < 1) {
            return 0;
        }else if(n == 1 || n == 2) {
            return 1;
        }
     
        return f1(n-1) + f1(n-2);
    }

显然，递归n次，时间复杂度O(2^n)，太恐怖，所以，必须优化。

先来开看看“兔子数列”以及其他数学应用场景！！
1. 1　兔子数列

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

1.2　排列组合

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?

2.1　兔子繁殖问题

斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

我们不妨拿新出生的一对小兔子分析一下：

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

两个月后，生下一对小兔对数共有两对

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对

－－－－－－

依次类推可以列出下表：
经过月数 1 2 3 4 5 6 7 8 9 10 11 12 …
幼仔对数 1 0 1 1 2 3 5 8 13 21 34 55 …
成兔对数 0 1 1 2 3 5 8 13 21 34 55 89
总体对数 1 1 2 3 5 8 13 21 34 55 89 144

幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

总体对数=本月成兔对数+本月幼仔对数

可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：

前面相邻两项之和，构成了后一项。
2.2　排列组合
2.2.1　跨楼梯组合

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不同的走法?

这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……

1，2，3，5，8，13……所以，登上十级，有89种走法。
2.2.2　掷硬币不连续情形

一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？

答案是:
（1/√5)∗(1+√5)/2−(1−√5)/2=144

（1/√5)∗(1+√5)/2−(1−√5)/2=144
…