current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

I'm a fairly new programmer (just started yesterday!). I decided to tackle Project Euler #2 today, as I did #1 yesterday without many problems. I came up with what seems to me to be a working solution, but I feel like I did it in an exceedingly ugly way. Could anyone suggest improvements to my code and/or logic?

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.

fib = 1
fib2 = 2
temp = 0
total = 0

while temp <=4000000:
    temp = fib2
    if temp % 2 == 0:
        total += temp
    temp = fib + fib2
    fib = fib2
    fib2 = temp

print total

I just sort of used my temp variable as a holding ground for the results, and then juggled some variables around to make it do what I wanted... Seems like quite a mess. But it does result in 4613732, which seems to be correct!

share|improve this question

4 Answers 4

up vote 8 down vote

I would use separately Fibonacci generator

def even_fib(4000000):
    a, b = 0, 1
    while a < limit:
        if not a % 2:         
            yield a
        a, b = b, a + b

And sum function to calculate sum of items

print sum(even_fib(4000000))
share|improve this answer
1  
+1. Aside from the use of a generator, this refactor has two improvements that bear mentioning explicitly. The first is tuple assignment to drop temp - another way to achieve the same is: a = a + b; b = a + b, but the tuple assignment logic is much more straightforward. The other one is if not a%2 is, at least arguably, better than comparing against zero. –  lvc Mar 9 '12 at 7:41
up vote 2 down vote

I'm also a fellow newbie but the way I would approach it is to first create a separate function for calculating the value for a given nth term in the Fibonacci sequence. Here's my solution:

def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

total = 0
i = 1
while fibonacci(i) <= 4000000:
    if fibonacci(i) % 2 == 0:
        total += fibonacci(i)
    i += 1
print(total)
share|improve this answer
1  
Very clean solution, but I will point out that the recursive solution becomes exponentially slower as n becomes large. –  RubberDuck Aug 6 '14 at 0:09
    
As @ckuhn203 said, this solution is too slow man, recursion is not a good way to handle this, compared to my solution I'm in the speed of light, haha just kidding... or not... –  matheussilvapb Aug 7 '14 at 19:17
up vote 1 down vote

First of all, I'd like to tell you that the fibonnaci series starts at 1 and the second number is 1, because 1+0=1, so a fibonacci series starts like this: [1, 1, 2, 3, 5, 8...]

I know you can say it's kind of cheatting but anyways: Fibonacci series follows a pattern, because to get an even number out of a sum you'll need 2 even or 2 odd numbers(3+3=6, 6 is even; 3+5=8; 2+8=10). Starting at 1 (odd) it follows this pattern: [odd, odd, even, odd, odd, even...].

Cheating or not this is my solution:

def generate_fib(max_value):
    series = [1, 1]
    while True:
        next_last = series[-1] + series[-2]
        if next_last > max_value:
            break
        series.append(next_last)
    return series

series = generate_fib(4000000)
evens = [series[x] for x in range(2, len(series), 3)]
print(sum(evens))
share|improve this answer
    
If you solve it and look at the corresponding solution pdf (note the checkmark, pdf, and person icons to the right of the Solved By column) you will see an even more optimized solution that isn't 'cheating' but rather recommended. –  MichaelT Apr 21 '14 at 18:26
    
Saying that the Fibonacci sequence starts at zero does not break the algorithm. It's completely reasonable to believe that it does start at zero. –  RubberDuck Aug 6 '14 at 1:18
    
@ckuhn203 actually it can't start at zero because the next number is defined by the sum of the two preceding numbers, so if you start at zero you'll have [0] the second number will be the first number plus zero because you still don't have 2 numbers, and it'll become [0, 0], then the third will be 0, the forth, the fifth all of them will be equal to zero... that's why you can't start the fibonacci series at zero. –  matheussilvapb Aug 7 '14 at 18:59
1  
Some say that the Fibonacci Sequence is 0, 1, 1, 2, …; other say it is 1, 1, 2, …. Either way, it makes no difference if you just want to find the sum of the even entries. –  200_success♦ Aug 7 '14 at 19:20
1  
It takes two fixed consecutive entries to uniquely define a Fibonacci-type sequence. The zero-based definition just says that it starts with 0, 1, …. A silly definition of 0, 0, … would, of course, result in all zeroes. –  200_success♦ Aug 7 '14 at 19:30
up vote -2 down vote

The only suggestion I would add is the way you are dealing with the recursion. It doesn't save on run-time, but it will clean up the code and eliminate the need for the temp variable.

fib1 = 1
fib2 = 2
total = 0

while fib2 <= 4*10**6:
    if fib2 % 2 == 0:
        total += fib2
    fib1, fib2 = fib2, fib1 + fib2

print total
share|improve this answer
5  
Recursion? Neither the OP nor your answer uses any recursion. –  lvc Mar 9 '12 at 7:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.