斐波那契序列更快,但起始数不同(F [n] = F [n-1] + F [n-2])

Question

(初学者在这里)

我想知道如何找到第n个序列F [n] = F [n-1] + F [n-2].

输入:

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001 
M < 8; M=10^M;

a和b是起始序列号.

n是我需要找到的序列的第n个数.

M是模数,数字变得很快,因此F [n] = F [n]%10 ^ M,我们找到余数,因为只需要第n个数字的最后一位数字

递归方法太慢了:

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

花费O(n)时间的动态编程解决方案也太慢了:

f[i] = f[i-1] + f[i-2];

虽然如果序列的第一个数字是0和1(通过使用这个公式可以在O(log n)中找到第n个数字),如何更快地找到第n个数字的解决方案:

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

但是,如果起始数字类似于25和60,则此公式不起作用.并且递归方法太慢.

所以我想知道如何找到比O(n)更快的序列的第n个数.部分代码会有所帮助.

谢谢.

Answer 1

这个矩阵:

A = / 1  1 \
    \ 1  0 /

当乘以列向量(f _{n + 1},f _n)时,其中f _n是斐波纳契数列中的第n个数,将给出列向量(f _{n + 2},f _{n + 1}),即它将推进你一步到位.无论序列的初始元素是什么,这都有效.

例如:

/ 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

因此,第n个斐波那契数是A ^n-1 v 的第一个元素,其中v是包含f ₁和f ₀的列向量,即序列中的前两个数字.

因此,如果你可以快速计算A ^n-1模数,那么这将给你f _n.这可以使用Exponentiation通过平方来完成,它在O(logn)中工作.只需确保在每次乘法和加法后执行模数以防止数字变得太大.