Friday, September 18, 2009

Project Euler Problem 2 (Python)

Alright, for this problem let's switch things up a bit and go with some Python code. I'm currently working with Python on some projects for college, so I decided to go ahead and solve some of these problems in Python rather than continue on in Java.
Also, I'm going to try and make the posts much shorter and to the point. I'm assuming anyone that reads these has at least a basic programming knowledge. (loops, if-statements, variables, functions, classes, etc.) Anything complex will still be explained, but I'd like to simply describe the problem and the steps to solving it. Typing up long explanations of basic programming constructs is time consuming and also probably not helpful. There are plenty of beginner programming tutorials out there, and if problems arise, then questions can be asked in the comments section.
Ok, enough talk, let's see what the second problem has in store for us.

Problem 2:

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.


--

To solve this problem we know we need a few things:

* We have to be able to calculate the numbers in the Fibonacci sequence.
* We need to be able to loop through the numbers in the sequence and add each number to a running total.
* We need a way to determine if a number in the sequence is even, and if so add it to the sum.
* We need to check when the number in the sequence is greater than 4,000,000 and then stop looping.

Fortunately, all 4 of these things can be done with basic programming constructs. The numbers in the Fibonacci sequence can be generated very easily by following the description given in the problem. A simple while loop can be used to loop through the numbers, and each time we can add to a variable that holds the sum. Determining if a number is odd or even can be done by taking the modulus of the number and seeing if it is 0. If it is, then we know that the number is even and add it to the sum. We make our condition for the while loop break out of the loop if the number exceeds 4,000,000.
That's all we need to solve this problem. Assemble these components correctly and we should get a program that gives us the correct answer.

Here's what I ended up with:


Thanks for reading!
-Michael

Update: After reading through some discussion of this problem, I've realized that there is definitely a better way to solve this problem that would remove the need for the use of the modulus operator to check if a number is even. By writing out some of the Fibonacci sequence, it becomes apparent that every third number is even. This makes sense, and is fairly easy to prove mathematically. Anyway, that being said, we could simply have looped through and added up every third number rather than using an if-statement to check for an even number. I'm not going to post new code, but I thought I would mention this optimization.

No comments:

Post a Comment