我试图通过线性递归来解决http://www.spoj.com/problems/FIBTWIST/问题。但是,由于约束条件很大,我不得不使用矩阵求幂。
我读过http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html
所以根据它形成的方程是

ft(n)=ft(n-1)+ft(n-2)+g(n)    ft(0)=0, ft(0)=1
g(n) =g(n-1)+1                g(1)=0

但是现在我很困惑如何形成A*M=B形式的矩阵A和B。在上面提到的blogspot链接中,它是作为类型7给出的,但是我很难理解它。

最佳答案

定义第三个序列fut,Fibonacci untwist,为
fut(n)=英尺(n)+(n+2)。
那么
fut(n)=ft(n)+n+1=ft(n-1)+ft(n-2)+(n-1)+(n+2)=fut(n-2)+fut(n-1)
所以fut只是Fibonacci递归的另一个解,因此
fut(n)=f(n-1)*fut(0)+f(n)*fut(1)=2*f(n-1)+4*f(n)=2*f(n)+2*f(n+1)=2*f(n+2)
最后
ft(n)=2*f(n+2)-(n+2)
测试:

    f(n):   0  1  1  2  3  5  8 13 21 34
2*f(n+2):   2  4  6 10 16 26 42 68
     n+2:   2  3  4  5  6  7  8  9
   ft(n):   0  1  2  5 10 19 34 59

实际上,最后一行是第二行和第三行的区别。

关于algorithm - 线性递归算法中的矩阵求幂,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22814868/

10-08 22:04
查看更多