我正在尝试做 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)=ft(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/