Edit (18/01/2013)
I have edited this post on the above date. However, the only change that I have made is that I am now hosting the source code (found at the end of this post) on GitHub. This means, that if I need to make a change to the code, I do not have to edit this post again – as it will pull the latest version of it from the relevant page on GitHub whenever it is accessed by a reader.
Firstly
This is a solution to problem 2 on Project Euler. I’ve not posted it up here to gloat, or to provide answers for cheats. I’ve posted it, so that you can see how I solve this kind of problem.
The original problem reads like this:
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.
The Algorithm
The first step I took was to calculate the Fibonacci sequence up to the limit of 4 million. That told me that the 33rd term was my stopping point (since the 33rd term gave the answer 3,524,578 and the 34th term gave the answer 5,702,887). The next step is to sum all of the even numbers between 0 and 33.
At it’s heart, this program is adding even numbers between 0 and 33. But instead of just adding the even numbers (2, 4, 6,… 32) together, I actually had the code calculate the Fibonacci sequence as well as a way of double checking my initial calculation.
This is good coding practise. Heck, it’s good maths practise. You should always check your answer. The last thing you’d want is to be sure that an answer is correct (especially something this large) with out checking it. Because, the chances are, you’ll have the wrong answer.
The Code
I’m not going to spend time explaining the code, since it should be straight forward for anyone with a little experience in the C family.
Psst. It’s written in C++
I’m also not going to explain how we calculate the Fibonacci sequence, since it’s not either terribly exciting, or even that hard to figure out from reading the code.
So, without further ado, here is the finished code:
It’s simple little puzzles like the above that improve your coding skills. Even if you start from a blank canvas.
Until next time,
J
