Thursday, March 21, 2013

Project Euler Problem 2 : Fibonacci

Assalamualaikum. Bismillah.

Someone asked my about Project Euler Problem 2. I can't seems to find it, and while I am going to study Algorithm Design, I might as well review it. The problem is, I think I use brute force to compute this one.

So, this is like, the incomplete answer scheme. -sigh- When will I am able to focus my whole attention to programming so I can actually design algorithm with my own power?

Anyway.

Project Euler 2
Find the sum of all the even-valued term in the Fibonacci sequence which do not exceed four million.

Translated to:

=====================
max = 4000000
sum = 0
a = 1
b = 1
while b < max
   if b mod 2 = 0 then sum = sum + b
   temp = a + b
   a = b
   b = temp
display sum
=====================
As you can see, it is in summary, increment a and b with each other to make Fibonacci seq. It actually start from 0, 1, 1, 2, 3, 5, 8, etc... And, it have condition for even numbers. But, lets see if there is a pattern there.

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

Every third element is even.

So,
=====================
max = 4000000
sum = 0
a = 1
b = 1
c = a + b
while c < max
   sum = sum + c
   a   = b + c
   b   = c + a
   c   = a + b  
display sum
=====================
It actually do the exact same algorithm just like the first one, but, it do the increment 2 times. This is to make the summation is only involving the even numbered Fibonacci series.

So yeah. This is not what I made. :( Just as usual, this is kind of my time capsule for my programming. :) By the way, read this.


.

No comments:

Post a Comment