Sunday, August 7, 2011

Project Euler Problem #2

So these Project Euler problems have become quite addictive. I've actually already completed quite a few of them. However, this post will be devoted to problem number dos.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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

So this problem is asking us to find all the terms in the Fibonacci sequence that are even and under 4,000,000. Then we have to sum all of those terms.

Alright, first we have to figure out the best way to generate our terms to use. The idea of the sequence is pretty straightforward. We start with two terms, 0 and 1, and then we can use an iterator block to return the second term to an enumerable object. Finally, we can set the second term to itself plus the first and set the first term equal to the new second minus the first.....confusing enough? Yea. Maybe this will help.

 public IEnumerable<long> Fibonacci()
  long a = 0;
  long b = 1;

  yield return b;

  b = a + b;
  a = b - a;

So now we have a Fibonacci generator!

So our final answer can be achieved by using a lambda expression with a 'TakeWhile' extension.

 Tools newTools = new Tools();
 return newTools.Fibonacci().TakeWhile(i => i > 4000000).Where(i => newTools.IsEven(i)).Sum();

I have placed my Fibonacci Generator and the IsEven function in a "Tools" class. This will be my common assembly that will be used in each problems class. I've implemented Dependency Injection on my solution just for the fun of it and will probably go over it in another post sometime. Who knows.

Anyways, for good measure, here is my IsEven function:

 public bool IsEven(long number)
  return (number % 2 == 0);

No comments:

Post a Comment