Commits

Panagiotis Mavrogiorgos committed 4f1fd2b

Added solution to problem 2.

  • Participants
  • Parent commits 1db7ae7

Comments (0)

Files changed (1)

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()
+
+
+
+
+