Given:
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.
MAX_LIMIT = 4000000 # Four million inclusive
FIB_CACHE = {}
def fib(n):
""" Calculates nth fibonacci term.
Args:
n: The nth term.
Returns:
The nth fibonacci term of the series.
"""
if (2 >= n):
return n
if (n not in FIB_CACHE):
FIB_CACHE[n] = fib(n-1) + fib(n-2) # linear recurrence
return FIB_CACHE[n]
def sum_fib():
sum = 0
i = 1
ith_fib = 0
while (1):
ith_fib = fib(i)
if (ith_fib > MAX_LIMIT):
return sum
if (ith_fib % 2 == 0):
sum += ith_fib
i += 1
return sum
print fib(1)
print fib(2)
print fib(10)
print sum_fib()
Note: Without caching, it was taking too long to complete since it's an exponential algorithm.
Few important points:
- I read somewhere about putting fewer changing values on the left. Is this true?
- I am always confused about when to use an
if
-if
branch and anif
-else
branch. Is there any heuristic? For example, could I write cache-checking code in theelse
branch too?
if (1 <= n)
, here1
is on left side. \$\endgroup\$(1/Sqrt(5))*(Golden_Ratio^n)
; generating even a long list of Fibs from that is very fast and consequently fast to sum the even fibs directly - no caching. It's in F# but easily adaptable to Python. \$\endgroup\$