奇趣Fibonacci数列
Fibonacci数列源起一个我们现在看起来非常“幼稚”的问题：开始时有一对兔子，每对兔子每个月繁殖一对，假设兔子没有死亡，这样历经了n个月，兔子有了多少对呢?
很容易把这个问题用数学语言来表达出来：
设第n个月有F(n)只兔子，依题意有
F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2)
看上去就是一个很简单的数列，又有什么玄机呢？
首先从直观的感觉上来说，似乎这个数列增长速度并不是很快，就是加法嘛，怎么加也就那样了，但是这种感觉是大错特错的！我们可以利用下面的程序运行一下：
#include <iostream>
#include <cmath>
using namespace std;
int F[50];
int main()
{
int i;
F[0]=F[1]=1;
for(i=2;;i++){
F[i] = F[i-1]+F[i-2];
if(F[i]
}
int cnt=i;
for(i=0;i<45;i++)
{
cout << F[i] << endl;
}
system("pause");;
}
最后一项是n=45时的情况，已经是10^9了，增长速度是惊人的！学过生物的人肯定知道有一个在没有生存压力的情况下种群“J”字形增长图，没错，就是这个模型。
于是大家就会思考了，那个图好像是指数型增长，难道说Fibonacci数列也是指数型增长的吗
我们来做一个实验，用Matlab一下，画出log(Fn)的图像
几乎是一条完美的直线，看来Fibonacci数列确实是呈指数形式增长的
虽然完美，但在左下角依然有一小小的显然不成线性的部分，这说明Fibonacci数列毕竟不是指数序列，而是一个混合体。
事实上，这个数列的通项公式是1/√5*(((1+√5)/2)^n-((1-√5)/2)^n),有人说，这是什么破公式，一点也不完美，但是仔细看就会发现(1+√5)/2是黄金分割比，而(√5-1)/2是它的倒数，为什么我们求出来的log函数是个线形的呢，因为((√5-1) /2)^n)->0,主部是((1+√5)/2)^n就是一个指数型的函数
在现实世界中到处可以见到Fibonacci数，比如某某花5瓣，某某花8瓣又有13瓣的，我都不感兴趣了，对于分形中的Fibonacci倒是很有兴趣，却没有探究，以后吧
Fibonacci数列之提高篇：
如何计算Fibonacci数列的通项公式？如果要证明的话就用数学归纳法好了，要是计算的话，有一种特征值理论，具体也可以从母函数（自组合数学）理论中推出，先不写这些理论了，具体应用很简单：
F(n)=F(n-1)+F(n-2) n-2最低项看成常数项，n-1看成线性项，n看成二次项，得到特征方程
x^2=x+1 ==> x=(1+√5)/2 | (-√5+1)/2,于是通项可以写成F(n)=a((1+√5)/2)^n+b*((-√5+1)/2)^n,再F(0)=F(1)=1代入就可以得到a=b=1/√5,得到了证明
在计算机领域，我们虽然有了通项公式，但是根号肯定意味着舍入误差，所以一般来说并不直接用通项公式这种方法，代之的是以下的矩阵运算
相对而言，两个公式都要计算n次方，所以应用二分法时间复杂度都是O(logn)，但是第二个精度就高了
有一个经典的证明（至少我认为）是GCD（利用Euclid算法）的时间复杂度O(logn)，这个证明只有数学的美感，而不是计算机科学看起来那么繁冗，是我在某本《代数》上看到的，首先介绍GCD算法（具体GCD我在这里就不说了，如果谁有需要我改天再写一篇文章，其实GCD和Fibonacci列一样不那么简单，也是一门科学啊）：
function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)
对于a，b的最大公约数，如何求？这个算法告诉我们：先找到a，b中的较大者为a，较小为b，计算a mod b = c,再把b赋给a，c赋给b，判断b是否为0，是就返回a，否则重复上述过程即可
下面是证明：由求GCD的过程，我们可以构造一个序列a,b,a mod b b mod(a mod b)….记为{An}
由于a总是大于等于b的，（如果等于就已经找到了，易证）那么我们可以得到一个不等式a-b>=(a mod b),这个还不是很明显，换一种写法
A(n)-A(n-1)>=A(n-2) ==> A(n)>=A(n-1)+A(n-2)
!!!简直就是不知道首项的Fibonacci数列，只不过把=换成>=，那好了，它比Fibonacci数列增长还要快，所以最坏情况不过O(logn)了，而且观察可见如果{An}就是一个Fibonacci数列，每一次递推都是=!所以Fibonacci数列就是最坏情况，也达到了O(logn)
综上，证毕
Fibonacci数列之精通篇：（我也不是很精通。。。所以说这一部分希望牛人进行补充）
本来今天要查一些资料写的更充实些的，但是由于我被问了几个我几乎答不上来的问题。。。于是现在就两点多了，困死我了，睡觉去。想起什么再加
希望这篇文章老少皆宜，能为大家提供些许帮助！
另注：本文原创，所以我就挑我觉得重要的写，比如Fibonacci其人就不介绍了。。