在O(logn)中找到第n个fib数

Question

我试图解决这个问题:SPOJ问题.

经过一些研究,我发现它归结为第n个纤维数的简单计算,但是n可以变得非常大,因此O(n)解决方案不会有任何好处.谷歌搜索我发现你可以计算O(logn)中的第n个fib数,也可以计算出完全相同的代码示例:

long long fibonacci(int n)
{
    long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
    int i,j,k;
    while(n)
    {
        if(n&1)
        {
            memset(tmp,0,sizeof tmp);
            for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                        tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
            for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
        }
        memset(tmp,0,sizeof tmp);
        for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                    tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
        for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
        n/=2;
    }
    return (ret[0][1]);
}

我试图修改它以解决问题,我仍然得到WA:http://ideone.com/3TtE5m

我计算模运算错了吗？或者是其他问题？

Answer 1

你的意思是我希望的第n个斐波那契.

为此,您需要对此处描述的斐波那契数字进行矩阵分解.

基本的想法是你采用Donald E. Knuth矩阵身份形式的斐波那契数字,即:

而不是以传统的方式计算斐波纳西数,你将尝试找到(k)的幂的矩阵,其中k被要求给出数.

所以这解决了k矩阵乘法中的问题,因为我们可以用更简单的方式来解决这个问题.

可是等等 !我们可以优化矩阵乘法.我们不是先进行k乘法,而是先对它进行平方,然后进行乘法的一半.我们可以继续这样做.因此,如果给定的数字是2 ^ a,那么我们可以分步进行.通过保持矩阵的平方.

如果矩阵不是正方形,我们可以对数字进行二进制分解,看看是否将给定的平方矩阵作为最终乘积.

在每次乘法后的情况下,您还需要将模运算符123456应用于每个矩阵编号.

希望我的解释有帮助,如果没有看到更清晰和更长的链接.

实际上还有一个任务的警告,因为要求你提供一些给定数量模数的斐波纳契数.您还应该证明采用每个矩阵元素的提醒不会改变操作.换句话说,如果我们乘以矩阵并提醒我们实际上仍然得到斐波那契数字提醒.但是由于提醒操作是分布式的并且相乘,它实际上确实产生了正确的结果.

Answer 2

斐波那契数以连续分数的连续收敛的比率出现 ，并且由任何连分数的连续收敛形成的矩阵具有+1或的行列式?1。

矩阵表示给出了斐波那契数列的以下封闭形式表达式，即

矩阵乘以n时间，因为只有这样我们才能得到(n+1)th斐波那契数作为(0, 0)结果矩阵中行和列的元素。

如果我们在不使用递归矩阵乘法的情况下应用上述方法，则Time Complexity: O(n)和Space Complexity: O(1)。

但是我们想要Time Complexity: O(log n)，所以我们必须优化上面的方法，这可以通过矩阵的递归乘法来获得nth幂。

可以在下面找到上述规则的实现。

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/*
The function that returns nth Fibonacci number.
*/

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];
}

/*
Optimized using recursive multiplication.
*/

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() {
    printf("%d\n", fib(15));
    /*
    15th Fibonacci number is 610.
    */
    return 0;
}