用Python實(shí)現(xiàn)Fibonacci函數(shù)

最近在玩Python，在粗略的看了一下Learning Python和Core Python之后，偶然發(fā)現(xiàn)網(wǎng)上有個(gè)帖子Python程序員的進(jìn)化寫的很有意思。于是打算仿照一篇，那篇帖子用了十余種方法完成一個(gè)階乘函數(shù)，我在這里會(huì)用九種不同的風(fēng)格寫出一個(gè)Fibonacci函數(shù)。

 

要求很簡(jiǎn)單，輸入n，輸出第n個(gè)Fibonacci數(shù)，n為正整數(shù)

 

下面是這九種不同的風(fēng)格：

 

 

1）第一次寫程序的Python程序員：

 

01 def fib(n):

02 return nth fibonacci number

 

說明：

第一次寫程序的人往往遵循人類語言的語法而不是編程語言的語法，就拿我一個(gè)編程很猛的哥們來說，他寫的第一個(gè)判斷閏年的程序，里面直接是這么寫的：如果year是閏年，輸出year是閏年，否則year不是閏年。

 

 

--------------------------------------------------------------------------------

 

2）剛學(xué)Python不久的的C程序員：

 

01 def fib(n):#{

02 if n<=2 :

03 return 1;

04 else:

05 return fib(n-1)+fib(n-2);

06 #}

 

說明：

在剛接觸Python時(shí)，用縮進(jìn)而非大括號(hào)的方式來劃分程序塊這種方式我是很不適應(yīng)的，而且每個(gè)語句后面沒有結(jié)束符，所以每次寫完一個(gè)Python函數(shù)之后干的第一件事一般就是一邊注釋大括號(hào)，一邊添加漏掉的冒號(hào)。

 

 

--------------------------------------------------------------------------------

 

3）懶散的Python程序員：

 

01 def fib(n):

02 return 1 and n<=2 or fib(n-1)+fib(n-2)

 

說明：

看了Learning Python之后，才知道Python沒有三元操作符？，不過鑒于Python里bool值比較特殊（有點(diǎn)像C，非零即真，非空即真），再加上Python的邏輯語句也是支持短路求值（Short-Circuit Evaluation）的，這就可以寫出一個(gè)仿？語句出來。

 

 

--------------------------------------------------------------------------------

 

4）更懶的Python程序員：

 

01 fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)

 

說明：

lambda關(guān)鍵字我曾在C#和Scheme里面用過，Python里面的lambda比C#里簡(jiǎn)便，并很像Scheme里的用法，所以很快就適應(yīng)了。在用Python Shell聲明一些小函數(shù)時(shí)經(jīng)常用這種寫法。

 

 

--------------------------------------------------------------------------------

 

5）剛學(xué)完數(shù)據(jù)結(jié)構(gòu)的Python程序員：

 

01 def fib(n):

02 x,y=0,1

03 while(n):

04 x,y,n=y,x+y,n-1

05 return x

 

說明：

前面的Fibonacci函數(shù)都是樹形遞歸的實(shí)現(xiàn)，哪怕是學(xué)一點(diǎn)算法就應(yīng)該知道這種遞歸的低效了。在這里從樹形遞歸改為對(duì)應(yīng)的迭代可以把效率提升不少。

Python的元組賦值特性是我很喜歡的一個(gè)東東，這玩意可以把代碼簡(jiǎn)化不少。舉個(gè)例子，以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a實(shí)現(xiàn)，既簡(jiǎn)潔又明了。

 

 

--------------------------------------------------------------------------------

 

6）正在修SICP課程的Python程序員：

 

01 def fib(n):

02 def fib_iter(n,x,y):

03 if n==0 : return x

04 else : return fib_iter(n-1,y,x+y)

05

06 return fib_iter(n,0,1)

 

說明：

在這里我使用了Scheme語言中很常見的尾遞歸（Tail-recursion）寫法。Scheme里面沒有迭代，但可以用不變量和尾遞歸來模擬迭代，從而實(shí)現(xiàn)相同的效果。不過我還不清楚Python有沒有對(duì)尾遞歸做相應(yīng)的優(yōu)化，回頭查一查。

PS：看過SICP的同學(xué)，一眼就能看出，這個(gè)程序其實(shí)就是SICP第一章里的一個(gè)例子。

 

 

--------------------------------------------------------------------------------

 

7）好耍小聰明的Python程序員：

 

01 fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)

 

說明：

基本的邏輯和上面的例子一樣，都是尾遞歸寫法。主要的區(qū)別就是利用了Python提供的默認(rèn)參數(shù)和三元操作符，從而把代碼簡(jiǎn)化至一行。至于默認(rèn)參數(shù)，學(xué)過C++的同學(xué)都知道這玩意，至于C#4.0也引入了這東東。

 

 

--------------------------------------------------------------------------------

 

8）剛修完線性代數(shù)的Python程序員：

 

01 def fib(n):

02 def m1(a,b):

03 m=[[],[]]

04 m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0])

05 m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1])

06 m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0])

07 m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1])

08 return m

09 def m2(a,b):

10 m=[]

11 m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0])

12 m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0])

13 return m

14 return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]

 

說明：

這段代碼就不像之前的代碼那樣清晰了，所以先介紹下原理（需要一點(diǎn)線性代數(shù)知識(shí)）：

首先看一下之前的迭代版本的Fibonacci函數(shù)，很容易可以發(fā)現(xiàn)存在一個(gè)變換：y->x, x+y->y。換一個(gè)角度，就是[x,y]->[y,x+y]。

在這里，我聲明一個(gè)二元向量[x,y]T，它通過一個(gè)變換得到[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的結(jié)果就是下一個(gè)Fibonacci數(shù)值，即：

Ax=[fib(1),fib(2)]T

亦有：

Ax=[fib(2),fib(3)]T

………………

以此類推，可以得到：

Aⁿx=[fib(n),fib(n-1)]T

也就是說可以通過對(duì)二元向量[0,1]T進(jìn)行n次A變換，從而得到[fib(n),fib(n+1)]T，從而得到fib(n)。

 

在這里我定義了一個(gè)二元矩陣的相乘函數(shù)m1，以及一個(gè)在二元向量上的變換m2，然后利用reduce操作完成一個(gè)連乘操作得到Aⁿx，最后得到fib(n)。

 

 

--------------------------------------------------------------------------------

 

9）準(zhǔn)備參加ACM比賽的Python程序員：

 

01 def fib(n):

02 lhm=[[0,1],[1,1]]

03 rhm=[[0],[1]]

04 em=[[1,0],[0,1]]

05 #multiply two matrixes

06 def matrix_mul(lhm,rhm):

07 #initialize an empty matrix filled with zero

08 result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]

09 #multiply loop

10 for i in range(len(lhm)):

11 for j in range(len(rhm[0])):

12 for k in range(len(rhm)):

13 result[i][j]+=lhm[i][k]*rhm[k][j]

14 return result

15

16 def matrix_square(mat):

17 return matrix_mul(mat,mat)

18 #quick transform

19 def fib_iter(mat,n):

20 if not n:

21 return em

22 elif(n%2):

23 return matrix_mul(mat,fib_iter(mat,n-1))

24 else:

25 return matrix_square(fib_iter(mat,n/2))

26 return matrix_mul(fib_iter(lhm,n),rhm)[0][0]

 

說明：

看過上一個(gè)fib函數(shù)就比較容易理解這一個(gè)版本了，這個(gè)版本同樣采用了二元變換的方式求fib(n)。不過區(qū)別在于這個(gè)版本的復(fù)雜度是lgn，而上一個(gè)版本則是線性的。

這個(gè)版本的不同之處在于，它定義了一個(gè)矩陣的快速求冪操作fib_iter，原理很簡(jiǎn)單，可以類比自然數(shù)的快速求冪方法，所以這里就不多說了。

PS：雖然說是ACM版本，不過說實(shí)話我從來沒參加過那玩意，畢竟自己算法太水了，那玩意又太高端……只能在這里YY一下鳥~

 

后記：

由于剛學(xué)習(xí)Python沒多久，所以對(duì)其各種特性的掌握還不夠熟練。與其說是我在用Python寫程序，倒不如說我是在用C，C++，C#或是Scheme來寫程序。至于傳說中的Pythonic way，我現(xiàn)在還沒有什么體會(huì)，畢竟還沒用Python寫過什么真正的程序。

Learning Python和Core Python都是不錯(cuò)的Python入門書籍，前者更適合沒有編程基礎(chǔ)的人閱讀。

Python是最好的初學(xué)編程入門語言，沒有之一。所以它可以取代Scheme成為MIT的計(jì)算機(jī)編程入門語言。