ARE YOU A MATH FREAK!!!!!!!

Wednesday, December 2, 2009

Problem 2: Sum of even fibonacci numbers

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


Sol:
This problem too is a trivial one if the brute force approach is followed. But on observing the fibonacci series, it is observed that there is an even number every three steps....
1 1 2 3 5 8 13 21 34 55 89 144 .......
So, instead of checking for divisibility by 2 each time an element is calculated, every third fibonacci number can be added upto 4 million to find the result.

The code to solve the problem can then be :

   i=1,j=2,d=0,x=0;
   long s=0;
   while(j<4000000)
   {
            s=s+j;
            while(d<=2)
            {
                       x=i+j;
                       i=j;
                       j=x;
                       d++;
            }
            d=0;           
   }
   cout << s
}

As explained, the code calculates three elements in each loop and adds the third number to the sum.

Please post your comments...
Better algorithms are always welcome..

No comments:

Post a Comment