### Python 实现斐波那契数列第 n 项 以下是几种常见的方法用于计算斐波那契数列的第 n 项： #### 方法一：递归方式 递归是一种直观的方式，但由于其时间复杂度较高 \(O(2^n)\)，不适用于较大的 n 值。 ```python def fibonacci_recursive(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else: return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2) ``` 这种方法基于斐波那契数列的定义 \(F(n) = F(n-1) + F(n-2)\)[^3]。 --- #### 方法二：迭代方式 通过循环逐步计算每一项，此方法的时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)。 ```python 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 ``` 这种方式利用了动态规划的思想，仅保留最近两个状态以减少内存消耗[^4]。 --- #### 方法三：矩阵快速幂 这是一种高效的算法，可以将时间复杂度降低到 \(O(\log n)\)。它依赖于以下性质： \[ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} \] ```python import numpy as np def matrix_power(matrix, n): result = np.eye(len(matrix), dtype=int) base = matrix while n > 0: if n % 2 == 1: result = np.dot(result, base) base = np.dot(base, base) n //= 2 return result def fibonacci_matrix(n): if n == 0: return 0 mat = np.array([[1, 1], [1, 0]], dtype=object) res_mat = matrix_power(mat, n - 1) return res_mat[0][0] ``` 这种实现充分利用了线性代数的知识来加速计算过程[^1]。 --- #### 方法四：闭式公式 (Binet's Formula) 使用黄金比例 \(\phi\) 和反黄金比例 \(-\frac{1}{\phi}\) 的关系可以直接得出结果。然而，由于浮点运算误差，可能不适合非常大的 n 值。 ```python from math import sqrt def fibonacci_binet(n): phi = (1 + sqrt(5)) / 2 psi = (1 - sqrt(5)) / 2 return int((pow(phi, n) - pow(psi, n)) / sqrt(5)) ``` 这个公式的理论基础来源于斐波那契数列与黄金分割的关系[^3]。 --- ### 总结 以上四种方法各有优劣，具体选择取决于实际需求和性能约束条件。对于较小的 n 值，推荐使用 **递归** 或 **迭代**；而对于更大的 n 值，则应考虑更高效的方法如 **矩阵快速幂** 或 **闭式公式**。