import time
def FibIter(n):
    '''Iterativna različica Fibonaccijja'''
    nti, nasl = 1,1
    for _ in range(n):
        nti, nasl = nasl, nti + nasl
    return nti

def FibMem(n):
    ''' s pomočjo globalnega slovarja glCache'''
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n in glCache:
        return glCache[n]
    # ni ga v slovarju
    rez = FibMem(n-2) + FibMem(n-1)
    glCache[n] = rez # si ga zapomnimo
    return rez

def FibMem_2(n):
    '''ne pacamo okoli s slovarji'''
    def FibMemLok(n): # lokalna funkcija
        ''' s pomočjo slovarja glCache iz "nosilne funkcije"'''
        if n == 0 or n == 1:
            return 1
        if n in glCache:
            return glCache[n]
        # ni ga v slovarju
        rez = FibMemLok(n-2) + FibMemLok(n-1)
        glCache[n] = rez # si ga zapomnimo
        return rez
    # gl. fun
    glCache = dict() # nastavimo slovar
    return FibMemLok(n) # izvedemo lokalno funkcijo

n = int(input('Fibonacci: '))
koliko = 100000
# merimo čas
zacIter = time.process_time()
for i in range(koliko):
    rezIter = FibIter(n)
konIter = time.process_time()
print('  iteracija - izvedemo ' + str(koliko) + ' ponovitev:\t\t\t\t\t\t\t      ', rezIter, 2*'\t', (konIter - zacIter))

zacMem = time.process_time()
glCache = dict()  # tukaj!
for i in range(koliko):
    rezMem = FibMem(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev, a "goljufamo":\t\t\t\t ', rezMem, 2*'\t', (konMem - zacMem))

zacMem = time.process_time()
for i in range(koliko):
    glCache = dict()  # tukaj!
    rezMem = FibMem(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev in "pošteno":\t\t\t\t   ', rezMem, 2*'\t', (konMem - zacMem))

zacMem = time.process_time()
for i in range(koliko):
    rezMem = FibMem_2(n)
konMem = time.process_time()
print('memoizacija - izvedemo ' + str(koliko) + ' ponovitev in "brez packanja":\t', rezMem, 2*'\t', (konMem - zacMem))