algorithm - 递归关系的生成矩阵

Question

Answered on Math.SE, generating matrix for a recurrence relation

对于循环 f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4) ，如何得到生成矩阵，用矩阵求幂求解？

对于f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)，对应的生成矩阵是:

| a  0  c |   |  f(n)  |   | f(n+1) |
| 1  0  0 | x | f(n-1) | = |  f(n)  |
| 0  1  0 |   | f(n-2) |   | f(n-1) |

那么如何为所需的重复获得相同的值呢？此外，任何重复的程序应该是什么形式:

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k) ?

谢谢。

Answer 1

尝试阅读这篇文章 - http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html

我相信你看完后可以自己构造矩阵。