斐波那契数列 Fibonacci 是一个经典数列问题,应用十分广泛。
其递推定义如下:
f(0)=1f(1)=1f(n)=f(n−1)+f(n−2)按照定义直接编写程序很容易爆栈,稍微大一点的数就无法计算,如 100,更不用说成千上万了。
1
2
3
4
| def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
|
经典的方法是动态规划,可以很轻松计算 100_000 :
1
2
3
4
5
| def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
|
还有更多高效算法,如矩阵快速幂。