矩阵递推斐波那契数列
2022/8/30 23:53:01
本文主要是介绍矩阵递推斐波那契数列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
斐波那契数列都很熟悉,它满足, \(F_{n} = \begin{cases}1&n\leqslant2\\F_{n - 1} + F_{n - 2}&n > 2\end{cases}\) 。
因为\(F_n\)从第三项开始是不断的递推下去的,所以我们可以考虑用矩阵加速递推。
设\(Fib\left( n\right)\)表示一个\(1×2\)的矩阵\(\begin{bmatrix}F_n& F_{n - 1}\end{bmatrix}\).我们希望根据\(Fib\left( n - 1\right) = \begin{bmatrix}F_{n - 1}&F_{n - 2}\end{bmatrix}\)推出\(Fib\left( n\right)\)。
因为\(Fib_n = Fib_{n - 1} + Fib_{n - 2}\),所以我们引入一个辅助矩阵\(base\),第一列应该为\(\begin{bmatrix}1\\1\end{bmatrix}\),这样在进行矩阵乘法运算的时候才能令\(F_{n - 1}\)和\(F_{n - 2}\)相加,从而得出\(F_{n}\),同理为了得出\(F_{n - 1}\),矩阵\(base\)的第二列应该为\(\begin{bmatrix}1\\0\end{bmatrix}\).
综上所述: \(base = \begin{bmatrix}1&1\\1&0\end{bmatrix}\)原式化为$$\begin{bmatrix}F_{n - 1}&F_{n - 2}\end{bmatrix}×\begin{bmatrix}1&1 \\ 1&0\end{bmatrix} = \begin{bmatrix}F_{n - 1} × 1 + F_{n - 2}×1&F_{n - 1}×0 + F_{n - 2}×1\end{bmatrix} = \begin{bmatrix} F_{n}&F_{n - 1} \end{bmatrix}$$
这样我们就可以根据\(\begin{bmatrix}F_{2}&F_{1}\end{bmatrix}\)一直与\(\begin{bmatrix}1&1\\1&0\end{bmatrix}\)进行矩阵乘法运算从而递推出\(\begin{bmatrix}F_{n}&F_{n - 1}\end{bmatrix}\)。
那么定义\(ans = \begin{bmatrix}F_{2}&F_{1}\end{bmatrix},base = \begin{bmatrix}1&1\\1&0\end{bmatrix}\),通过观察发现从\(\begin{bmatrix}F_{2}&F_{1}\end{bmatrix}\)递推出\(\begin{bmatrix}F_{n}&F_{n - 1}\end{bmatrix}\)只需要做\(n - 2\)次矩阵乘法。所以可以得出$$Fib\left( n\right) = ans×base^{n - 2}$$
这篇关于矩阵递推斐波那契数列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署