實現斐波拉契數列的四種方式python程式碼
摘要：
斐波那契數列
1. 斐波拉契數列簡介
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34...
斐波那契數列
1. 斐波拉契數列簡介
斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞迴的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從1963年起出版了以《斐波納契數列季刊》為名的一份數學雜誌，用於專門刊載這方面的研究成果。
其實就是從第三項開始，每項的值等於前兩項的和。
下面是在面試中常見的問題：青蛙跳臺階
一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
只有一級臺階時，1；
有兩節臺階的時候有兩種跳法，11和2；
有三節臺階的時候有三種跳法，111、12、21
有四階臺階的時候，有五種跳法，1111、112、121、22、211
2. 實現斐波拉契數列生成
2.1 使用匿名函式的方式生成
fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)
通過執行fib(n)
來輸出斐波那契數列前n項的值。
也可以通過listData = [fib(i) for i in range(1,n)]
來生成斐波拉契數列前n項的值，最後通過print listData
可以打印出結果。
2.2 利用裝飾器的方式生成
def memo(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap
@ memo
def fib(i):
if i < 2:
return 1
return fib(i-1) + fib(i-2)
2.3 定義簡單的方法來實現
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return b
2.4 利用迭代器的方式實現(Python3)
class Fib(object):
def __init__(self):
self.prev = 0
self.curr = 1
def __iter__(self):
return self
def __next__(self):
value = self.curr
self.curr += self.prev
self.prev = value
return value
2.5 利用迭代器的方式實現(Python2)
python2需要修改__next__(self)
:方法，其實生成的是一個無限迴圈的迭代器，也可以使用 itertools模組把無限迭代器轉為有限迭代器。
from itertools import islice
class Fib:
def __init__(self):
self.prev = 0
self.curr = 1
def __iter__(self):
return self
def __next__(self):
value = self.curr
self.curr += self.prev
self.prev = value
return value
>>> f = Fib()
>>> list(islice(f, 0, 10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]