Python算法题----玩转fibonacci数列
fibonacci数列是个很常见的面试题，相信大家都见识过，反正我碰见过两次。递归是最容易想到的办法。但是写一个递归，往往面试官并不满意，会追问。这个递归存在什么问题啊。有没有其它办法啊……。办法总比问题多，跳跳大路通帝都。下面就总结一下。把程序写到面试官的心缝里！递归法
这个递归存在的最严重的问题就是重复计算，在代码的递归分支里可以看到函数被递归调用了两次，那么很多函数其实都被重复计算了。最后再来解决这个问题。
def fib01(n):
if n == 1 or n == 2:
return n
else:
return fib01(n-1) + fib01(n-2)
递推法1
使用一个列表来存储整个fibonnci数列，所求的即为列表的第n项
def fib02(n):
if n == 1 or n == 2:
return n
else:
arr =
i = 3
for i in range(3, n+1):
arr.append(arr + arr)
return arr
递推法2
声明几个历史变量不断计算数列的值，并且交换变量
def fib03(n):
if n == 1 or n == 2:
return n
else:
x = 1
y = 2
for i in range(3, n+1):
fi = x + y
x = y
y = fi
return y
缓存递归中间结果
定义一个字典，将递归函数的计算结果存入_fib_cache，每次判断该函数是否在缓存中，在直接返回，不在，计算并放入缓存
_fib_cache = {}
def fib04(n):
if n in _fib_cache:
return _fib_cache
else:
_fib_cache = n if n <= 2 else fib04(n-1) + fib04(n-2)
return _fib_cache
有了缓存，生活美好了很多，但是看着有点别扭。孤零零的_fib_cache，弄个装饰器多好，这明显可以有个装饰器的。
函数装饰器
def memo(f):
cache = {}
def decorated(*args):
if args in cache:
return cache
else:
cache = f(*args)
return cache
return decorated
有了这个装饰器函数，我们就可以装饰我们的递归函数了
@memo
def fib01(n):
if n == 1 or n == 2:
return n
else:
return fib01(n-1) + fib01(n-2)
页:
[1]