決定開始看algorithms，而且盡量多思考，多寫點代碼。第一個碰到的算法就很具有啟發(fā)性，一些看似正確的算法，實際的復雜度卻很高。我們直接看問題：

---

問題：假設fibonacci(0)=0,fibonacci(1)=1,如果計算fibonacci(n)

解決方案一：直接利用斐波那契數的性質用遞歸計算

1?def?fibonacci1(n):
2?????if?n?==?0:
3?????????return?0
4?????elif?n?==?1:
5?????????return?1
6?????else:
7?????????return?fibonacci1(n-1)+fibonacci1(n-2)

一看好像這樣做沒什么不妥，但是你如果跑下fibonacci1(50)機器就開始忙碌了，仔細想想，這個算法的復雜度其實是O(2ⁿ),看看原書上的圖就明白了

其中重復的計算很多，最后需要計算的次數是2^0.694n +3n次，這個明顯是不行的，當n較大時，什么電腦都要跑上很久很久

解決方案二：不用遞歸，直接用循環(huán)計算

1?def?fibonacci2(n):
2?????fib=[0,?1]
3?????for?i?in?range(2,n+1):
4?????????fib.append(fib[i-1]+fib[i-2])
5?????return?fib[n]

這種做法也比較直觀，很明顯這種方法的復雜度是O(n)。一般來說，你肯定會覺得這樣就夠了，實際上還有l(wèi)ogn復雜度的方法。

解決方案三：用矩陣計算

斐波那契數的性質可以用矩陣來表示：，那么有。我們用X來表示其中的0111矩陣，那么對于Fn，我們只要計算Xⁿ

就可以得到Fn。當然我們不能用循環(huán)來計算Xⁿ ，而是用“折半法“通過X^n/2 *X^n/2計算。

代碼?1?def?fibonacci3(n):
?2?????return?recuCal(n)[1]
?3?
?4?matrix=[0,1,1,1]
?5?def?recuCal(n):
?6?????if?n?==?1:
?7?????????return?matrix
?8?????elif?n?==?2:
?9?????????return?matrixCal(matrix,matrix)
10?????elif?n?%?2:
11?????????return?matrixCal(matrixCal(recuCal(n/2),recuCal(n/2)),matrix)
12?????else:
13?????????return?matrixCal(recuCal(n/2),recuCal(n/2))
14?
15?def?matrixCal(matrix1,matrix2):
16?????matrix3?=?[0,0,0,0]
17?????matrix3[0]=matrix1[0]*matrix2[0]+matrix1[1]*matrix2[2]
18?????matrix3[1]=matrix1[0]*matrix2[1]+matrix1[1]*matrix2[3]
19?????matrix3[2]=matrix1[2]*matrix2[0]+matrix1[3]*matrix2[2]
20?????matrix3[3]=matrix1[2]*matrix2[1]+matrix1[3]*matrix2[3]
21?????return?matrix3

算法比較簡單，matrixCal是計算兩個矩陣的方法。recuCal是實現“折半法”的函數，返回計算結果矩陣，而這個矩陣的第2個數就是需要的結果。

---

以上代碼都是用python寫的，可以再寫一個main來驗證結果：

1?if?__name__?==?'__main__':
2?????print?fibonacci1(50)
3?????print?fibonacci2(50)
4?????print?fibonacci3(50)

當然fibonacci1(50)短時間跑不完的。最好還是把n定小點。

寫完咯，睡覺

?

轉載于:https://www.cnblogs.com/kakafei/archive/2009/12/04/1616576.html

總結

以上是生活随笔為你收集整理的[算法学习]斐波那契数的计算的全部內容，希望文章能夠幫你解決所遇到的問題。

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