矩阵快速幂的应用——优化递推过程

65 阅读 0 评论 43 点赞

我是靠谱客的博主忧郁流沙，最近开发中收集的这篇文章主要介绍矩阵快速幂的应用——优化递推过程，觉得挺不错的，现在分享给大家，希望可以做个参考。

矩阵快速幂可用来优化递推

矩阵快速幂的实现及一些详细介绍可以参考我的另一篇文章：
数论常用内容——矩阵快速幂

首先，需要先构造合适的初始状态（第一个矩阵）然后，利用此矩阵和矩阵乘法的性质，使用快速幂的手段求出之后的状态

构造矩阵可以根据矩阵乘法的实现特点来构造，利用合适的性质可以简化运算

例如：给出矩阵A，求S = A + A2 + A3 + … + Ak

分析：把问题转化以加速，令

B = A  I

    0  I

则B^(k + 1) = A^(k + 1)      I + A + A2 + A3 + … + Ak

             0                          I

再比如，求fibnacci数列的时候用

1 1
0 1
作为首项再做n次方求fib（n）

以上就是忧郁流沙为你收集整理的矩阵快速幂的应用——优化递推过程的全部内容，希望文章能够帮你解决矩阵快速幂的应用——优化递推过程所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。