代码之家 › 专栏 › 技术社区 › Ratiess

具有不同种子的O log(N)中的斐波那契

space-complexity big-o time-complexity algorithm c#

Ratiess · 技术社区 · 8 年前

此代码是从mathemathics wiki中的伪代码翻译而来,用于解决O log(n)中的斐波那契问题。

当你想改变斐波那契(1,0)的种子时,问题就来了,这是比编程更复杂的数学问题。。。

所以A和B从哪里开始,例如种子5,6?

谢谢你的时间!

public static BigInteger Fib(int A, int B, int n)
        {
            if (n <= 0)
                return 0;

            n = n - 1;
            _auxOne = 0;
            _auxTwo = 1;

            Matrix[0, 0] = _auxTwo; //a
            Matrix[0, 1] = _auxOne; //b
            Matrix[1, 0] = _auxOne; //c
            Matrix[1, 1] = _auxTwo + _auxOne; //d

            while (n > 0)
            {
                if (n % 2 != 0)
                {
                    _auxOne = Matrix[1, 1] * Matrix[0, 1] + Matrix[1, 0] * Matrix[0, 0]; //(db+ca)
                    _auxTwo = Matrix[1, 1] * (Matrix[0, 1] + Matrix[0, 0]) + Matrix[1, 0] * Matrix[0, 1]; //(d(b+a)+cb)
                    Matrix[0, 0] = _auxOne;
                    Matrix[0, 1] = _auxTwo;
                }
                _auxOne = BigInteger.Pow(Matrix[1, 0], 2) + BigInteger.Pow(Matrix[1, 1], 2); //(cÂ²+dÂ²)
                _auxTwo = Matrix[1, 1] * (2 * Matrix[1, 0] + Matrix[1, 1]); //(d*(2c+d))
                Matrix[1, 0] = _auxOne;
                Matrix[1, 1] = _auxTwo;

                n = n / 2;
            }
            return Matrix[0, 0] + Matrix[0, 1];
        }

1 回复 | 直到 8 年前

vitalygolub 8 年前

好的,正如我之前在评论中写的,实际上我们只需要“正规”斐波那契矩阵乘以我们的带种子的修改矩阵,所以我的代码的一部分是现有运算代码的变异。我只做了2个更改-我需要整个矩阵而不是计算结果,并用Int64替换BigInteger以避免额外的引用。

public static Int64 PerversationFib(int A, int B, int n) 
{
    if (n <= 0)
        return 0;

    if (n == 1)
        return A + B;
    else 
    {
        Int64[,] myMatrix = new Int64[2, 2] { { A , B }, { B, A+B} };
        Int64[,] fibMatrix = Fib(n);

        //a11Â·b11 + a12Â·b21
        return myMatrix[0, 0] * fibMatrix[0, 0] + myMatrix[0, 1] * fibMatrix[1, 0];  

    }

}

public static Int64[,] Fib( int n)
{
    if (n <= 0)
        return null;

    //n = n - 1;
   Int64 _auxOne = 0, _auxTwo = 1;
   Int64[,] Matrix = new Int64[2, 2]; 

   Matrix[0, 0] = _auxTwo; //a
   Matrix[0, 1] = _auxOne; //b
   Matrix[1, 0] = _auxOne; //c
   Matrix[1, 1] = _auxTwo + _auxOne; //d


    while (n > 0)
    {
        if (n % 2 != 0)
        {
            _auxOne = Matrix[1, 1] * Matrix[0, 1] + Matrix[1, 0] * Matrix[0, 0]; //(db+ca)
            _auxTwo = Matrix[1, 1] * (Matrix[0, 1] + Matrix[0, 0]) + Matrix[1, 0] * Matrix[0, 1]; //(d(b+a)+cb)
            Matrix[0, 0] = _auxOne;
            Matrix[0, 1] = _auxTwo;
        }
        _auxOne = Matrix[1, 0] * Matrix[1, 0]  +Matrix[1, 1]*Matrix[1,1]; //(cÂ²+dÂ²)
        _auxTwo = Matrix[1, 1] * (2 * Matrix[1, 0] + Matrix[1, 1]); //(d*(2c+d))
        Matrix[1, 0] = _auxOne;
        Matrix[1, 1] = _auxTwo;

        n = n / 2;
    }
    Matrix[1, 0] = Matrix[0, 1];
    Matrix[1, 1] = Matrix[0, 0]+Matrix[0,1] ;
    return Matrix;
}