当前位置:首页>python>Python编程基础算法--斐波那契数列的矩阵算法

Python编程基础算法--斐波那契数列的矩阵算法

  • 2026-10-21 13:28:44
Python编程基础算法--斐波那契数列的矩阵算法
计算斐波那契数列是存在一个矩阵算法的。以后面试的时候如果被问到了,在回答完传统的递归/循环解法后,进一步提到矩阵解法,或许能成为加分项呢!
斐波那契数列的递推公式为F[n] = F[n-1] + F[n-2],考虑把连续两项打包成一个向量[ F[n], F[n-1] ],根据递推公式可以得到下面的矩阵运算关系(小伙伴们可以根据矩阵乘法展开后自行验证一下)
经过反复代入可得
所以为了计算F[n],我们可以直接计算右边矩阵运算的结果,然后取出第一行第一列的元素即可。
关于矩阵算法还有两点拓展,感兴趣的小伙伴们可以自己研究一下先~
  • 通过矩阵快速幂可以实现O(logN)的计算复杂度,快速幂可是编程竞赛的一大神器啊
  • 对右侧矩阵进行特征值分解便可以发现斐波那契数列与黄金分割的关系
借助NumPy库后的python代码实现如下,还是比较简洁的
import numpy as npdef fibonacci_matrix(n):    if n < 0:        raise ValueError("斐波那契数的索引不能为负数")    if n == 0:        return 0    if n == 1:        return 1    # 定义基本斐波那契矩阵    base_matrix = np.array([[1, 1], [1, 0]], dtype=object)    # 计算矩阵的 n-1 次幂    result_matrix = np.linalg.matrix_power(base_matrix, n-1)    # 提取第 n 个斐波那契数    return result_matrix[0, 0]# 测试代码if __name__ == "__main__":    max_n = 15    for i in range(max_n):        print(f"F({i}) = {fibonacci_matrix(i)}")

推荐合集

推荐文章

最新文章

随机文章