系列文章目录
Python 算法学习：斐波那契数列（10种方法计算第n项）
文章目录
系列文章目录一、算法需求二、方法+源码方法1：递归方法2：迭代方法3：动态规划方法4：生成器方法5：矩阵快速幂方法6：闭包方法7：公式法（Binet's Formula）方法8：利用Python的内置函数方法9：基于生成器的迭代方法10：列表推导式 总结
一、算法需求
采用多种方法，来计算斐波那契数列的第n项。
二、方法+源码
方法1：递归
递归是最直观的方法，但效率较低，因为它会重复计算很多子问题。代码如下：
def fibonacci_recursive(n): if n <= 0: return 0 elif n == 1: return 1 else: return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)# 测试递归方法print(fibonacci_recursive(10)) # 输出斐波那契数列的第10项方法2：迭代
迭代方法比递归更高效，因为它避免了重复计算。代码如下：
def fibonacci_iterative(n): if n <= 0: return 0 a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b# 测试迭代方法print(fibonacci_iterative(10)) # 输出斐波那契数列的第10项方法3：动态规划
动态规划方法通过存储已经计算过的值来避免重复计算，这种方法比递归更高效。代码如下：
def fibonacci_dp(n, memo={}): if n in memo: return memo[n] if n <= 0: return 0 elif n == 1: return 1 memo[n] = fibonacci_dp(n-1, memo) + fibonacci_dp(n-2, memo) return memo[n]# 测试动态规划方法print(fibonacci_dp(10)) # 输出斐波那契数列的第10项方法4：生成器
使用Python的生成器可以创建一个斐波那契数列生成器，每次调用时返回下一个斐波那契数。代码如下：
def fibonacci_generator(): a, b = 0, 1 while True: yield a a, b = b, a + b# 使用生成器gen = fibonacci_generator()for _ in range(11): print(next(gen)) # 输出斐波那契数列的前11项方法5：矩阵快速幂
斐波那契数列可以通过矩阵乘法来表示，其中每个斐波那契数可以看作是矩阵的幂次方的结果。这种方法利用了矩阵的快速幂算法。在这个实现中：matrix_multiply 函数用于计算两个矩阵的乘积。
matrix_power 函数用于计算矩阵的幂次方，这是快速幂算法的核心。
fibonacci_matrix 函数使用上述两个函数来计算斐波那契数列的第n项。
这种方法利用了斐波那契数列与矩阵乘法之间的关系，通过快速幂算法高效地计算出结果。这种方法特别适合计算非常大的斐波那契数，因为它的时间复杂度远低于递归和迭代方法。
代码如下：
def matrix_multiply(a, b): return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]], [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]]def matrix_power(matrix, n): if n == 1: return matrix if n % 2 == 0: half_power = matrix_power(matrix, n // 2) return matrix_multiply(half_power, half_power) else: return matrix_multiply(matrix, matrix_power(matrix, n - 1))def fibonacci_matrix(n): if n <= 0: return 0 base_matrix = [[1, 1], [1, 0]] result_matrix = matrix_power(base_matrix, n - 1) return result_matrix[0][0]# 测试矩阵快速幂方法print(fibonacci_matrix(10)) # 输出斐波那契数列的第10项方法6：闭包
使用闭包来存储计算斐波那契数列所需的状态（即前两个数），从而避免重复计算。在这个实现中：fibonacci_closure 函数定义了一个内部函数 fib，它使用 nonlocal 关键字来修改外部函数中的变量 a 和 b。
fib 函数递归地计算斐波那契数列的第n项，同时更新 a 和 b 的值。
当 fibonacci_closure 被调用时，它返回 fib 函数，这个函数现在关联了 a 和 b 的初始值。
这种方法的优点是它利用了闭包的特性来存储状态，避免了全局变量的使用，并且可以重复调用而不需要重新初始化状态。这在某些情况下可以提高代码的封装性和可读性。不过，对于斐波那契数列的计算，这种方法的性能并不比迭代或动态规划方法更优，但它展示了Python闭包的有趣用法。
代码如下：
def fibonacci_closure(): a, b = 0, 1 def fib(n): nonlocal a, b if n == 0: return a elif n == 1: return b else: a, b = b, a + b return fib(n - 1) return fib# 创建一个斐波那契闭包函数fib = fibonacci_closure()# 测试闭包方法print(fib(10)) # 输出斐波那契数列的第10项方法7：公式法（Binet’s Formula）
Binet公式可以直接计算斐波那契数列的第n项，但因为涉及到无理数的计算，当n较大时会有精度问题。代码如下：
import mathdef fibonacci_binet(n): phi = (1 + math.sqrt(5)) / 2 # 黄金分割比 psi = (1 - math.sqrt(5)) / 2 return round((phi**n - psi**n) / math.sqrt(5))# 测试公式法print(fibonacci_binet(10)) # 输出斐波那契数列的第10项方法8：利用Python的内置函数
Python的functools模块提供了一个lru_cache装饰器，可以缓存函数的最近调用结果，从而优化递归函数的性能。代码如下：
from functools import lru_cache@lru_cache(maxsize=None)def fibonacci_cached(n): if n < 2: return n return fibonacci_cached(n-1) + fibonacci_cached(n-2)# 测试缓存优化的递归方法print(fibonacci_cached(10)) # 输出斐波那契数列的第10项方法9：基于生成器的迭代
使用Python的生成器，可以创建一个迭代器，每次迭代返回斐波那契数列的下一个值。代码如下：
def fibonacci_generator(n): a, b = 0, 1 for _ in range(n): yield a a, b = b, a + b# 测试生成器迭代方法for value in fibonacci_generator(10): print(value, end=' ') # 输出斐波那契数列的前10项方法10：列表推导式
使用Python的列表推导式来计算斐波那契数列的第n项的方法。这种方法利用了列表推导式的强大功能，可以快速生成斐波那契数列的前n项，然后直接返回第n项。在这个实现中：我们首先检查n是否小于或等于1，如果是，直接返回斐波那契数列的第0项或第1项。
对于n > 1的情况，我们使用列表推导式来生成斐波那契数列的前n项。
列表推导式中的enumerate([0, 1] + [0] * (n-1))用于生成一个初始列表，其中包含两个初始斐波那契数和足够多的0，以确保列表长度至少为n。
对于列表中的每个索引i，如果i < 2，直接使用初始值0或1。否则，使用递归调用fibonacci_list_comprehension(i-1) + fibonacci_list_comprehension(i-2)来计算斐波那契数。
最后，返回列表的第n项。
这种方法虽然简洁，但由于它在列表推导式中使用了递归调用，可能会导致性能问题，尤其是在计算较大的n值时。因此，它更适合于教学和理解斐波那契数列的生成过程，而不是用于实际的大规模计算。
代码如下：
def fibonacci_list_comprehension(n): if n <= 0: return 0 elif n == 1: return 1 else: return [x if i < 2 else (fibonacci_list_comprehension(i-1) + fibonacci_list_comprehension(i-2)) for i, x in enumerate([0, 1] + [0] * (n-1))][n]# 测试列表推导式方法print(fibonacci_list_comprehension(10)) # 输出斐波那契数列的第10项总结
1. 递归方法：
直接使用递归定义来计算斐波那契数。
简单直观，但效率低，因为存在大量重复计算。
2. 迭代方法：
使用循环迭代计算斐波那契数，避免了递归的重复计算。
效率较高，适用于计算较大数值。
3. 动态规划：
通过存储已计算的结果来避免重复计算，通常用于递归函数的优化。
减少了计算次数，提高了效率。
4. 矩阵快速幂：
利用斐波那契数列与矩阵乘法的关系，通过快速幂算法高效计算。
时间复杂度为O(log n)，适合计算大数。
5. 闭包：
使用闭包来存储计算状态，避免全局变量。
封装性好，但性能并不比迭代或动态规划更优。
6. Binet公式：
直接使用数学公式计算斐波那契数，涉及无理数运算。
计算快速，但可能存在精度问题。
7. 内置函数优化：
使用Python的functools.lru_cache装饰器优化递归函数。
缓存递归调用结果，提高性能。
8. 基于生成器的迭代：
使用Python的生成器逐项生成斐波那契数列。
适合逐项处理的场景，内存效率高。
9. 列表推导式：
使用列表推导式快速生成斐波那契数列。
代码简洁，但可能因递归调用而导致性能问题。
总而言之，每种方法都有其适用场景和优缺点。递归和迭代是最基础的方法，而动态规划和矩阵快速幂提供了更高效的计算方式。闭包和列表推导式展示了Python语言特性的应用，而Binet公式则提供了一种数学上的解决方案。内置函数优化是一种实用的技巧，可以显著提高递归函数的性能。基于生成器的方法则适用于需要逐个处理斐波那契数的场景。