快捷導(dǎo)航

如何使用Python實(shí)現(xiàn)斐波那契數(shù)列

更新時(shí)間：2019年07月02日 15:02:30 作者：FOOFISH-PYTHON之禪

這篇文章主要介紹了如何使用Python實(shí)現(xiàn)斐波那契數(shù)列，斐波那契數(shù)列（Fibonacci）最早由印度數(shù)學(xué)家Gopala提出，而第一個(gè)真正研究斐波那契數(shù)列的是意大利數(shù)學(xué)家 Leonardo Fibonacci,需要的朋友可以參考下

斐波那契數(shù)列（Fibonacci）最早由印度數(shù)學(xué)家Gopala提出，而第一個(gè)真正研究斐波那契數(shù)列的是意大利數(shù)學(xué)家 Leonardo Fibonacci，斐波那契數(shù)列的定義很簡(jiǎn)單，用數(shù)學(xué)函數(shù)可表示為：

數(shù)列從0和1開(kāi)始，之后的數(shù)由前兩個(gè)數(shù)相加而得出，例如斐波那契數(shù)列的前10個(gè)數(shù)是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34。

用 Python 實(shí)現(xiàn)斐波那契數(shù)列常見(jiàn)的寫(xiě)法有三種，各算法的執(zhí)行效率也有很大差別，在面試中也會(huì)偶爾會(huì)被問(wèn)到，通常面試的時(shí)候不是讓你簡(jiǎn)單的用遞歸寫(xiě)寫(xiě)就完了，還會(huì)問(wèn)你時(shí)間復(fù)雜度怎樣，空間復(fù)雜度怎樣，有沒(méi)有可改進(jìn)的地方。

遞歸法

所謂遞歸就是指函數(shù)的定義中使用了函數(shù)自身的方法

def fib_recur(n):
assert n >= 0
if n in (0, 1):
return n
return fib_recur(n - 1) + fib_recur(n - 2)
for i in range(20):
print(fib_recur(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

遞歸是一種代碼最簡(jiǎn)潔的方法，但它是效率非常低，因?yàn)闀?huì)出現(xiàn)大量的重復(fù)計(jì)算，時(shí)間復(fù)雜度是：O(1.618 ^ n)，1.618是黃金分割。同時(shí)受限于 Python 中遞歸的最大深度是 1000，所以用遞歸來(lái)求解并不是一種可取的辦法。

遞推法

遞推法就是從0和1開(kāi)始，前兩項(xiàng)相加逐個(gè)求出第3、第4個(gè)數(shù)，直到求出第n個(gè)數(shù)的值

def fib_loop(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
for i in range(20):
print(fib_loop(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

這種算法的時(shí)間復(fù)雜是O(n)，呈線性增長(zhǎng)，如果數(shù)據(jù)量巨大，速度越到后面會(huì)越慢。

上面兩種方式都是使用分而治之的思想，就是把一個(gè)大的問(wèn)題化小，然后利用小問(wèn)題的求解得到目標(biāo)問(wèn)題的答案。

矩陣法

《線性代數(shù)》是大學(xué)計(jì)算機(jī)專(zhuān)業(yè)低年級(jí)的課程，這門(mén)課教的就是矩陣，那時(shí)候覺(jué)得這東西學(xué)起來(lái)很枯燥，沒(méi)什么用處，工作后你才發(fā)現(xiàn)搞機(jī)器學(xué)習(xí)、數(shù)據(jù)分析、數(shù)據(jù)建模時(shí)大有用處，書(shū)到用時(shí)方恨少。其實(shí)矩陣的本質(zhì)就是線性方程式。

斐波那契數(shù)列中兩個(gè)相鄰的項(xiàng)分別為：F(n) 和 F(n - 1)，如果把這兩個(gè)數(shù)當(dāng)作一個(gè)2行1列的矩陣可表示為：

因?yàn)?F(n) = F(n-1)+F(n-2)，所以就有：

通過(guò)反推，其實(shí)它是兩個(gè)矩陣的乘積得來(lái)的

依此類(lèi)推：

最后可推出：

因此想要求出F(n)的值，只要能求出右邊矩陣的n-1次方的值，最后求得兩矩陣乘積，取新矩陣的第一行的第一列的值即可，比如n=3時(shí)，

可以得知F(3)的值2，F(xiàn)(2)的值為1，因?yàn)閮邕\(yùn)算可以使用二分加速，所以矩陣法的時(shí)間復(fù)雜度為 O(log n)

我們可以用科學(xué)計(jì)算包 numpy 來(lái)實(shí)現(xiàn)矩陣法：

import numpy
def fib_matr(n):
return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0]
for i in range(20):
print(int(fib_matr(i)), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

3中不同的算法效率對(duì)比：