import time
#直接实现
def fibonacci1(n):
t=0
after=1
for i in range(0,n):
t,after=after,after+t
return t
start=time.clock()
print fibonacci1(200)
end=time.clock()
print 'time of fibonacci1',end-start
2.递归（加入缓存）：
import time
def fibonacci(n,d):#递归
if n==0 :
return 0
if n==1:
return 1
else:
if cache(n,d)!=-1:
return cache(n,d)
else:
d[n]=fibonacci(n-1,d)+fibonacci(n-2,d)
return fibonacci(n-1,d)+fibonacci(n-2,d)
def cache(n,d):
if n in d:
return int(d[n])
else:
return -1
d={}
start=time.clock()
print fibonacci(200,d)
end=time.clock()
print 'time of fibonacci',end-start
import time
def best(n):
t=5**0.5
a=((t+1)/2)**n-((1-t)/2)**n
a=a/t
return a
start=time.clock()
print best(200)
end=time.clock()
print 'time of best',end-start
4.运行结果
280571172992510140037611932413038677189525
time of fibonacci 0.000887445364758
280571172992510140037611932413038677189525
time of fibonacci1 2.35444688609e-05
2.80571172993e+41
time of best 6.94259979233e-06
，SO想试下多种解法