Fibonacciho čísla

https://en.wikipedia.org/wiki/Fibonacci_number

Výpočet môžeme urobiť priamočiaro pomocou rekurzie.

In [17]:
def fib(i):
    if i <= 1:
        return i
    return fib(i-1)+fib(i-2)

fib(20)
Out[17]:
6765

Zložitosť je exponenciálna, O(2^n), resp. O(fi^n), kde fi je zlaty rez (sqrt(5)+1)/2

V strome volaní sa výpočty opakujú - môžeme si pamätať priebežné medzivýsledky (v pomocnom poli) - MEMOIZÁCIA

In [10]:
n = 50

F = [-1]*(n+1) #vytvorime 41-prkove pole, vyplnime -1 (este nepocitane)
F[0] = 0
F[1] = 1

def fib2(i):
    if F[i] == -1: #ak sme ho este nepocitali
        F[i] = fib2(i-1)+fib2(i-2)
    return F[i] #vratime zapametanu hodnotu

fib2(n)
Out[10]:
12586269025

Dynamické programovanie (zdola nahor) vypočíta (a zapamätá) postupne všetky medzivýsledky od najmensších hodnot

In [14]:
n = 200

F = [-1]*(n+1) #vytvorime 41-prkove pole, vyplnime -1 (este nepocitane)
F[0] = 0
F[1] = 1
for i in range(2, n+1): #od 2 po n
    F[i] = F[i-1]+F[i-2] #predchadzajuce hodnoty uz si vypocitane
print(F[n])

280571172992510140037611932413038677189525

Dá sa vyriešiť aj bez pomocného poľa, teda v konštantnej pamäťovej zložitosti. Stačí si pamätať posledné 2 čísla.

In [16]:
n = 50
a, b = 0, 1 #priradenie dvojice; a = 0 a b = 1
for i in range(n):
    a, b = b, a+b #Python najprv vypocita pravu stranu a potom priradi
print(a)

12586269025
In [ ]: