《笔记》青蛙跳台阶——斐波那契数列

斐波那契数列

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

---

斐波那契数列的定义

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

• ( F(0) = 0 )
• ( F(1) = 1 )
• 对于 ( n >= 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 0if n == 1:return 1return fibonacci(n - 1) + fibonacci(n - 2)

测试

print(fibonacci(10)) # 输出 55

2. 动态规划实现

复制def fibonacci(n):if n == 0:return 0if n == 1:return 1dp = [0] * (n + 1)dp[0] = 0dp[1] = 1for 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 0if n == 1:return 1prev1 = 0  # F(n-2)prev2 = 1  # F(n-1)for i in range(2, n + 1):current = prev1 + prev2prev1 = prev2prev2 = currentreturn prev2

测试

print(fibonacci(10)) # 输出 55

优点：

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

4. 矩阵快速幂实现

import numpy as npdef fibonacci(n):if n == 0:return 0def 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 // 2return resultmatrix = 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)，适合计算大数的斐波那契数列。

总结

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