偶斐波那契数列之和

Question

这是一个项目欧拉问题。如果你不想看到候选解决方案，请不要在这里查看。

大家好！我正在开发一个应用程序，将找到斐波那契数列的所有偶数项的总和。该序列的最后一项为4,000,000。我的代码有些问题，但我无法找到问题，因为它对我来说是有意义的。你能帮帮我吗？

using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
           long[] arr = new long [1000000] ;
           long i= 2;
           arr[i-2]=1;
           arr[i-1]=2;
           long n= arr[i];

           long s=0;
            for (i=2 ; n <= 4000000; i++)
            {                    
                arr[i] = arr[(i - 1)] + arr[(i - 2)];
            }
            for (long f = 0; f <= arr.Length - 1; f++)
            {
                if (arr[f] % 2 == 0)
                    s += arr[f];
            }
            Console.Write(s);
            Console.Read();                
        }
    }
}

- user300484

---

我敢打赌计算那些东西肯定有捷径。http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression 在尝试计算之前，始终尝试简化公式。 - Hamish Grubijan

http://projecteuler.net/index.php?section=problems&id=2 - Inisheer

我认为不需要存储先前生成的序列项，只需计算下一个项，检查其是否为偶数，并有条件地将其相加。 - President James K. Polk

Answer 1

请使用以下链接：http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression 第三个公式： 当j是奇数时，前n−1个斐波那契数Fj的和是第(2n)个斐波那契数。 当j是偶数时，前n个斐波那契数Fj的和是第(2n+1)个斐波那契数减1。

[16]

唯一的问题是将黄金比率phi提高至(2n+1)次方可能会导致精度损失。

- Hamish Grubijan

---

如果他们无法使用递归或生成函数自行证明，那么提供一个封闭形式毫无意义。 - Wes

Answer 2

在本节中：

       long n= arr[i];

       long s=0;
        for (i=2 ; n <= 4000000; i++)
        {

            arr[i] = arr[(i - 1)] + arr[(i - 2)];
        }

您只对n进行了一次赋值，n从未更新，因此您的循环永远不会终止。 n未与i绑定；将n设置为arr[2]是因为此时i为2。因此，i将永远从循环的第一个迭代开始为3。

修复此问题的一种方法是完全摆脱n并使您的循环条件为：

for (i = 2; arr[i] <= 4000000; i++)

- Mark Rushakoff

---

我已经尝试了你的修复方法，但它没有起作用。VS显示索引超出范围。 - user300484

在IndexOutOfRangeException发生之前，变量i和数组arr[i]的值是什么？ - Mark Rushakoff

Answer 3

将第一个 for 循环改为以下内容：

for (i = 2; arr[i - 1] < 4000000; i++)

- user153498

Answer 4

试试这个（并将其用于您的大整数需求：http://intx.codeplex.com/Wikipage）：

using System;
using System.Collections;
using System.Linq;
using System.Collections.Generic;

using Oyster.Math;

namespace Application
{


public class Test
{

    public static void Main()
    {    
        IntX even = 0;
        Console.WriteLine("Sum of even fibonacci {0}\n", 
            Fibonacci(20).Where(x => x % 2 == 0).Sum());
        Console.WriteLine("Sum of odd fibonacci {0}", 
            Fibonacci(20).Where(x => x % 2 == 1).Sum());

        Console.Write("\nFibonacci samples");
        foreach (IntX i in Fibonacci(20))
            Console.Write(" {0}", i);

        Console.ReadLine();

    }

    public static IEnumerable<IntX> Fibonacci(int range)
    {
        int i = 0;

        IntX very = 0;       
        yield return very;
        ++i;

        IntX old = 1;       
        yield return old;
        ++i;

        IntX fib = 0; 
        while (i < range)
        {
            fib = very + old;
            yield return fib;
            ++i;

            very = old;
            old = fib;                
        }

    }
}


public static class Helper
{
    public static IntX Sum(this IEnumerable<IntX> v)
    {
        int s = 0;
        foreach (int i in v) s += i;
        return s;
    }
}

}

样例输出：

Sum of even fibonacci 3382

Sum of odd fibonacci 7563

Fibonacci samples 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

- Michael Buen

---

你好，我发现Michael的这段代码非常有帮助，但是由于我刚接触C#，有些部分我还不太理解... 为什么我们要在这一行中将参数值设为20呢？Fibonacci(20).Where(x => x % 2 == 0).Sum()); - user629917

只需取一个偶数的斐波那契数，再往上两个斐波那契数。从该数字中减去1并除以2，即可得到从起始位置开始的所有偶数斐波那契数之和。例如，34，再往上两个是89。减去1等于88。除以2得到44。这就是2+8+34的总和。 - Stefan Gruenwald

Answer 5

我承认我会完全不同的方法。我可能会使用Lucas和Fibonacci数列的配对序列，加上简单的公式

F(n+a) = (F(a)*L(n) + L(a)*F(n))/2

L(n+a) = (5*F(a)*F(n) + L(a)*L(n))/2

请注意，只有每三个斐波那契数是偶数。因此，由于F(3) = 2，而L(3) = 4，我们得到

F(n+3) = L(n) + 2*F(n)

L(n+3) = 5*F(n) + 2*L(n)

现在只需将这些项相加即可。

（编辑：有一个更简单的解决方案，需要一些数学技巧来推导，或者对Fibonacci序列和该序列的恒等式有一些了解，或者通过整数序列百科全书进行搜索。遗憾的是，任何超过这个提示的内容都似乎不适合PE问题，所以我将把这个解决方案留在这个注释的边缘。因此，前k个偶数斐波那契数的总和是...）

- user85109