Curso Python 300 - Aula 28

fib_pd.py

'''
Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
F(1) = F(2) = 1
F(n) = F(n - 1) + F(n - 2)
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
'''

MAX_N = 100
valores = [0] * MAX_N
valores[0] = valores[1] = 1

# recursivo lento - complexidade exponencial - O(2^n)
def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)


# iterativo - complexidade linear - O(n)
def fib_rapido(n):
    if n > MAX_N:
        print('Valor maximo de n tem que ser 100!')
    else:
        if valores[n - 1] != 0:
            print('Fib de %d, valor jรก calculado...' % n)
            return valores[n - 1]
        else:
            print('Calculando o fib de %d...' % n)
            for i in range(2, n):
              valores[i] = valores[i - 1] + valores[i - 2]
            return valores[n - 1]

#print('Calculando o fib de forma lenta...')
#print(fib(n))
#print('Calculando o fib de forma rapida...')
print(fib_rapido(20))
print(fib_rapido(10))
print(fib_rapido(50))
print(fib_rapido(45))
print(fib_rapido(30))