編程之美2.9：神奇的菲波那契數列

本文主要是介绍編程之美2.9：神奇的菲波那契數列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

只要是聽說過遞歸，學過一點數據結構的人都聽過這個數列。其實高二數學課上也有，不過那時候我還在受馬克思主義的薰陶，不知編程爲何物。好了，據說這個數列源於一對繁殖能力特別驚人的兔子。
其實這個就是一個遞推公式：

F (n) = ⎧ ⎩ ⎨ 01 F (n - 1) + F (n - 2) n = 0; n = 1; n>=2

$F(n)= \begin{cases} 0 & \mbox {n = 0;}\\ 1 & \mbox {n = 1;} \\ F(n-1)+F(n-2) & \mbox{n>=2} \end{cases}$
一般學校都是在將遞歸時用這個當例子，這當然好。面試提也會考到這道題，Facebook有次就靠到了。不過你要是幹用遞歸寫，你也不用進行下一輪面試了。原因只有一個，太慢！！！重複計算太多！！
你看，如果要求F(5)，則計算F(4)和F(3)，計算F(4)呢，又要再次計算一下F(3)，當然慢。而且函數調用還要保存棧指針，傳遞參數等。
比較好一點的人可能想到用個一維數組。這樣就可以把複雜度降低到

O(n) $O(n)$ 了，我也在這裏獻醜了。寫一個我的實現。

滚动数组法

#include <stdio.h>
int arr[3]={0,1};
int main(void){int index=0;printf("Enter the index:\n");scanf("%d",&index);if(index<=2){printf("%d\n",arr[index-1]);return 0;}else{for(int i=3;i<=index;++i){arr[2]=arr[1]+arr[0];arr[0]=arr[1];arr[1]=arr[2];}}printf("%d\n",arr[2]);return 0;
}

好了，这就是传说中的複雜度爲 $O(N)$ 的方法，比之前的递归是要好一点了。面试的时候写这个也差不多达到平均水平了。下面还有一种方法，虽然理论上可以。就是求数列的通项公式，不过这个引入了无理数。所以实际上不行。
下面是最暴的，也是比较有水平的方法。复杂度可以达到 $O(Log_2N)$ .策略呢，当然是我抄过来的。用矩阵。
因为Fibonacci是二阶递推数列，所以由矩阵相称的公式可得。存在一个2＊2的矩阵A。使得 $(F_n\quad F_{n-1})=(F_{n-1}\quad F_{n-2})*A$
求解可得：

A = (1110)

$A=\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$
由上面可以推出：

(FnFn−1)=(Fn−1Fn−2)∗A=(Fn−2Fn−3)∗A2=....=(F1F0)An−1 $(F_n\quad F_{n-1})=(F_{n-1}\quad F_{n-2})*A=(F_{n-2}\quad F_{n-3})*A^2=....=(F_1\quad F_0)A^{n-1}$
看到了没，现在只需要能求出

An−1 $A^{n-1}$ ，然后做一个矩阵乘法就行啦。
所以我们要做的工作就是实现一个矩阵操作的类或者函数。OK，我在装下B，写一个简单实现。

#include <iostream>
#include <cassert>
using namespace std;
const int N=4;
class Martix{
public:unsigned int size;long long int data[N*N];
};
//Multi bewteen martix and martix
Martix  martixMulti(const Martix A,const Martix B,Martix result){assert(A.size==B.size);result.size=A.size;for(int i=0;i<result.size;++i)for(int j=0;j<result.size;++j){result.data[i*result.size+j]=0;for(int k=0;k<result.size;++k)result.data[i*result.size+j]+=A.data[i*A.size+k]*B.data[k*B.size+j];}return result;
}
//Compute the n-1 of exp
Martix martixPow(Martix &A,int index){if(index==0)exit(0);--index; //compute n-1 expMartix IdenMartix;IdenMartix.size=2;IdenMartix.data[0]=1,IdenMartix.data[1]=0;IdenMartix.data[2]=0,IdenMartix.data[3]=1;Martix result=IdenMartix;for(;index;index>>=1){if(index&1)result=martixMulti(result,A,result);A=martixMulti(A,A,A);}return result;
}
int Fib(int n){Martix A;A.size=2;A.data[0]=1,A.data[1]=1;A.data[2]=1,A.data[3]=0;Martix an=martixPow(A,n);return an.data[0];
}
int main(int agrc,char **argv){unsigned int index;cout<<"Input index:";cin>>index;cout<<Fib(index)<<endl;return 0;
}