欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

用Python實現(xiàn)斐波那契(Fibonacci)函數(shù)

 更新時間:2016年03月25日 10:57:25   投稿:hebedich  
這篇文章主要介紹了用Python實現(xiàn)斐波那契(Fibonacci)函數(shù)的相關(guān)資料,需要的朋友可以參考下

Fibonacci斐波那契數(shù)列,很簡單,就是一個遞歸嘛,學(xué)任何編程語言可能都會做一下這個。

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

要求很簡單,輸入n,輸出第n個Fibonacci數(shù),n為正整數(shù)

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

1)第一次寫程序的Python程序員:

def fib(n):
  return nth fibonacci number

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

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

def fib(n):#{
 if n<=2 :
  return 1;
 else:
  return fib(n-1)+fib(n-2);
#}

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

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

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

def fib(n):
 x,y=0,1
 while(n):
  x,y,n=y,x+y,n-1
 return x

說明:
前面的Fibonacci函數(shù)都是樹形遞歸的實現(xiàn),哪怕是學(xué)一點算法就應(yīng)該知道這種遞歸的低效了。在這里從樹形遞歸改為對應(yīng)的迭代可以把效率提升不少。
Python的元組賦值特性是我很喜歡的一個東東,這玩意可以把代碼簡化不少。舉個例子,以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a實現(xiàn),既簡潔又明了。

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里面沒有迭代,但可以用不變量和尾遞歸來模擬迭代,從而實現(xiàn)相同的效果。不過我還不清楚Python有沒有對尾遞歸做相應(yīng)的優(yōu)化,回頭查一查。
PS:看過SICP的同學(xué),一眼就能看出,這個程序其實就是SICP第一章里的一個例子。

7)好耍小聰明的Python程序員:

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

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

8)剛修完線性代數(shù)的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]

說明:
這段代碼就不像之前的代碼那樣清晰了,所以先介紹下原理(需要一點線性代數(shù)知識):
首先看一下之前的迭代版本的Fibonacci函數(shù),很容易可以發(fā)現(xiàn)存在一個變換: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的結(jié)果就是下一個Fibonacci數(shù)值,即:
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)。

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

9)準(zhǔn)備參加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函數(shù)就比較容易理解這一個版本了,這個版本同樣采用了二元變換的方式求fib(n)。不過區(qū)別在于這個版本的復(fù)雜度是lgn,而上一個版本則是線性的。

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

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

python中,最基本的那種遞歸(如下fib1)效率太低了,只要n數(shù)字大了運算時間就會很長;而通過將計算的指保存到一個dict中,后面計算時直接拿來使用,這種方式成為備忘(memo),如下面的fib2函數(shù)所示,則會發(fā)現(xiàn)效率大大提高。

在n=10以內(nèi)時,fib1和fab2運行時間都很短看不出差異,但當(dāng)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數(shù)列的函數(shù),如下: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())

后記:

由于剛學(xué)習(xí)Python沒多久,所以對其各種特性的掌握還不夠熟練。與其說是我在用Python寫程序,倒不如說我是在用C,C++,C#或是Scheme來寫程序。至于傳說中的Pythonic way,我現(xiàn)在還沒有什么體會,畢竟還沒用Python寫過什么真正的程序。
Learning Python和Core Python都是不錯的Python入門書籍,前者更適合沒有編程基礎(chǔ)的人閱讀。
Python是最好的初學(xué)編程入門語言,沒有之一。所以它可以取代Scheme成為MIT的計算機編程入門語言。

相關(guān)文章

  • python微信公眾號開發(fā)簡單流程實現(xiàn)

    python微信公眾號開發(fā)簡單流程實現(xiàn)

    這篇文章主要介紹了python微信公眾號開發(fā)簡單流程實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-03-03
  • Python多進程編程技術(shù)實例分析

    Python多進程編程技術(shù)實例分析

    這篇文章主要介紹了Python多進程編程技術(shù),包括了線程、隊列、同步等概念及相關(guān)的技巧總結(jié),需要的朋友可以參考下
    2014-09-09
  • 利用Python腳本實現(xiàn)ping百度和google的方法

    利用Python腳本實現(xiàn)ping百度和google的方法

    最近在做SEO的時候,為了讓發(fā)的外鏈能夠快速的收錄,想到了利用ping的功能,google和百度都有相關(guān)的ping介紹,有興趣的朋友可以去看看相關(guān)的知識。下面這篇文章主要介紹了利用Python腳本實現(xiàn)ping百度和google的方法,需要的朋友可以參考借鑒,一起來看看吧。
    2017-01-01
  • python網(wǎng)絡(luò)編程學(xué)習(xí)筆記(五):socket的一些補充

    python網(wǎng)絡(luò)編程學(xué)習(xí)筆記(五):socket的一些補充

    前面已經(jīng)為大家介紹了python socket的一些相關(guān)知識,這里為大家補充下,方便需要的朋友
    2014-06-06
  • Python中的if、else、elif語句用法簡明講解

    Python中的if、else、elif語句用法簡明講解

    這篇文章主要介紹了Python中的if、else、elif語句的用法講解,條件判斷語句是程序中流程控制的基礎(chǔ)辦法之一,需要的朋友可以參考下
    2016-03-03
  • Python入門篇之文件

    Python入門篇之文件

    文件是我們儲存信息的地方,我們經(jīng)常要對文件進行讀、寫、刪除等的操作,在Python中,我們可用Python提供的函數(shù)和方法方便地操作文件。文件可以通過調(diào)用open或file來打開,open通常比file更通用,因為file幾乎都是為面向?qū)ο蟪绦蛟O(shè)計量身打造
    2014-10-10
  • 詳解pandas獲取Dataframe元素值的幾種方法

    詳解pandas獲取Dataframe元素值的幾種方法

    這篇文章主要介紹了詳解pandas獲取Dataframe元素值的幾種方法,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-06-06
  • python項目--使用Tkinter的日歷GUI應(yīng)用程序

    python項目--使用Tkinter的日歷GUI應(yīng)用程序

    在 Python 中,我們可以使用 Tkinter 制作 GUI。如果你非常有想象力和創(chuàng)造力,你可以用 Tkinter 做出很多有趣的東西,希望本篇文章能夠幫到你
    2021-08-08
  • 用python自動生成日歷

    用python自動生成日歷

    這篇文章主要介紹了如何用python自動生成日歷,幫助大家更好的理解和學(xué)習(xí)使用python,感興趣的朋友可以了解下
    2021-04-04
  • Python自動化之?dāng)?shù)據(jù)驅(qū)動讓你的腳本簡潔10倍【推薦】

    Python自動化之?dāng)?shù)據(jù)驅(qū)動讓你的腳本簡潔10倍【推薦】

    數(shù)據(jù)驅(qū)動是一種思想,讓數(shù)據(jù)和代碼進行分離。這篇文章主要介紹了Python自動化之?dāng)?shù)據(jù)驅(qū)動,讓你的腳本簡潔10倍,需要的朋友可以參考下
    2019-06-06

最新評論