9

什么是计算斐波那契数之和的最有效方法，分别F(n)是第n 个和第 m 个斐波那契数，并且 0 =< n <= m <10 9（其中 F(0)=0, F(1)= 1）。F(m)F(n)F(m)

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

n仅通过蛮力，m提到的范围将需要很长时间。如果可以通过矩阵求幂来完成，那怎么做？

4

5 回答 5

22

前两个答案（最旧的）对我来说似乎不正确。根据已在其中一个答案中引用的讨论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]，但我们想要 sum fromF[m]到F[n] inclusive。所以我们从 sum up to 中减去 sum F[m-1]up to 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。

于 2016-12-02T10:35:43.420 回答
13

鉴于“前 n 个斐波那契数的和是 (n + 2)nd 斐波那契数减 1”。（谢谢，维基百科），您可以计算F(m + 2) - F(n + 2)（不应该有-2，请参阅Sнаđошƒаӽ's answer 了解我忽略的内容）。使用比内特的斐波那契数公式快速计算F(m + 2)和F(n + 2)。对我来说似乎相当有效。

更新：找到了一个旧的 SO 帖子，“次线性时间内的第 n 个斐波那契数”，并且（由于mjv和Jim Lewis在评论中指出的准确性），你无法真正逃避O(n)计算的解决方案F(n)。

于 2010-12-05T03:54:17.217 回答
7

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

从字面上看，你的上限 m 的总和减去你的下限 n 的总和。

于 2010-12-05T03:53:13.523 回答
1

通过此处和此处找到的矩阵属性解释的算法

class Program
{
    static int FibMatrix(int n, int i, int h, int j, int k)
    {
        int t = 0;

        while (n > 0)
        {
            if (n % 2 == 1)
            {
                t = j * h;
                j = i * h + j * k + t;
                i = i * k + t;
            }
            t = h * h;
            h = 2 * k * h + t;
            k = k * k + t;
            n = n / 2;
        }

        return j;            
    }

    static int FibSum(int n, int m)
    {
        int sum = Program.FibMatrix(n, 1, 1, 0, 0);

        while (n + 1 <= m)
        {
            sum += Program.FibMatrix(n + 1, 1, 1, 0, 0);
            n++;
        }

        return sum;
    }

    static void Main(string[] args)
    {
        // Output : 4
        Console.WriteLine(Program.FibSum(0, 4).ToString());

        Console.ReadLine();
    }
}
于 2013-08-07T05:47:20.037 回答
1

答案是：

f(m+2)-f(n+1)

例子：

for n = 3 to m = 8

Ans1 = f(m+2) = f(10) = 55

Ans2 = f(n+1) = f(4) = 3 

Answer = 55 - 3 = 52

现在要计算 O(logN) 中的第 N 个斐波那契，您可以使用矩阵求幂法

链接：- http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

于 2017-02-04T14:18:00.513 回答