最简单版本
def fib(n):
return 1 if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(30))
1346269
使用装饰器缓存优化
使用缓存达到与循环数组相似的效果
def cache(fun):
fibs = {}
def wrapper(n):
if n in fibs:
return fibs[n]
res = fun(n)
fibs[n] = res
return res
return wrapper
@cache
def fib(n):
return 1 if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(30))
1346269
矩阵快速幂
import numpy as np
def power(m, n):
if n <= 1:
return m
t = power(m, n // 2)
if n % 2 == 0:
return np.dot(t, t)
return np.dot(m, np.dot(t, t))
def fib(n):
mat = np.array([[1, 1], [1, 0]])
t = power(mat, n)[0][1]
print(t)
for i in range(1, 40):
fib(i)
1
1
2
3
5
8
13
21
34
55
89
| 
转播
