文章來自：http://blog.csdn.net/mshantingting/article/details/22689573

?

斐波那契數列（又名黃金分割數列）在數學上的定義如下：

?????????????????????

許多人包括作者自己在看到這道題的時候，第一個想法就是使用函數遞歸來實現程序。

?

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long long Fibonacci(int n) 5 { 6 long long f; 7 if(n==1||n==2) 8 f=1; 9 else 10 f=Fibonacci(n-1)+Fibonacci(n-2); 11 return f; 12 } 13 14 int main() 15 { 16 int n; 17 long long f; 18 scanf("%d",&n); 19 f=Fibonacci(n); 20 printf("%lld",f); 21 return 0; 22 } View Code

?

這種方法雖然便于理解，但是我們考慮一下，它的時間復雜度可是以n的指數形式增長 的。當n=10，n=20或者n=30時，程序能夠在我們可以接受的運行時間內反饋給我們運行結果。但是，我們如果試一下n=50的情況，運行時間已經遠 遠超過了我們能夠等待的時間（大概一分半鐘）。原因很簡單，例如我們要求f(8)，就要知道f(7)和f(6)，而求f(7)我們要求得f(6)和 f(5)，因此我們重復求了很多項，浪費很多時間。 改進的做法也是很簡單的，我們可以從小往大算，循環n-1次，根據f(0)和f(1)求出f(2)，再根據f(1)和f(2)求出f(3)，以此類推。代碼實現如下： 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long long Fibonacci(int n) 5 { 6 int result[2]={0,1},i; 7 if(n<2) 8 return result[n]; 9 long long One = 1,Two = 0,Current_N = 0; 10 for(i=2;i<=n;i++) 11 { 12 Current_N = One + Two; 13 Two = One; 14 One = Current_N; 15 } 16 return Current_N; 17 } 18 19 int main() 20 { 21 long long n,f; 22 scanf("%d",&n); 23 f=Fibonacci(n); 24 printf("%lld",f); 25 return 0; 26 } View Code

此方法時間復雜度是O(n)。這種方法提高了時間效率，被很多人采用。那還有沒有更快的方法呢？根據《劍指offer》一書中作者提到的方法，書中介紹了一個數學公式如下：

?????????????????????????????

我進行了如下驗算：

?????????????????????????????

因此f(n)就等于等式右邊的二階方陣的(n-1)次方所求得方陣的第一行第一列個數的值。代碼實現如下：

?

1 #include <cstdio> 2 #include <iostream> 3 #include <cstdlib> 4 5 using namespace std; 6 7 //求矩陣a的n次冪的函數 8 long long * Matrix(long long *a,int n) 9 { 10 long long *result = (long long *)malloc(sizeof(long long)*4); 11 long long *finnal = (long long *)malloc(sizeof(long long)*4); 12 //如果n等于1的話，則直接返回矩陣a，畢竟，一次冪就不必求了。 13 if(n==1) 14 return a; 15 //先求出矩陣的n/2次冪 16 long long *CurMatrix = Matrix(a,n/2); 17 //兩個矩陣的n/2次冪相乘得到矩陣的n次冪 18 result[0] = CurMatrix[0]*CurMatrix[0]+CurMatrix[1]*CurMatrix[2]; 19 result[1] = CurMatrix[0]*CurMatrix[1]+CurMatrix[1]*CurMatrix[3]; 20 result[2] = CurMatrix[2]*CurMatrix[0]+CurMatrix[3]*CurMatrix[2]; 21 result[3] = CurMatrix[2]*CurMatrix[1]+CurMatrix[3]*CurMatrix[3]; 22 //如果n為奇數的話，則(n/2)會少一位，補回來。a = a^(n/2)*a^(n/2) * a; 23 if(n%2==1) 24 { 25 finnal[0] = result[0]*a[0]+result[1]*a[2]; 26 finnal[1] = result[0]*a[1]+result[1]*a[3]; 27 finnal[2] = result[2]*a[0]+result[3]*a[2]; 28 finnal[3] = result[2]*a[1]+result[3]*a[3]; 29 } 30 //如果n為偶數的話，n/2還是n/2 31 else 32 finnal = result; 33 return finnal; 34 } 35 36 int main(void) 37 { 38 long long a[4]; 39 int n; 40 cin>>n; 41 //矩陣按一位數組設置,t[0]即為febonacci(n) 42 a[0] = 1; 43 a[1] = 1; 44 a[2] = 1; 45 a[3] = 0; 46 long long *t = Matrix(a,n-1); 47 cout<<t[0]<<endl; 48 return 0; 49 } View Code

?

顯而易見，該算法的復雜度為O(logn)。
以上三種方法的時間效率一次增高，雖然人們普遍對第三種算法中的公式比較陌生，但經過一番細細地琢磨以后，便能體會到它的獨到之處。
（聲明：文章版權歸原作者所有，轉載請注明出處：http://blog.csdn.net/mshantingting/article/details/22689573）

?

轉載于:https://www.cnblogs.com/huashanqingzhu/p/3637518.html

總結

以上是生活随笔為你收集整理的斐波那契数列的低效与高效解法 【转】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。