求斐波那契(Fibonacci)数列通项的七种实现方法

求斐波那契数列通项的七种实现方法

方法一：递归

斐波那契数列的递推公式为：F(n) = F(n-1) + F(n-2)，为了求得第 n 个斐波那契数，可以通过递归求解，但是递归实现时间复杂度为 O(2^n)，随着 n 的增大，运行效率会非常低下。

def fib_recursion(n):
    if n <= 1:
        return n
    return fib_recursion(n-1) + fib_recursion(n-2)

方法二：记忆化递归

方法一中的递归实现重复计算较多，可以通过使用记忆化的方式来优化时间复杂度，将已经计算过的斐波那契数进行缓存，从而在计算后续斐波那契数时避免重复计算。

def fib_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)
    return memo[n]

示例：

>>> fib_memoization(10)
55

方法三：迭代

最简单直接的方法是迭代实现，从前往后计算斐波那契数列的每一项。

def fib_iteration(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a+b
    return b

示例：

>>> fib_iteration(10)
55

方法四：矩阵乘法

使用矩阵的乘法运算可以将斐波那契数列的计算时间复杂度降至 O(log n)。

import numpy as np

def matrix_pow(mat, n):
    res = np.eye(mat.shape[0], dtype=int)
    while n > 0:
        if n & 1 == 1:
            res = np.matmul(res, mat)
        mat = np.matmul(mat, mat)
        n >>= 1
    return res

def fib_matrix(n):
    if n <= 1:
        return n
    mat = np.array([[1, 1], [1, 0]], dtype=int)
    res_mat = matrix_pow(mat, n-1)
    return res_mat[0, 0]

示例：

>>> fib_matrix(10)
55

方法五：通项公式

斐波那契数列的通项公式为：F(n) = (1/sqrt(5)) * ((1+sqrt(5))/2)^n - (1/sqrt(5)) * ((1-sqrt(5))/2)^n。

import math

def fib_formula(n):
    sqrt_5 = math.sqrt(5)
    phi = (1+sqrt_5)/2
    psi = (1-sqrt_5)/2
    return int((pow(phi, n)-pow(psi, n))/sqrt_5)

示例：

>>> fib_formula(10)
55

方法六：通项公式利用矩阵乘法

通过矩阵乘法，可以将斐波那契数列的通项公式的计算时间复杂度降至 O(log n)。

def fib_formula_matrix(n):
    if n <= 1:
        return n
    mat = np.array([[1, 1], [1, 0]], dtype=int)
    phi = np.array([[1+math.sqrt(5), 1-math.sqrt(5)]])/2
    res_mat = matrix_pow(phi.dot(mat), n-1)
    return res_mat[0, 0]

示例：

>>> fib_formula_matrix(10)
55

方法七：通项公式求和

使用斐波那契数列的通项公式可以简单地求得斐波那契数列的前 n 项的和。

def fib_formula_sum(n):
    sqrt_5 = math.sqrt(5)
    phi = (1+sqrt_5)/2
    psi = 1-phi
    return int((pow(phi, n+1)-pow(psi, n+1))/sqrt_5 - 1)

示例：

>>> fib_formula_sum(10)
143

以上就是七种实现斐波那契数列通项的方法，不同的方法各有优劣，选择适合自己的方法可以在实际运用中提高代码效率。