在這些時候，我可以附和著笑，項目經理是決不責備的。而且項目經理見了孔乙己，也每每這樣問他，引人發笑。孔乙己自己知道不能和他們談天，便只好向新人說話。有一回對我說道，“你學過數據結構嗎？”我略略點一點頭。他說，“學過數據結構，……我便考你一考。斐波那契數列用Python怎樣寫的？”我想，討飯一樣的人，也配考我么？便回過臉去，不再理會。孔乙己等了許久，很懇切的說道，“不能寫罷？……我教給你，記著！這些字應該記著。將來做項目經理的時候，寫賬要用。”我暗想我和項目經理的等級還很遠呢，而且我們項目里也用不到斐波那契數列；又好笑，又不耐煩，懶懶的答他道，“誰要你教，不是f(n) = f(n-1)+f(n-2)嗎？”孔乙己顯出極高興的樣子，將兩個指頭的長指甲敲著辦公桌，點頭說，“對呀對呀！……斐波那契數列在python中有四種寫法，你知道么？”我愈不耐煩了，努著嘴走遠。孔乙己剛拿出筆記本電腦,想要寫幾段程序，見我毫不熱心，便又嘆一口氣，顯出極惋惜的樣子。

斐波那契數列的定義

F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

CODE

本次介紹Python中斐波那契數列的四種寫法,第一種寫法比較常見,第二種寫法也比較常見.(魯迅聽了想打人).咳咳.第一種依賴于遞歸,第二種依賴與循環,前兩種算法都是可以在幾乎所有編程語言里面都能都快速移植的.我們先從這兩種介紹

第一種:遞歸

# 遞歸 def Fibonacci_Recursion_tool(n):if n <= 0:return 0elif n == 1:return 1else:return Fibonacci_Recursion_tool(n - 1) + Fibonacci_Recursion_tool(n - 2)def Fibonacci_Recursion(n):result_list = []for i in range(1, n + 1): result_list.append(Fibonacci_Recursion_tool(i))return result_list

在代碼中,對于第n個斐波那契數列我們采用遞歸生成.而對于獲取list形式的斐波那契數列我們則采取for循環獲取.

但是我們將遞歸拆開來看就會發現一個巨大的問題,f(n) = f(n-1)+f(n-2),為了求一個f(n),我們要多次計算前面的數值,這樣既浪費了內存,又浪費了計算能力,那有沒有更簡單的算法呢?答案是必然的.使用循環我們就可以避免這個問題.

既然代碼已經寫完了，那么問題來了，到底什么是遞歸呢？

第二種:循環

def Fibonacci_Loop_tool(n):a, b = 0, 1while n > 0:a, b = b, a + bn -= 1def Fibonacci_Loop(n):result_list = []a, b = 0, 1while n > 0:result_list.append(b)a, b = b, a + bn -= 1return result_list

Fibonacci_Loop_tool 是獲取 對應位數的類,而 Fibonacci_Loop 是獲取獲取數列的類.在這里比較特別的計算方式就在于,我們改從后向前的運算為從前到后,只是用a,b兩個變量交替向前,這樣就減少了生成數列的速度,當然如果想要生成某一個值的話,卻需要從頭開始計算在有些時候確實不太方便.

不過在介紹另外一種特殊的可以直接計算第n位數值的算法前,我們不如首先利用Python的特性來做優化一下循環生成斐波那契數列的算法.

yield關鍵字

對于前面的循環loop,當用其生成數列時,存在一個問題,那就是必須使用一個list來獲取存儲每次計算的數值,代碼十分地不優雅.python是優雅的編程語言,我們使用yield關鍵字,就可以讓代碼變得優雅起來.

def Fibonacci_Yield_tool(n):a, b = 0, 1while n > 0:yield ba, b = b, a + bn -= 1def Fibonacci_Yield(n):# return [f for i, f in enumerate(Fibonacci_Yield_tool(n))]return list(Fibonacci_Yield_tool(n))

相比于之前的Fibonacci_Loop,Fibonacci_Yield 明顯優雅了很多,yield關鍵字,可以在不打斷循環的情況下從循環中返回數值,這個特性簡直是nice,不過其返回的數據類型也變得有點特別,變成了generator,那么取值也就比以前不同了一點,這里有兩種方式,第一種是直接轉化為list,使用list()即可,這種方式比較快,速度消耗很小.除此之外還有第二種,return [f for i, f in enumerate(Fibonacci_Yield_tool(n))]列表解析,這種方式轉換速度很慢,在n=1000左右時,在我的電腦上速度接不斷接近于1s,但是讓我們只運行Fibonacci_Yield_tool()卻會發現,Fibonacci_Yield_tool的運行耗時只在10的負六次方到五次方之間.而直接轉化為list則對計算速度的影響較小,接近于純粹的計算耗時本身,幾乎不存在影響.在本例子中循環算法與yield關鍵字(list轉換)的速度接近.

第四種,矩陣求解_直接求出第n位數值

好了，Y(^o)Y介紹完了前面的內容，我們終于可以開始介紹矩陣直接求解了。要知道前面的三種算法都存在一個很大的問題,那就是無論計算哪一個數值,實際上都要將前面的數值f(n-?)計算一遍。而現在我們終于可以直接求解了，想想還有點小激動呢。

那么我們現在就通過矩陣求解就可以避免重復計算的問題,當然這里的矩陣求解并不是指向量化,而是指原斐波那契數列求解公式的轉化,將其轉化為新的求解方式,利用矩陣運算直接求解第n位的數值，簡單來說就是——

# 矩陣 Matrix = np.matrix('1 1;1 0') # 其n-1 次方的第一位,也就是Matrix(11)--下標11就是斐波那契數列的解

復雜來說，就是——

def Fibonacci_Matrix_tool(n): # 遞歸求解,速度慢與直接求方Matrix = np.matrix('1 1;1 0')if n == 1:return Matrixif n == 2:return pow(Matrix, 2)elif n % 2 == 1:return Fibonacci_Matrix_tool((n - 1) / 2) ** 2 * Matrixelse:return Fibonacci_Matrix_tool(n / 2) ** 2def Fibonacci_Matrix_tool2(n):Matrix = np.matrix('1 1;1 0')return pow(Matrix, n) # pow函數速度快于 使用雙星號 "**"def Fibonacci_Matrix(n):result_list = []for i in range(0, n): result_list.append(np.array(Fibonacci_Matrix_tool2(i))[0][0])return result_list

等等，這他喵是什么玩意，你就是在難為我段子手胖虎！

不過話說回來，其實這個很簡單的，就是菲波那切數列的求解公式，用矩陣求解而已。原理嗎，其實就是斐波那契額同樣公式的再簡化，有興趣的同學可以自己搜幾篇論文看看，公式如下：

性能比較

性能對比比較簡單，這里我們使用time函數進行計時。同時使用numpy類庫保存到文件中，之后可以用此來繪圖。具體代碼如下：

def Test_Fibonacci(n, list):t1 = time.clock()Fibonacci_Recursion(n)t2 = time.clock()l1 = t2 - t1t1 = time.clock()Fibonacci_Loop(n)t2 = time.clock()l2 = t2 - t1t1 = time.clock()Fibonacci_Yield(n)t2 = time.clock()l3 = t2 - t1t1 = time.clock()Fibonacci_Matrix(n)t2 = time.clock()l4 = t2 - t1list.append([l1,l2, l3, l4])print("第%d次的測試結果為:" % n, [l1,l2, l3, l4])def Test_Save(times_items, filename):times_list = []for i in range(1, times_items + 1): Test_Fibonacci(i, times_list)np.savetxt(filename, times_list)def Test_Print(Test_Print_n):print(Fibonacci_Recursion(Test_Print_n))print(Fibonacci_Loop(Test_Print_n))print(Fibonacci_Yield(Test_Print_n))print(Fibonacci_Matrix(Test_Print_n))times_items = 40 filename = "/home/fonttian/Data/17_DS_AI/Fibonacci/Fibonacci_all.txt" # Test_Save(times_items,filename)

然后我們進行多次計算最終得到了多種情況下的四種方法的性能數據。那么問題又來了，穿山甲到底說了什么 ，哪種方法是性能最好的呢？

我們打開我們的火眼金睛，然后第一個發現的就是一號這個內奸。從效果來看第一種效果最差，當其在35以上的運算次數時,其耗時就會達到1s,40秒的時候就會過百秒。咳咳，真是有點過分了。不顧好在其他的計算速度則仍然在十的負五次方到負六次方之間。

但是之后的比較就會出現一些問題。比如在早期較低的CPU頻率（約12G，能分給Python8~9G）的測試中，當次數大于1000時,loop的速度開始明顯不足，從這里看似乎生成器比循環要好些。但當CPU頻率不再是程序瓶頸時，卻又會發生逆轉。如總計算頻率為48G時，無論是循環還是生成器都將占用約20的計算資源，計算速度卻一直持平。其實熟悉yield的人基本會預料到這種情況，因為生成器本身就是一個循環不停止的“return”。而此時生成器的一個劣勢就很明顯的出現了，那就是內存，Python自身的垃圾回收機制并不強，而在高頻率的計算中生成器占用的內存長期得不到釋放，因此會越變越多，當到達萬次時，內存就可以穩定積累到1G以上，是不是十分可怕。

那么看來矩陣解法一定是最好最合適的算法嘍，答：當然不是！

從數學上看，當計算次數比較多時，矩陣一定是最好的方法，可以直接求一個結果就是最好的方法。然而實驗數據卻又狠狠打了我們的臉。因為np.Matrix在大數量級運算時存在一個問題——內存溢出(導致的數值錯誤)。。。。。。。

不過整體而言,定睛一看，矩陣求解最起碼也得上億才會溢出，而且這只是使用工具的問題，換個方法寫，公式不變其實是完全是可行的，只是編寫會麻煩一點。而返回來目前最好的還是yield,這是python出色設計的功勞。不愧是我最愛的Python，溜了溜了。

總結

以上是生活随笔為你收集整理的Python中斐波那契数列的四种写法的全部內容，希望文章能夠幫你解決所遇到的問題。

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