# Program to compute the first 100 numbers of the Fibonacci series
# Matt Bishop, ECS 10, Fall 2012
# idea: every time we compute a Fibonacci number fn, we store n and fn
# in a dictionary; n is the key, fn the value
# then, rather than recompute it, we look it up and if not there, compute
# it and put it in the dictionary
#
# here's the dictionary -- empty initially
fibdict = {}
# compute the nth Fibonacci number
# and store it in the dictionary
def fib(n):
global fibdict
#
# look it up first; if already computed, return it
#
if n in fibdict:
return fibdict[n]
#
# nope -- so recompute it
#
# base case: f0 = 0, f1 = 1
if n == 0:
fibdict[0] = 0
return 0
elif n == 1:
fibdict[1] = 1
return 1
# recursive case: fn+2 = fn+1 + fn
# as we computed it, we also store it
fibdict[n] = fib(n-1) + fib(n-2)
return fibdict[n]
#
# the heart of the program
#
def main():
# say how many numbers are to be printed
count = 100
# compute the sequence and print the terms
for i in range(count-2):
# get next Fibonacci number and
# announce it
print("Fibonacci number", i+1, "is", fib(i))
main()