Project Euler: Task 2

Hola!

Second Project Euler task coming up! After the first walkthrough, I’m looking to lay this one out exactly the same. Remember, as always, try and give it a shot yourself. If you get nowhere or need that extra hand, then have a look here for some inspiration. You get nothing from photocpying a crossword puzzle… Apart from a photocpied crossword puzzle.

Task Analysis

The task I will be completing will be in somewhat relation to the Fibonacci series and their numbers. But direct from the project Euler site:

“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.”

Following my 4 P’s strategy, I’m going to involve myself in some more planning and preperation for this one. Although I think it is pretty straight forward myself, it’s always better to be safe than sorry, as though no planning means no plan.

Design

The Maths

First of all, Im going to start off with explaining the formula for the fibonacci sequence, and if you are any good at maths, *Says with enthusiasm* try to contain your excitement:

Fibonacci

Where:
F<n> = The new Fibonacci Number.
F<n-1> = The last Fibonacci Number so far in the series.
F<n-2> = The second last Fibonacci Number so far in the series.

Other Factors

Other Factors which I may need to consider are such things like the one minute rule and the fact that this program needs to be going up to 4 Million numbers. As though it increases in a sort of Geometric Progression type of way, it should reach 4 Million in at around 500 numbers into the sequence? (Hopefully!)

For the one minute rule to be fulfilled, I’m going to invest some time in a good algorithm to follow. So, lets get to business with some Pseudo Code!

Pseudo Code

INT sum = 0, num1 = 1, num2 = 1, num3
WHILE num3 < 4,000,000 THEN
	num3 = num1 + num2
	num1 = num2
	num2 = num3
	IF (num3 % 2 = 0) THEN
		sum += num3
	ELSE
		Continue
END WHILE
PRINT sum

This pseudo code is pretty straight forward and it clearly highlights what I want to achieve. It shouldn’t really need explaining, but as a quick walkthrough of the pseudo code, here is what happens:

  1. The initial Variables that I will need are declared and/or initialised.
  2. A while loop is created, for when ‘num3’ is less than 4 Million.
  3. Number 3 then equals the sum of number 2 and number 1
  4. Number 1 becomes number 2
  5. Number 2 become number 3
  6. An if statement then does the modulus operation of the variable ‘num3’ with the number 2. Therefore meaning that if it is an even number, the result will be an output of 0. Thus, if this is the case, then the value ‘sum’ will be increased by the number just validated.
  7. If it is odd, it will continue running, and for both cases it will loop. That is unless the next number is greater than 4 million, and then the program will display the sum and wait out for user input.

Note: I have changed the first two numbers in the series to both 1 however, which reduces the need for me to manually add 2 to the final answer, however the same series will be run and executed, it won’t matter.

Development

Same as last time, I’m writing in visual studio with C#, however if you want to challenge yourself, give a try of another programming language this time.

Tip: Not getting the right answer? Remember to look through your program for logic errors; if pseudo code isn’t helping, write a flow chart!

The Code Itself

Project Euler 2

  1. The initial Variables that I will need are declared and/or initialised.
  2. A while loop is created, for when ‘num3’ is less than 4 Million.
  3. Number 3 then equals the sum of number 2 and number 1
  4. Number 1 becomes number 2
  5. Number 2 become number 3
  6. An if statement then does the modulus operation of the variable ‘num3’ with the number 2. Therefore meaning that if it is an even number, the result will be an output of 0. Thus, if this is the case, then the value ‘sum’ will be increased by the number just validated.
  7. If it is odd, it will continue running, and for both cases it will loop. That is unless the next number is greater than 4 million, and then the program will display the sum and wait out for user input.

Now… Did you notice something?
Everything I wrote there for the code itself was exactly the same which I had wrote for the pseudo code…. I surprised myself with that! I thought I would have had to re-write another explanation! That just clearly demonstrates how a good use of pseudo code, or a flow chart can really assist you with your programming practices. See, I’m not just drivelling on about how essential it is to plan your code!

Answer = 4,613,732

Evaluation

Overall, That was pretty straight forward with the thought process behind it, and that pseudo code helped a lot… it just shows why it is important and imperative to have good planning skills as a programmer.

Furthermore, the answer was generated in under 3 seconds… And I don’t know about you, but it just beats my personal record of 3.67 seconds without a computer…

Task 3 will be coming shortly, share this with your friends if you found this useful!

Got a burning question? Ask it!

Done it differently? Show it!

Be back later,

Alpha. 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s