斐波那契數(shù)列的相關(guān)題目是面試常見的，所以我看了些資料總結(jié)記錄一下這些小的知識點挑社。
1. 元組實現(xiàn)
代碼：
fibs = [0, 1]
for i in range(8):
fibs.append(fibs[-2] + fibs[-1])
print(fibs)
輸出：
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
2. 迭代器實現(xiàn)
class Fibs:
def __init__(self):
self.a = 0
self.b = 1
def next(self):
self.a, self.b = self.b, self.a + self.b
return self.a
def __iter__(self):
return self
這將得到一個無窮的數(shù)列， 可以采用如下方式訪問：
fibs = Fibs()
for f in fibs:
if f > 1000:
print(f)
break
else:
print(f)
3. 通過定制類實現(xiàn)
class Fib(object):
def __getitem__(self, n):
if isinstance(n, int):
a, b = 1, 1
for x in range(n):
a, b = b, a + b
return a
elif isinstance(n, slice):
start = n.start
stop = n.stop
a, b = 1, 1
L = []
for x in range(stop):
if x >= start:
L.append(a)
a, b = b, a + b
return L
else:
raise TypeError("Fib indices must be integers")
這樣可以得到一個類似于序列的數(shù)據(jù)結(jié)構(gòu)运准，可以通過下標(biāo)來訪問數(shù)據(jù)：
f = Fib()
print (f[0:10])
4.Python實現(xiàn)比較簡易的斐波那契數(shù)列示例
i, j = 0, 1
while i < 10000:
print( i,j, = j, i+j)
最后展示運行結(jié)果：
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
5.列表生成式實現(xiàn)
def fib(n):
if n == 1 or n == 0:
return 1
else:
return fib(n - 2) + fib(n - 1)
print([fib(n) for n in range(10)])
這個計算斐波那契數(shù)列前n項很簡單涩堤，但是從下面的圖可以看出這個計算花費的時間較多因為會重復(fù)計算很多值。
Paste_Image.png
這個時候我需要修改一下故俐，加入緩存機制想鹰。
def fib(n, cache=None):
if cache is None:
cache = {}
if n in cache:
return cache[n]
if n == 1 or n == 0:
return 1
else:
cache[n] = fib(n - 2, cache) + fib(n - 1, cache)
return cache[n]
print([fib(n) for n in range(999)])
這樣即使是n的值很大也能很快的計算很出來。
