I have a homework assignment that I'm stumped on. I'm trying to write a program that outputs the fibonacci sequence up the nth number. Here's what I have so far:
def fib():
n = int(input("Please Enter a number: "))
if n == 1:
return(1)
elif n == 0:
return(0)
else:
return (n-1) + (n-2)
mylist = range[0:n]
print(mylist)
I'm thinking I could use separate functions but I can't figure out how to pass the argument that calculates the fibonacci sequence. Then the next step would be to to print out the sequence of numbers up to that number.
Non-recursive solution
def fib(n):
cur = 1
old = 1
i = 1
while (i < n):
cur, old, i = cur+old, cur, i+1
return cur
for i in range(10):
print(fib(i))
Generator solution:
def fib(n):
old = 0
cur = 1
i = 1
yield cur
while (i < n):
cur, old, i = cur+old, cur, i+1
yield cur
for f in fib(10):
print(f)
Note that generator solution outperforms the non-recursive (and non-recursive outperforms recursive, if memoization is not applied to recursive solution)
One more time, recursive with memoization:
def memoize(func):
memo = dict()
def decorated(n):
if n not in memo:
memo[n] = func(n)
return memo[n]
return decorated
@memoize
def fib(n):
#added for demonstration purposes only - not really needed
global call_count
call_count = call_count + 1
#end demonstration purposes
if n<=1:
return 1
else:
return fib(n-1) + fib(n-2)
call_count = 0 #added for demonstration purposes only - not really needed
for i in range(100):
print(fib(i))
print(call_count) #prints 100
This time each fibbonacci number calculated exactly once, and than stored. So, this solution would outperform all the rest. However, the decorator implementation is just quick and dirty, don't let it into production. (see this amazing question on SO for details about python decorators :)
So, having fib
defined, the program would be something like (sorry, just looping is boring, here's some more cool python stuff: list comprehensions)
fib_n = int(input("Fib number?"))
fibs = [fib(i) for i in range(fib_n)]
print " ".join(fibs)
this prints all numbers in ONE line, separated by spaces. If you want each on it's own line - replace " "
with "\n"