如何在对数(N)时间内求解F(n) = F(n-3) +F(n-2)方程？

Question

其中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))方程的矩阵是什么？

Answer 1

据我所知，在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]列对应的幂中使用上面的矩阵

Answer 2

通过注意F(n)是x^n(x^2+2x) mod ^3-x-1的常数系数，可以在log(n)时间(算术运算)中计算这一点。

它几乎和矩阵解一样，除了这些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: %ld\n", i, mul((poly_s){0, 2, 1}, polypow((poly_s){0, 1, 0}, i)).x0);
    }
}

输出：

0: 0
1: 1
2: 2
3: 1
4: 3
5: 3
6: 4
7: 6
8: 7
9: 10
10: 13
11: 17
12: 23
13: 30
14: 40
15: 53
16: 70
17: 93
18: 123
19: 163
20: 216
21: 286
22: 379
23: 502
24: 665
25: 881
26: 1167
27: 1546
28: 2048
29: 2713