Python实现斐波那契数列的十种计算方法
实现斐波那契数列的方法有很多种,这里我将介绍十种不同的Python实现方式:
递归法:
def fibonacci_recursive(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
递归法(带备忘录):
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 0:
return 0
elif n == 1:
return 1
else:
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
迭代法:
def fibonacci_iterative(n):
if n <= 0:
return 0
elif n == 1:
return 1
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
动态规划法:
def fibonacci_dp(n):
if n <= 0:
return 0
elif n == 1:
return 1
fib = [0] * (n + 1)
fib[1] = 1
for i in range(2, n + 1):
fib[i] = fib[i - 1] + fib[i - 2]
return fib[n]
生成器法:
def fibonacci_generator():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
# 使用生成器
fib_gen = fibonacci_generator()
for _ in range(10):
print(next(fib_gen))
矩阵快速幂法:
import numpy as np
def fibonacci_matrix(n):
def matrix_mult(m1, m2):
return np.dot(m1, m2)
def matrix_pow(matrix, power):
result = np.array([[1, 0], [0, 1]])
while power:
if power % 2:
result = matrix_mult(result, matrix)
matrix = matrix_mult(matrix, matrix)
power //= 2
return result
fib_matrix = np.array([[1, 1], [1, 0]])
result_matrix = matrix_pow(fib_matrix, n)
return result_matrix[0][1]
Binet公式(近似法):
import math
def fibonacci_binet(n):
sqrt_5 = math.sqrt(5)
phi = (1 + sqrt_5) / 2
psi = (1 - sqrt_5) / 2
return int((math.pow(phi, n) - math.pow(psi, n)) / sqrt_5)
尾递归法:
def fibonacci_tail_recursive(n, a=0, b=1):
if n <= 0:
return a
elif n == 1:
return b
else:
return fibonacci_tail_recursive(n-1, b, a+b)
Caché装饰器法:
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_lru(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_lru(n-1) + fibonacci_lru(n-2)
闭包法:
def fibonacci_closure():
cache = {0: 0, 1: 1}
def fib(n):
if n in cache:
return cache[n]
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fibonacci = fibonacci_closure()
print(fibonacci(10))
这些方法各有优缺点,选择时需要根据具体的应用场景,并考虑到时间复杂度和空间复杂度。