《笔记》青蛙跳台阶——斐波那契数列
斐波那契数列
斐波那契数列（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. 递归实现
def fibonacci(n):if n == 0:return 0if n == 1:return 1return fibonacci(n - 1) + fibonacci(n - 2)
测试
print(fibonacci(10)) # 输出 55
- 动态规划实现
复制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)。
- 优化空间复杂度的动态规划
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)。
- 矩阵快速幂实现
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)，适合计算大数的斐波那契数列。
总结
斐波那契数列是一个经典的数学问题，具有广泛的应用场景。通过递归、动态规划、矩阵快速幂等方法，可以高效地计算斐波那契数列的值。在实际应用中，动态规划和矩阵快速幂是最常用的方法。