# Commits

committed 4f1fd2b

Added solution to problem 2.

• Participants
• Parent commits 1db7ae7

# File problem_2.py

`+#!/usr/bin/env python`
`+# -*- coding: utf-8 -*-`
`+"""`
`+Created on Sun Mar 27 20:34:29 2011`
`+`
`+@author: pmav99`
`+`
`+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.`
`+`
`+Additional resources`
`+http://en.literateprograms.org/Fibonacci_numbers_(Python)`
`+"""`
`+`
`+from __future__ import division`
`+import timeit`
`+import sys`
`+`
`+sys.setrecursionlimit(20000)`
`+`
`+# simple recursion - very slow.`
`+def fib_rec(n):`
`+    if n < 2:`
`+        return n`
`+    else:`
`+        return fib_rec(n-1) + fib_rec(n-2)`
`+`
`+def recursive_dictionary(limit):`
`+    """`
`+    Creates a dictionary containing the elements of the fibonacci sequence`
`+    with values lower than limit`
`+    """`
`+`
`+    def fib(n):`
`+        """`
`+        Returns the n-th item of the fibonacci sequence.`
`+        "memo" is a dictionary containing the previously calculated elements.`
`+        """`
`+        if n not in memo:`
`+            memo[n] = fib(n-1) + fib(n-2)`
`+        return memo[n]`
`+`
`+    memo = {0:0, 1:1}`
`+    n = 2`
`+    temp = 0`
`+    while temp < limit:`
`+        temp = fib(n)`
`+        n += 1`
`+`
`+    # Find the total`
`+    tot = 0`
`+    for value in memo.values():`
`+        if value % 2 == 0:`
`+            tot += value`
`+    return tot`
`+`
`+def iterator(limit):`
`+    """`
`+    Creates a list containing the elements of the fibonacci sequence`
`+    with values lower than limit`
`+    """`
`+    def fib(n):`
`+        a, b = 0, 1`
`+        for i in range(n):`
`+            a, b = b, a + b`
`+        return a`
`+`
`+    n = 0`
`+    lst = []`
`+    temp = 0`
`+    while temp <= limit:`
`+        temp = fib(n)`
`+        lst.append(temp)`
`+        n += 1`
`+`
`+    # Find the total`
`+    tot = 0`
`+    for item in lst:`
`+        if item % 2 == 0:`
`+            tot += item`
`+    return(tot)`
`+`
`+def generator_set(limit):`
`+    def fib():`
`+        a, b = 0, 1`
`+        while True:`
`+            yield a`
`+            a, b = b, a + b`
`+`
`+    gen = fib()`
`+    temp = gen.next()`
`+    s = set()`
`+    while temp < limit:`
`+        s.add(temp)`
`+        temp = gen.next()`
`+`
`+    # Find the total`
`+    tot = 0`
`+    for item in s:`
`+        if item % 2 == 0:`
`+            tot += item`
`+    return(tot)`
`+`
`+def generator_list(limit):`
`+    def fib():`
`+        a, b = 0, 1`
`+        while True:`
`+            yield a`
`+            a, b = b, a + b`
`+`
`+    gen = fib()`
`+    lst = [gen.next()]`
`+    while lst[-1] < limit:`
`+        lst.append(gen.next())`
`+    lst.pop()`
`+`
`+    # Find the total`
`+    tot = 0`
`+    for item in lst:`
`+        if item % 2 == 0:`
`+            tot += item`
`+    return(tot)`
`+`
`+def generator_dictionary(limit):`
`+    def fib():`
`+        a, b = 0, 1`
`+        while True:`
`+            yield a`
`+            a, b = b, a + b`
`+`
`+    gen = fib()`
`+    temp = gen.next()`
`+    memo = {}`
`+    n = 0`
`+    while temp < limit:`
`+        memo[n] = temp`
`+        n += 1`
`+        temp = gen.next()`
`+`
`+    # Find the total`
`+    tot = 0`
`+    for value in memo.values():`
`+        if value % 2 == 0:`
`+            tot += value`
`+    return tot`
`+`
`+def main():`
`+    limit = 4000000`
`+    times = 1000`
`+`
`+    functions = (recursive_dictionary, iterator,`
`+                 generator_set, generator_list, generator_dictionary)`
`+`
`+    # Check that the result is correct`
`+    for function in functions:`
`+        print(function(limit))`
`+`
`+    # time the functions`
`+    print(50 * "-")`
`+    print(sys.version)`
`+    print(50 * "-")`
`+    for function in functions:`
`+        t = timeit.Timer("{0}({1})".format(function.__name__, str(limit)),`
`+                         "from __main__ import {0}".format(function.__name__))`
`+        print("{0:30} => {1}".format(function.__name__, t.timeit(times)))`
`+    print(50 * "-")`
`+`
`+if __name__ == "__main__":`
`+    main()`
`+`
`+`
`+`
`+`
`+`