fib.py
'''\
Fibonacci Algorithms.
fib series: 0 1 1 2 3 5 8...
definition: fib(n) = fib(n-1) + fib(n-2)
exception: fib(0) = 0
exception: fib(1) = 1
January 2014
'''
from __future__ import print_function
from sys import stdout, stderr, argv
from datetime import datetime
def fib1 (n):
'''Fibonacci #1: naive multiple recursion.'''
if n < 2:
return n
return fib1(n-1) + fib1(n-2)
def fib2 (n, lst=None):
'''Fibonacci #2: single recursion.'''
if not lst:
return fib2(n, [0, 1])
if len(lst) < 2:
lst.append(lst[0]+1)
ix = len(lst) - 1
c = lst[ix] + lst[ix-1]
lst.append(c)
if n <= len(lst):
return lst
return fib2(n, lst)
def fib3 (n, lst=[]):
'''Fibonacci #3: single recursion.'''
if len(lst) < 1:
lst.append(0)
if len(lst) < 2:
lst.append(lst[0]+1)
ix = len(lst)
f = lst[ix-1] + lst[ix-2]
lst.append(f)
if len(lst) < n:
fib3(n, lst)
return lst
def do_fib1 (*args):
n = int(args[0]) if 0 < len(args) else 16
print("Fib #1:")
lst = map(fib1, range(n))
print(lst)
return [n, lst]
def do_fib2 (*args):
n = int(args[0]) if 0 < len(args) else 16
print("Fib #2:")
lst = fib2(n)
print(lst)
return [n, lst]
def do_fib3 (*args):
n = int(args[0]) if 0 < len(args) else 16
print("Fib #3:")
lst = fib3(n)
print(lst)
return [n, lst]
def do_main (*args):
print('main/parameters: %d' % len(args))
n = int(args[0]) if 0 < len(args) else 16
print("Fib #1:")
lst1 = map(fib1, range(n))
print(lst1)
print()
print("Fib #2:")
lst2 = fib2(n)
print(lst2)
print()
print("Fib #3:")
lst3 = fib3(n)
print(lst3)
print()
print("Fib #3:")
lst = fib3(n, [2])
print(lst)
print()
print("Fib #3:")
lst = fib3(n, [3])
print(lst)
print()
return [n, lst1, lst2, lst3]
def dispatch (cmd, *args):
print('command: %s' % cmd)
print('arguments: %d' % len(args))
if cmd == 'fib1': return do_fib1(*args)
if cmd == 'fib2': return do_fib2(*args)
if cmd == 'fib3': return do_fib3(*args)
if cmd == 'main': return do_main(*args)
return [None, cmd, args]
if __name__ == '__main__':
print('autorun: %s' % argv[0])
cmd = argv[1] if 1 < len(argv) else ''
etc = argv[2:]
obj = dispatch(cmd, *etc)
print('')
print('exit')
'''eof'''