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\$
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
    \$\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 '15 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.