如何在log(n)时间内求解F(n)=F(n-3)+F(n-2)方程

其中f(0(=0，f(1(=1，f(2(=2。我知道有一种方法可以使用矩阵解释来求解斐波那契。

解决方案是

#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}

但是这个(F(n(=F(n-3(+F(n-2((方程的矩阵是什么？

据我所知，您需要一个矩阵来计算log(n(时间中所描述类型的广义Tribonacci值。

写依赖关系我们可以推导出这样的方程

[Fn+1]   [0  + Fn-1 + Fn-2]    [0  1  1]   [Fn]
[Fn  ] = [Fn  + 0    + 0  ] =  [1  0  0]   [Fn-1]
[Fn-1]   [0 +  Fn-1 +  0  ]    [0  1  0]   [Fn-2]
^
matrix

因此，您可以使用[2,1,0]列的相应功率的上述矩阵

您可以在没有矩阵的log(n(时间(算术运算(中计算这一点，方法是注意F(n(是x^n(x^2+2x(mod x^3-x-1的常数系数。

它的工作原理与矩阵解几乎相同，只是这些2阶多项式是3x3矩阵解中出现的特定矩阵的更紧凑的表示，并且它们的乘积可以使用9次乘法而不是23-27次乘法轻松计算(具体取决于如何进行3x3矩阵乘法(。

#include <stdint.h>
#include <stdio.h>
typedef struct poly_s {
int64_t x0, x1, x2;
} poly_s;
poly_s mul(poly_s a, poly_s b) {
return (poly_s){
a.x0*b.x0 + a.x2*b.x1 + a.x1*b.x2,
a.x1*b.x0 + a.x0*b.x1 + a.x2*b.x2 + a.x2*b.x1 + a.x1*b.x2,
a.x2*b.x0 + a.x1*b.x1 + a.x0*b.x2 + a.x2*b.x2
};
}
poly_s polypow(poly_s x, int n) {
poly_s r = {1, 0, 0};
while(n) {
if (n & 1) r = mul(r, x);
x = mul(x, x);
n >>= 1;
}
return r;
}
int main() {
for (int i = 0; i < 30; i++) {
printf("%d: %ldn", i, mul((poly_s){0, 2, 1}, polypow((poly_s){0, 1, 0}, i)).x0);
}
}

输出：

相关内容

最新更新

热门标签：