5
\$\begingroup\$

This is my implementation of Project Euler #2 in C#. It takes 0 milliseconds to run, and I believe it is correct - I have seen nothing to indicate otherwise!

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

static void GetFibos(ref List<int> nums, int maxVal)
{
    nums.Add(1);
    int lastNum = 2;

    while (lastNum <= maxVal)
    {
        nums.Add(lastNum);
        lastNum = nums[nums.Count - 2] + nums[nums.Count - 1];
    }
}

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    List<int> fiboNums = new List<int>();
    GetFibos(ref fiboNums, 4000000);

    int sumEvenFibos = 0;

    foreach (int i in fiboNums) { if (i % 2 == 0) sumEvenFibos += i; }

    s.Stop();

    Console.WriteLine(sumEvenFibos);
    Console.WriteLine(s.ElapsedMilliseconds);
}

Is there anything I should be doing different?

\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

Why do you need the actual list of Fibonacci numbers? That just requires space, and time.

Believe it or not, you have over-thought this problem. Additionally, your code style is off.

C# Code conventions always use braces for single-statement blocks, and the brace should open at the start of a new line. Code like:

foreach (int i in fiboNums) { if (i % 2 == 0) sumEvenFibos += i; }

should be:

foreach (int i in fiboNums)
{
    if (i % 2 == 0)
    {
        sumEvenFibos += i;
    }
}

As for the list, you don't need it:

int current = 1;
int previous = 0;
int sum = 0;
while (current <= 4000000)
{
    if ((current % 2) == 0)
    {
        sum += current;
    }
    int tmp = current + previous;
    previous = current;
    current = tmp;
}

Now, that whole thing should be put in its own function, and your main method with a parameter for the upper limit (4,000,000) and it becomes:

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumEvenFibos = GetFiboSum(4000000);

    s.Stop();

    Console.WriteLine(sumEvenFibos);
    Console.WriteLine(s.ElapsedMilliseconds);
}
\$\endgroup\$
5
\$\begingroup\$
  1. This:

    List<int> fiboNums = new List<int>();
    GetFibos(ref fiboNums, 4000000);
    

    looks like a C++-ism. In C# you have value types (struct) and reference types (class). List<T> is a class and thus passing it by ref doesn't gain you anything unless you want to replace the list object with a different one. If anything GetFibos should create the list, fill it and then return it.

  2. GetFibos could be better named like GetFibonacciNumbers.

  3. As @rolfl pointed out you don't actually need to store all the numbers - you can just generate them as a sequence with an enumerator and then do your processing on the resulting sequence:

    public IEnumerable<int> GetFibonacciNumbers(int max)
    {
        int current = 1;
        int previous = 0;
        while (current <= max)
        {
            yield return current;
    
            int tmp = current + previous;
            previous = current;
            current = tmp;
        }
    }
    

    Now you can combine this with some LINQ in order to calculate what you want:

    var sumOfAllEven = GetFibonacciNumbers(4000000).Where(n => n % 2 == 0).Sum();
    
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @Hosch250: List<T> is a class and therefor a reference type. Reference types are always passed by reference (as the name indicates). This article might be useful. \$\endgroup\$
    – ChrisWue
    Jan 11, 2015 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.