4

这是一个 Project Euler 问题。如果您不想看到候选解决方案，请不要看这里。

大家好！我正在开发一个应用程序，它将找到斐波那契数列的所有偶数项的总和。该序列的最后一项是 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();                
        }
    }
}
4

5 回答 5

3

使用这个：http ://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

第三恒等式 这个恒等式对于 Fj 的形式略有不同，这取决于 j 是奇数还是偶数。前 n - 1 个斐波那契数的总和 Fj，使得 j 是奇数，是第 (2n) 个斐波那契数。

前 n 个斐波那契数的总和 Fj，使得 j 是偶数，是第 (2n + 1) 个斐波那契数减 1。

[16]

唯一的问题是当您将 phi 提高到 (2n + 1) 次方时可能会损失精度。

于 2010-04-04T14:37:03.670 回答
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不受约束；_ _ 设置为，因为当时是 2。因此，从循环的第一次迭代开始，将永远是 3。inarr[2]ii

要解决此问题，一种方法是完全摆脱n并使您的循环条件

for (i = 2; arr[i] <= 4000000; i++)
于 2010-04-04T14:08:29.987 回答
1

我承认我会以完全不同的方式做这件事。我可能会使用成对的卢卡斯和斐波那契数列，加上简单的公式

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)

现在只需总结条款。

（编辑：对此有一个更简单的解决方案，它确实依赖于一些数学复杂性来推导，或者一些关于斐波那契数列和该数列恒等式的知识，或者可能是通过整数序列的百科全书进行搜索。可悲的是，没有更多比这个提示似乎不适合 PE 问题，所以我将把这个解决方案留在本笔记的空白处。因此，前 k 个偶数斐波那契数的总和是......）

于 2010-04-08T01:31:40.320 回答
1

for将第一个循环更改为：

for (i = 2; arr[i - 1] < 4000000; i++)
于 2010-04-04T14:43:57.707 回答
1

试试这个（并将其用于您的大整数要求：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
于 2010-04-04T16:06:15.557 回答