這篇文章主要介紹瞭如何使用Python實現斐波那契Fibonacci函數相關資料,需要的朋友可以參考下
Fibonacci斐波那契數列，很簡單，就是一個遞歸嘛，學任何程式語言可能都會做一下這個。
最近在玩Python，在粗略的看了一下Learning Python和Core Python之後，偶然發現網路上有個貼文Python程式設計師的演化寫的很有意思。於是打算仿照一篇，那篇貼文用了十餘種方法完成一個階乘函數，我在這裡會用九種不同的風格寫出一個Fibonacci函數。
要求很簡單，輸入n，輸出第n個Fibonacci數，n為正整數
下面是這九種不同的風格：
1）第一次寫程式的Python程式設計師：
def fib(n): return nth fibonacci number
說明：
第一次寫程式的人往往遵循人類語言的語法而不是程式語言的語法，就拿我一個程式設計很猛的哥們來說，他寫的第一個判斷閏年的程序，裡面直接是這麼寫的：如果year是閏年，輸出year是閏年，否則year不是閏年。
2）剛學Python不久的的C程式設計師：
def fib(n):#{
if n<=2 :
return 1;
else:
return fib(n-1)+fib(n-2);
#}說明：
剛接觸Python時，用縮排而非大括號的方式來劃分程式塊這種方式我是很不適應的，而且每個語句後面沒有結束符，所以每次寫完一個Python函數之後乾的第一件事一般就是一邊註釋大括號，一邊加上漏掉的冒號。
3）懶散的Python程式設計師：
def fib(n): return 1 and n<=2 or fib(n-1)+fib(n-2)
說明：
看了Learning Python之後，才知道Python沒有三元操作符？ ，不過鑑於Python裡bool值比較特殊（有點像C，非零即真，非空即真），再加上Python的邏輯語句也是支援短路求值（Short-Circuit Evaluation）的，這就可以寫出一個仿？語句出來。
4）更懶的Python程式設計師：
fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)
說明：
lambda關鍵字我曾在C#和Scheme裡面用過，Python裡面的lambda比C#裡簡便，很像Scheme裡的用法，所以很快就適應了。在用Python Shell宣告一些小函數時常用這種寫法。
5）剛學完資料結構的Python程式設計師：
def fib(n): x,y=0,1 while(n): x,y,n=y,x+y,n-1 return x
說明：
前面的Fibonacci函數都是樹形遞歸的實現，就算學一點演算法就應該知道這種遞歸的低效了。這裡從樹形遞歸改為對應的迭代可以把效率提升不少。
Python的元組賦值特性是我很喜歡的一個東東，這玩意可以把程式碼簡化不少。舉個例子，以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a實現，既簡潔又明了。
6）正在修SICP課程的Python程式設計師：
def fib(n): def fib_iter(n,x,y): if n==0 : return x else : return fib_iter(n-1,y,x+y) return fib_iter(n,0,1)
說明：
在這裡我使用了Scheme語言中很常見的尾遞歸（Tail-recursion）寫法。 Scheme裡面沒有迭代，但可以用不變量和尾遞歸來模擬迭代，從而達到相同的效果。不過我還不清楚Python有沒有對尾遞歸做相對應的優化，回頭查一查。
PS：看過SICP的同學，一眼就能看出，這個程式其實就是SICP第一章裡的例子。
7）好耍小聰明的Python程式設計師：
fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)
說明：
基本的邏輯和上面的例子一樣，都是尾遞歸寫法。主要的差別就是利用了Python提供的預設參數和三元操作符，從而把程式碼簡化至一行。至於預設參數，學過C++的同學都知道這玩意，至於C#4.0也引進了這東東。
8）剛修完線性代數的Python程式設計師：
def fib(n): def m1(a,b): m=[[],[]] m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1]) m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1]) return m def m2(a,b): m=[] m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) return m return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]
說明：
這段程式碼就不像之前的程式碼那樣清晰了，所以先介紹下原理（需要一點線性代數知識）：
先看一下之前的迭代版本的Fibonacci函數，很容易可以發現存在一個變換：y->x, x +y->y。換一個角度，就是[x,y]->[y,x+y]。
在這裡，我宣告一個二元向量[x,y]T，它透過一個變換得到[y,x+y]T，可以很容易得到變換矩陣是[[1,0],[1, 1]]，也就是說：[[1,0],[1,1]]*[x,y]T=[y,x+y]T
設二元矩陣A=[[1, 0],[1,1]]，二元向量x=[0,1]T，容易知道Ax的結果就是下一個Fibonacci數值，即：
Ax=[fib(1),fib(2) ]T
亦有：
Ax=[fib(2),fib(3)]T
………………
以此類推，可以得到：
Aⁿx=[fib(n),fib(n-1)]T
也就是說可以透過對二元向量[0,1]T進行n次A變換，從而得到[fib(n),fib(n+1 )]T，從而得到fib(n)。
在這裡我定義了一個二元矩陣的相乘函數m1，以及一個在二元向量上的變換m2，然後利用reduce操作完成一個連乘操作得到Aⁿx，最後得到fib (n)。
9）準備參加ACM比賽的Python程式設計師：
def fib(n):
lhm=[[0,1],[1,1]]
rhm=[[0],[1]]
em=[[1,0],[0,1]]
#multiply two matrixes
def matrix_mul(lhm,rhm):
#initialize an empty matrix filled with zero
result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
#multiply loop
for i in range(len(lhm)):
for j in range(len(rhm[0])):
for k in range(len(rhm)):
result[i][j]+=lhm[i][k]*rhm[k][j]
return result
def matrix_square(mat):
return matrix_mul(mat,mat)
#quick transform
def fib_iter(mat,n):
if not n:
return em
elif(n%2):
return matrix_mul(mat,fib_iter(mat,n-1))
else:
return matrix_square(fib_iter(mat,n/2))
return matrix_mul(fib_iter(lhm,n),rhm)[0][0]說明：
看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。
这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。
PS：虽然说是ACM版本，不过说实话我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里YY一下鸟~
python中，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。
在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.00001秒。
n=40时，输出如下：
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 2014-10-16 16:28:35.176396 fib1(40)=102334155 2014-10-16 16:29:10.479953 fib2(40)=102334155 2014-10-16 16:29:10.480035
这两个计算Fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
import datetime
def fib1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib1(n - 1) + fib1(n - 2)
known = {0: 0, 1: 1}
def fib2(n):
if n in known:
return known[n]
res = fib2(n - 1) + fib2(n - 2)
known[n] = res
return res
if __name__ == '__main__':
n = 40
print(datetime.datetime.now())
print('fib1(%d)=%d' % (n, fib1(n)))
print(datetime.datetime.now())
print('fib2(%d)=%d' % (n, fib2(n)))
print(datetime.datetime.now())后记：
由于刚学习Python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序，倒不如说我是在用C，C++，C#或是Scheme来写程序。至于传说中的Pythonic way，我现在还没有什么体会，毕竟还没用Python写过什么真正的程序。
Learning Python和Core Python都是不错的Python入门书籍，前者更适合没有编程基础的人阅读。
Python是最好的初学编程入门语言，没有之一。所以它可以取代Scheme成为MIT的计算机编程入门语言。
以上是如何使用Python實作斐波那契Fibonacci函數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
