## fibonacci.py
## Berechnung der Fibonacci-Folge
## Wolfgang.Urban@schule.at

# fuer den Generator in Algorihmus 5
from __future__ import generators   

## Algorithmus 1

def fibo1(n):
    if n <= 2:
        return 1
    else:
        return fibo1(n-1)+fibo1(n-2)

## Algorithmus 1a

def fibo1a(n):
    if n <= 2:
        return 1
    return fibo1a(n-1)+fibo1a(n-2)

## Algorithmus 2

fiboliste = {}

def fibo2(n):
    global fiboliste
    if fiboliste.has_key(n):
        return fiboliste[n]
    if n <= 2:
        return 1
    ergebnis = fiboliste[n] = fibo2(n-1)+fibo2(n-2)
    return ergebnis

## Algorithmus 2a

fiboliste2a = {1:1, 2:1}

def fibo2a(n):
    global fiboliste2a
    if fiboliste2a.has_key(n):
        return fiboliste2a[n]
    ergebnis = fiboliste2a[n] = fibo2a(n-1)+fibo2a(n-2)
    return ergebnis

## Algorithmus 3

def fibo3(n):
    if n <= 2:
        return 1
    a,b = 1,1
    for zaehler in range(3,n+1):
        a,b = b,a+b
    return b

## Algorithmus 3a

def fibo3a(n):
    a,b = 0,1
    for zaehler in range(n):
        a,b = b,a+b
    return a

## Algorithmus 4

def fibo4(n,a=1,b=1):
    if n == 1: return a
    if n == 2: return b
    return fibo4(n-1,b,a+b)

####################################################
## SPEZIALITAET:
## Fibonacci-Zahlen mit Memoizing-Klasse
## klappt fuer beliebige Funktionen mit bel. vielen
## Eingabeparametern!
## Hier die Klassendefinition (mehr ist nicht noetig!):

class Memoize:
    def __init__(self,funktion):
        self.fn = funktion
        self.memo = {}
    def __call__(self,*value):
        if value not in self.memo.keys():
            self.memo[value] = self.fn(*value)
        return self.memo[value]

####################################################

## Algorithmus 5 basierend auf Alg. 3

def fib5():
    a = 1 ; yield a
    b = 1 ; yield b
    while 1:
       a,b = b,a+b
       yield b

## Algorithmus 5 basierend auf Alg. 3a

def fib5a():
    a,b = 0,1
    while 1:
       a,b = b,a+b
       yield a

#  oder umgekehrt b auswerfen
       
def fib5b():
    a,b = 0,1
    while 1:
        yield b
        a,b = b,a+b

###############################################
## Tests                                     ##
###############################################

# Alg. 1
print "Alg. 1",fibo1(10)

# Alg. 4
print "Alg. 4",fibo4(10,1,1)

# Algorithmus 1, Memoized    
fib_m = Memoize(fibo1)
print "Memoized:",fib_m(10)

# Generator
fib_g = fib5a()
print "Generator: ",
for i in range(10):
    print fib_g.next(),
print