提示信息

Python实现斐波那契数列的十种计算方法

喜怒无常 已关注

实现斐波那契数列的方法有很多种,这里我将介绍十种不同的Python实现方式:

  1. 递归法:

    1. def fibonacci_recursive(n):
    2. if n <= 0:
    3. return 0
    4. elif n == 1:
    5. return 1
    6. else:
    7. return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
  2. 递归法(带备忘录):

    1. def fibonacci_memo(n, memo={}):
    2. if n in memo:
    3. return memo[n]
    4. if n <= 0:
    5. return 0
    6. elif n == 1:
    7. return 1
    8. else:
    9. memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    10. return memo[n]
  3. 迭代法:

    1. def fibonacci_iterative(n):
    2. if n <= 0:
    3. return 0
    4. elif n == 1:
    5. return 1
    6. a, b = 0, 1
    7. for _ in range(2, n + 1):
    8. a, b = b, a + b
    9. return b
  4. 动态规划法:

    1. def fibonacci_dp(n):
    2. if n <= 0:
    3. return 0
    4. elif n == 1:
    5. return 1
    6. fib = [0] * (n + 1)
    7. fib[1] = 1
    8. for i in range(2, n + 1):
    9. fib[i] = fib[i - 1] + fib[i - 2]
    10. return fib[n]
  5. 生成器法:

    1. def fibonacci_generator():
    2. a, b = 0, 1
    3. while True:
    4. yield a
    5. a, b = b, a + b
    6. # 使用生成器
    7. fib_gen = fibonacci_generator()
    8. for _ in range(10):
    9. print(next(fib_gen))
  6. 矩阵快速幂法:

    1. import numpy as np
    2. def fibonacci_matrix(n):
    3. def matrix_mult(m1, m2):
    4. return np.dot(m1, m2)
    5. def matrix_pow(matrix, power):
    6. result = np.array([[1, 0], [0, 1]])
    7. while power:
    8. if power % 2:
    9. result = matrix_mult(result, matrix)
    10. matrix = matrix_mult(matrix, matrix)
    11. power //= 2
    12. return result
    13. fib_matrix = np.array([[1, 1], [1, 0]])
    14. result_matrix = matrix_pow(fib_matrix, n)
    15. return result_matrix[0][1]
  7. Binet公式(近似法):

    1. import math
    2. def fibonacci_binet(n):
    3. sqrt_5 = math.sqrt(5)
    4. phi = (1 + sqrt_5) / 2
    5. psi = (1 - sqrt_5) / 2
    6. return int((math.pow(phi, n) - math.pow(psi, n)) / sqrt_5)
  8. 尾递归法:

    1. def fibonacci_tail_recursive(n, a=0, b=1):
    2. if n <= 0:
    3. return a
    4. elif n == 1:
    5. return b
    6. else:
    7. return fibonacci_tail_recursive(n-1, b, a+b)
  9. Caché装饰器法:

    1. from functools import lru_cache
    2. @lru_cache(maxsize=None)
    3. def fibonacci_lru(n):
    4. if n <= 0:
    5. return 0
    6. elif n == 1:
    7. return 1
    8. else:
    9. return fibonacci_lru(n-1) + fibonacci_lru(n-2)
  10. 闭包法:

    1. def fibonacci_closure():
    2. cache = {0: 0, 1: 1}
    3. def fib(n):
    4. if n in cache:
    5. return cache[n]
    6. cache[n] = fib(n-1) + fib(n-2)
    7. return cache[n]
    8. return fib
    9. fibonacci = fibonacci_closure()
    10. print(fibonacci(10))

这些方法各有优缺点,选择时需要根据具体的应用场景,并考虑到时间复杂度和空间复杂度。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
喜怒无常 关注 已关注

最近一次登录:2024-11-21 09:58:04   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图