def fib_rek(n):
global pocet
pocet += 1
if n < 2:
return n
return fib_rek(n-1)+fib_rek(n-2)
for hodnota in range(11):
pocet = 0
fb = fib_rek(hodnota)
print(f'{hodnota:02d}: {fb} {pocet}')
00: 0 1 01: 1 1 02: 1 3 03: 2 5 04: 3 9 05: 5 15 06: 8 25 07: 13 41 08: 21 67 09: 34 109 10: 55 177
def fib_mem(n):
global pocet
pocet += 1
if MEM[n] is None:
MEM[n] = fib_mem(n-1)+fib_mem(n-2)
return MEM[n]
for hodnota in range(11):
pocet = 0
MEM = [None]*12
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
print(f'{hodnota:02d}: {fb} {pocet}')
00: 0 1 01: 1 1 02: 1 3 03: 2 5 04: 3 7 05: 5 9 06: 8 11 07: 13 13 08: 21 15 09: 34 17 10: 55 19
# obe moznosti + rozdiel
n = 20
for hodnota in range(n+1):
pocet = 0
fb = fib_rek(hodnota)
print(f'{hodnota:02d}: {fb} {pocet}', end=" ... ")
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
print(f'{fb} {pocet}, teda rozdiel je {pocet_rek-pocet}')
00: 0 1 ... 0 1, teda rozdiel je 0 01: 1 1 ... 1 1, teda rozdiel je 0 02: 1 3 ... 1 3, teda rozdiel je 0 03: 2 5 ... 2 5, teda rozdiel je 0 04: 3 9 ... 3 7, teda rozdiel je 2 05: 5 15 ... 5 9, teda rozdiel je 6 06: 8 25 ... 8 11, teda rozdiel je 14 07: 13 41 ... 13 13, teda rozdiel je 28 08: 21 67 ... 21 15, teda rozdiel je 52 09: 34 109 ... 34 17, teda rozdiel je 92 10: 55 177 ... 55 19, teda rozdiel je 158 11: 89 287 ... 89 21, teda rozdiel je 266 12: 144 465 ... 144 23, teda rozdiel je 442 13: 233 753 ... 233 25, teda rozdiel je 728 14: 377 1219 ... 377 27, teda rozdiel je 1192 15: 610 1973 ... 610 29, teda rozdiel je 1944 16: 987 3193 ... 987 31, teda rozdiel je 3162 17: 1597 5167 ... 1597 33, teda rozdiel je 5134 18: 2584 8361 ... 2584 35, teda rozdiel je 8326 19: 4181 13529 ... 4181 37, teda rozdiel je 13492 20: 6765 21891 ... 6765 39, teda rozdiel je 21852
for _ in range(int(input())): #dany pocet testovacich sad/cisel
hodnota = int(input()) #nacitame cislo
#vypocitame rozdiel
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
print(f'{pocet_rek-pocet}')
3 1 0 5 6 10 158
%%time
for hodnota in [20]*20: #dany pocet testovacich sad/cisel
#vypocitame rozdiel
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
print(f'{pocet_rek-pocet}')
21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 Wall time: 73 ms
1000/20*0.073 #cas v sekundach pre vstup 1000*20
3.65
%%time
for hodnota in [20]*1000: #dany pocet testovacich sad/cisel
#vypocitame rozdiel
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
print(f'{pocet_rek-pocet}')
21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 21852 Wall time: 3.53 s
efektívnejšie:
def rozdiel(hodnota):
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
return pocet_rek-pocet
rozdiel(10)
158
MEM_ROZDIEL = [None]*21 # Memoizacia rozdielu
def rozdiel(hodnota):
if MEM_ROZDIEL[hodnota] is None:
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
MEM_ROZDIEL[hodnota] = pocet_rek-pocet
return MEM_ROZDIEL[hodnota]
%time rozdiel(20)
Wall time: 4 ms
21852
%time rozdiel(20)
Wall time: 0 ns
21852
%time rozdiel(19)
Wall time: 2.03 ms
13492
%time rozdiel(19)
Wall time: 0 ns
13492
%%time
MEM_ROZDIEL = [None]*21 # Memoizacia rozdielu
def rozdiel(hodnota):
if MEM_ROZDIEL[hodnota] is None:
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
MEM_ROZDIEL[hodnota] = pocet_rek-pocet
return MEM_ROZDIEL[hodnota]
for _ in range(1000):
rozdiel(20)
Wall time: 4 ms
from functools import cache, lru_cache #memoizacia priamo Pythonom
%%time
@cache #@lru_cache(size=None) #dekorator
def rozdiel_cache(hodnota):
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
return pocet_rek-pocet
for _ in range(1000):
rozdiel_cache(20)
Wall time: 4 ms
%%time
def rozdiel_(hodnota):
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
return pocet_rek-pocet
rozdiel_cache = cache(rozdiel_) #vytvori memoizaciu s funkcie
for _ in range(1000):
rozdiel_cache(20)
Wall time: 3.98 ms
cache
vytvorí slovník (asociatívne pole/mapa), kde ukladá už vzpočítané hodnoty podľa parametrov funkcie
%%time
MEM_ROZDIEL = {} # Memoizacia rozdielu
def rozdiel(hodnota):
if not hodnota in MEM_ROZDIEL: #ak este v zozname nie je
global pocet
global MEM
pocet = 0
fb = fib_rek(hodnota)
pocet_rek = pocet
pocet = 0
MEM = [None]*(n+1)
MEM[:1] = 0, 1
fb = fib_mem(hodnota)
MEM_ROZDIEL[hodnota] = pocet_rek-pocet
return MEM_ROZDIEL[hodnota]
for _ in range(1000):
rozdiel(20)
Wall time: 5 ms
MEM_ROZDIEL
{20: 21852}
rozdiel(18)
8326
MEM_ROZDIEL
{20: 21852, 18: 8326}
n = 10
DP = [None]*(n+1)
DP[:2] = 0, 1
for i in range(2, n+1):
DP[i] = DP[i-1]+DP[i-2]
DP
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
DP[n]
55
n = 10
DP_VOLANI_REKURZIOU = [None]*(n+1)
DP_VOLANI_REKURZIOU[:2] = [1]*2
for i in range(2, n+1):
DP_VOLANI_REKURZIOU[i] = DP_VOLANI_REKURZIOU[i-1]+DP_VOLANI_REKURZIOU[i-2]+1
print(*DP_VOLANI_REKURZIOU)
1 1 3 5 9 15 25 41 67 109 177
nepotrebujeme si pamätať celé pole, stačí len posledné dve hodnoty
n = 10
a, b = 0, 1
for _ in range(n-1):
a, b = b, a+b
print(b)
55
n = 10
a, b = 1, 1
for _ in range(n-1):
a, b = b, a+b+1
print(b)
177
rovnaká časová zložitosť, ale menšia pamäťová zložitosť
n = 20
a, b = 0, 1
for _ in range(n-1):
a, b = b, a+b
print(b)
6765
n = 0 # NEFUNGUJE PRE n = 0
a, b = 0, 1
for _ in range(n-1):
a, b = b, a+b
print(b)
1
n = 0 # FUNGUJE iba PRE n = 0
a, b = 0, 1
for _ in range(n-1):
a, b = b, a+b
print(a)
0
n = 20 # FUNGUJE iba PRE n = 0
a, b = 0, 1
for _ in range(n-1):
a, b = b, a+b
print(a)
4181
n = 20 # FUNGUJE AJ PRE n = 0
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
print(a)
6765
a, b = 2, 6
a, b = b, a+b+2*6-6
b
14
a, b = b, a+b+2*7-6
b
28
a, b = b, a+b+2*8-6
b
52