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

Я столкнулся с этой проблемой здесь, в stackoverflow:

«У меня возникли проблемы с этой проблемой в Project Euler. Вот что задает вопрос: каждый новый член в последовательности Фибоначчи получается добавлением двух предыдущих членов.Начиная с 1 и 2, первые 10 членов будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Найдите сумму все четные члены последовательности, не превышающие четырех миллионов».

Главный ответ был таким (который не компилируется для меня в VS2010... почему?):

    IEnumerable<int> Fibonacci()
    {
        int n1 = 0;
        int n2 = 1;

        yield return 1;
        while (true)
        {
          int n = n1 + n2;
          n1 = n2;
          n2 = n;
          yield return n;
        }
    }

    long result=0;

    foreach (int i in Fibonacci().TakeWhile(i => i<4000000).Where(i % 2 == 0))
    {
        result+=i;
    }
    Console.WriteLine(result);

Я решил попробовать это сам, прежде чем искать ответ, и придумал это (пожалуйста, скажите мне, почему или почему это не является хорошим или плохим способом решения этой проблемы):

Я написал его в классе, потому что в будущем я мог бы добавить к классу гораздо больше, чем просто решение одной задачи Фибоначчи.

class Fibonacci
{
    private int prevNum1 = 1;
    private int prevNum2 = 2;
    private int sum = 0;

    public int GetSum(int min, int max)
    {
        prevNum1 = min;
        prevNum2 = prevNum1 + prevNum1;
        if (prevNum1 % 2 == 0)
        {
            sum += prevNum1;
        }
        if (prevNum2 % 2 == 0)
        {
            sum += prevNum2;
        }
        int fNum = 0;
        while (prevNum2 <= max)
        {
            fNum = prevNum1 + prevNum2;
            if (fNum % 2 == 0)
            {
                //is an even number...add to total
                sum += fNum;
            }
            prevNum1 = prevNum2;
            prevNum2 = fNum;

        }

        return sum;
    }

}

        Fibonacci Fib = new Fibonacci();
        int sum = Fib.GetSum(1, 4000000);

        Console.WriteLine("Sum of all even Fibonacci numbers 1-4,000,000 = {0}", sum);

Опять же, я ищу ответ, почему это хороший или плохой способ решить эту проблему. Также почему первое решение не компилируется. Я начинающий программист и пытаюсь учиться. Спасибо!


.net c# fibonacci
person user1230593    schedule 08.08.2012    source источник
comment
Насколько я могу судить, оба решения одинаково хороши. Тем не менее, лучший ответ - воспользоваться некоторой внутренней магией .Net (оператор yield и операции Linq, которые высоко оптимизированы).   -  person Samy Arous    schedule 08.08.2012

Ответы (2)


arrow_upward
3
arrow_downward

При этом он должен скомпилировать:

foreach (int i in Fibonacci().TakeWhile(i => i < 4000000).Where(i => i % 2 == 0))
{
    result += i;
}

Проблема, из-за которой код не компилировался, заключалась в неправильном лямбда-выражении, а именно:

.Where(i % 2 == 0)

но должно быть

.Where(i => i % 2 == 0)
person horgh    schedule 08.08.2012

arrow_upward
2
arrow_downward

Код не компилируется из-за этой строки:

foreach (int i in Fibonacci().TakeWhile(i => i<4000000).Where(i % 2 == 0))

Прежде всего, .Where() — это метод расширения (погуглите), который можно вызывать для коллекции (например, IEnumerable целых чисел в этом примере). Он возвращает другую коллекцию, содержащую любые элементы, удовлетворяющие некоторому условию.

Обратите внимание, что аргумент .Where() — это выражение, производящее логическое значение, истинное или ложное.

i % 2 == 0

.Where() не принимает логическое значение в качестве аргумента, в этом случае соответствующий аргумент имеет тип

Func<int,bool>

Что в основном означает функцию, которая имеет int в качестве аргумента и возвращает bool. Вы можете определить их довольно просто

// defines a function taking an int, returning true if that int is even
Func<int,bool> foo = i => i % 2 == 0

Таким образом, правильный способ использования .Where() в этом случае будет

foreach (int i in Fibonacci().TakeWhile(i => i<4000000).Where(i => i % 2 == 0))

Итак, вы можете видеть, что .Where() берет функцию, которую мы ей предоставляем, и применяет ее к каждому числу, возвращая набор четных чисел.

С ключевым словом yield происходит и другая магия, не стесняйтесь гуглить это, но это более сложная тема.

person Skepticism    schedule 08.08.2012