看到一篇介紹python實(shí)現(xiàn)fibonacci的計(jì)算方式，覺(jué)得甚是有趣糊秆，相信絕大多數(shù)人最初開(kāi)始學(xué)習(xí)編程的時(shí)候伍纫，都是用的遞歸實(shí)現(xiàn)，即以下的示例2；然后了解掌握記憶術(shù)，即示例4和5，python中的記憶術(shù)可以用裝飾器實(shí)現(xiàn)配并，或者functools里面的lru_cache函數(shù)實(shí)現(xiàn)嫉髓；然后才是動(dòng)態(tài)規(guī)劃的示例1梧油；學(xué)習(xí)到了Python之后，才知道可以用生成器實(shí)現(xiàn)类少，即示例3。
第六個(gè)使用標(biāo)準(zhǔn)庫(kù)的方法是我自己加的残吩，這個(gè)方法要注意使用紧唱，可能會(huì)有緩存保存，如果有必要需要清除铜犬。
## Example 1: Using looping technique
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
## Example 2: Using recursion
def fibR(n):
if n==1 or n==2:
return 1
return fibR(n-1)+fibR(n-2)
print fibR(5)
## Example 3: Using generators
a,b = 0,1
def fibI():
global a,b
while True:
a,b = b, a+b
yield a
f=fibI()
f.next()
f.next()
f.next()
f.next()
print f.next()
## Example 4: Using memoization
def memoize(fn, arg):
memo = {}
if arg not in memo:
memo[arg] = fn(arg)
return memo[arg]
## fib() as written in example 1.
fibm = memoize(fib,5)
print fibm
## Example 5: Using memoization as decorator
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, arg):
if arg not in self.memo:
self.memo[arg] = self.fn(arg)
return self.memo[arg]
@Memoize
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
# Example6: using functools's lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
下面是對(duì)于以上算法的總結(jié)：
https://technobeans.com/2012/04/19/5-ways-of-fibonacci-in-python-best-way/
