Python 斐波那契数列
数学实例 014
题目
斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13…,从第三项起每一项等于前两项之和。用生成器输出前 20 项,并用缓存优化递归版本。
参考代码
from functools import lru_cache
def fib_gen(n):
a, b = 0, 1
for _ in range(n):
yield a
a, b = b, a + b
print("前 20 项:", list(fib_gen(20)))
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
print("第 100 项:", fib(100))执行以上代码输出结果为:
前 20 项: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
第 100 项: 354224848179261915075代码解析
不加缓存的递归会重复计算大量子问题,fib(40) 就要算很久。@lru_cache 会记住已经算过的结果,让递归版本的复杂度降到线性。