a simple example of trade-off from fibonacci function to fast-fibonacci function
1350 ワード
#old recursive fib function
def fib(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fib(n-1)+fib(n-2)
print fib(100)
everyone who is a programmer must hear about fibonacci sequence.
It is a good example to study recursion.
However, have you ever tried to compute a lare fibonacci number, like fibonacci(99),
using the recursive method? If you have not, I advise that you should not do that.
The only one goodness is that it will waste of your patience. :)
To make a faster Fibonacci Function, people need spend some memory on saving time.
#new version Fib function
class fibDic(object):
def __init__(self):
self.dic = {}
def isInfibDic(self,n):
if n in self.dic:
return True
return False
def getValue(self,n):
return self.dic[n]
def update(self,n,result):
self.dic[n] = result
aDic = fibDic()
def fastfib(n,aDic):
if aDic.isInfibDic(n):
return aDic.getValue(n)
else:
if n == 0:
result = 1
elif n == 1:
result = 1
else:
result = fastfib(n-1,aDic) +fastfib(n-2,aDic)
aDic.update(n,result)
return result
print fastfib(100,aDic)