找到斐波纳契数的总和

Question

什么是计算斐波纳契数从总和最有效的方式F(n),以F(m)其中F(n)和F(m)是第n和分别第m斐波那契数和0 = <N <= M <10 ⁹(以F(0)= 0,F(1)= 1).

例如,如果n=0,m=3我们需要找到F(0)+F(1)+F(2)+F(3).

只是通过蛮力,它将需要很长时间的范围n和m提到.如果可以通过矩阵求幂来完成那么如何？

Answer 1

前两个答案(最老的答案)似乎对我不正确.根据在其中一个答案中已经引用的讨论,第一个n斐波纳契数的总和由下式给出:

SumFib(n) = F[n+2] - 1                          (1)

现在,让我们定义SumFib(m, n)斐波纳契数从m和n 包含的总和(根据OP的要求)(见脚注).所以:

SumFib(m, n) = SumFib(n) - SumFib(m-1)

注意第二个术语.这是因为SumFib(m)包括F[m],但我们希望从金额F[m]来F[n] 包容.因此,我们减去总结到F[m-1],从总结到F[n].简单的幼儿园数学,不是吗？:-)

SumFib(m, n) = SumFib(n) - SumFib(m-1)
             = (F[n+2] - 1) - (F[m-1 + 2] - 1)    [using eq(1)]
             = F[n+2] - 1 - F[m+1] + 1
             = F[n+2] - F[m+1]

Therefore, SumFib(m, n) = F[n+2] - F[m+1]                    (2)

例:

m = 3, n = 7
Sum = F[3] + F[4] + F[5] + F[6] + F[7]
    = 2 + 3 + 5 + 8 + 13
    = 31

并通过使用(2)上面派生:

SumFib(3, 7) = F[7+2] - F[3+1]
             = F[9] - F[4]
             = 34 - 3
             = 31

奖励:
当m和n很大,需要高效的算法来生成斐波那契数.这是一篇非常好的文章,解释了一种方法.

脚注:在问题m和nOP满足这个范围:0 =< n <= m但在我的回答中,范围有点改变,它是0 =< m <= n.

Answer 2

鉴于"前n个斐波那契数的总和是(n + 2)和斐波纳契数减1." (感谢,维基百科),你可以计算F(m + 2) - F(n + 2)(不应该有-2,见Sнаđошƒаӽ的答案,我忽略了).使用Binet的Fibonacci数公式快速计算F(m + 2)和F(n + 2).对我来说似乎相当有效.

更新:找到一个旧的SO帖子,"次线性时间的第n个斐波纳契数",并且(由于mjv和Jim Lewis在评论中指出的准确性),你无法真正逃脱O(n)计算的解决方案F(n).

Answer 3

F(m+2) - F(n+2) - 2(讨论)

从字面上看,上限m的总和减去下限n的总和.