斐波那契数列：从定义到实现

斐波那契数列：从定义到实现

引用

CSDN

1.

https://m.blog.csdn.net/Devil_MayCare/article/details/145038658

斐波那契数列是一个经典的数学数列，不仅在数学领域有着重要的地位，还在计算机科学、自然界、金融等领域有着广泛的应用。本文将从斐波那契数列的定义出发，介绍其性质、应用场景，并通过递归、动态规划、矩阵快速幂等多种方法实现斐波那契数列的计算。

斐波那契数列

斐波那契数列（Fibonacci Sequence）是一个经典的数学数列，其特点是每一项都是前两项的和。数列的前两项通常定义为 0 和 1（或 1 和 1），后续每一项都是前两项的和。

斐波那契数列的定义

斐波那契数列的定义如下：

• ( F(0) = 0 )
• ( F(1) = 1 )
• 对于 ( n \geq 2 )，( F(n) = F(n-1) + F(n-2) )

数列的前几项为：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

斐波那契数列的性质

斐波那契数列的应用

1. 自然界中的斐波那契数列：

• 植物的叶子排列、花瓣数量、松果的鳞片等都与斐波那契数列有关。
• 例如，向日葵的花瓣数量通常是斐波那契数列中的某个数。

2. 计算机科学：

• 斐波那契数列常用于算法设计和动态规划问题。
• 例如，青蛙跳台阶问题、爬楼梯问题等。

3. 金融领域：

• 斐波那契数列在技术分析中用于预测股票价格的支撑位和阻力位。

4. 艺术与设计：

• 黄金分割比例（与斐波那契数列相关）被广泛应用于建筑、绘画和设计中。

斐波那契数列的实现

以下是斐波那契数列的几种常见实现方式：

1. 递归实现

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

测试：

print(fibonacci(10)) # 输出 55

2. 动态规划实现

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

测试：

print(fibonacci(10)) # 输出 55

优点：

时间复杂度为 O(n)，空间复杂度为 O(n)。

3. 优化空间复杂度的动态规划

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    prev1 = 0  # F(n-2)
    prev2 = 1  # F(n-1)
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev1 = prev2
        prev2 = current
    return prev2

测试：

print(fibonacci(10)) # 输出 55

优点：

时间复杂度为 O(n)，空间复杂度为 O(1)。

4. 矩阵快速幂实现

import numpy as np

def fibonacci(n):
    if n == 0:
        return 0
    def matrix_power(matrix, power):
        result = np.identity(2, dtype=object)
        while power > 0:
            if power % 2 == 1:
                result = np.dot(result, matrix)
            matrix = np.dot(matrix, matrix)
            power = power // 2
        return result
    matrix = np.array([[1, 1], [1, 0]], dtype=object)
    result_matrix = matrix_power(matrix, n - 1)
    return result_matrix[0][0]

测试：

print(fibonacci(10)) # 输出 55

优点：

时间复杂度为 O(logn)，适合计算大数的斐波那契数列。

总结
斐波那契数列是一个经典的数学问题，具有广泛的应用场景。通过递归、动态规划、矩阵快速幂等方法，可以高效地计算斐波那契数列的值。在实际应用中，动态规划和矩阵快速幂是最常用的方法。