Сумма четных чисел Фибоначчи

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();                
        }
    }
}

Answer 1

Используйте это: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Третья личность Эта идентичность имеет несколько разные формы для Fj, в зависимости от того, является ли j нечетным или четным. Сумма первых n - 1 чисел Фибоначчи, Fj, таких, что j нечетно, является (2n) -ым числом Фибоначчи.

Сумма первых n чисел Фибоначчи, Fj, таких, что j четное, есть (2n + 1) -ое число Фибоначчи минус 1.

[16]

Единственная проблема - это потенциальная потеря точности, когда вы повышаете фи до (2n + 1) -й степени.

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++)

Answer 3

Я признаю, что сделал бы это совершенно по-другому. Я бы, вероятно, использовал парную последовательность чисел Лукаса и Фибоначчи, плюс простые формулы

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 четных чисел Фибоначчи равна ...)

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

Answer 5

Измените первый цикл for на этот:

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