Predstavme si jednorozmernú hraciu plochu. Prvé (ľavé) políčko je štartovacie, posledné (pravé) cieľové. Ostatné políčka reprezentujú rôzne mestá a obahujú číselný údaj - mýto za prechod mestom. V jednom ťahu sa hráč pohybuje o 1 až tri políčka (hádže sa kockou, kde sú hodnoty 1, 2, 3 dva krát).
Akú minimálnu sumu je možné dosiahnuť pri uvedenej hre, presun zo štartovacieho do cieľového políčka?
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma):
... vyskusat vsetky skoky (1-3) ...
... ukocenie rekurzie/baza, teda posledne policko ...
skoky(0, 0)
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma):
#... ukocenie rekurzie/baza, teda posledne policko ...
#potrebujeme platit za myto
skoky(pozicia+1, suma)
skoky(pozicia+2, suma)
skoky(pozicia+3, suma)
skoky(0, 0)
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma):
#ukocenie rekurzie/baza, teda posledne policko ...
if pozicia == len(myto)-1:
print(suma)
return
suma += myto[pozicia] #potrebujeme platit za myto
skoky(pozicia+1, suma)
skoky(pozicia+2, suma)
skoky(pozicia+3, suma)
skoky(0, 0)
33
--------------------------------------------------------------------------- IndexError Traceback (most recent call last) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in <cell line: 13>() 11 skoky(pozicia+3, suma) 12 ---> 13 skoky(0, 0) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 7 return 8 suma += myto[pozicia] #potrebujeme platit za myto ----> 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 8 suma += myto[pozicia] #potrebujeme platit za myto 9 skoky(pozicia+1, suma) ---> 10 skoky(pozicia+2, suma) 11 skoky(pozicia+3, suma) 12 ~\AppData\Local\Temp\ipykernel_16092\2140699488.py in skoky(pozicia, suma) 6 print(suma) 7 return ----> 8 suma += myto[pozicia] #potrebujeme platit za myto 9 skoky(pozicia+1, suma) 10 skoky(pozicia+2, suma) IndexError: list index out of range
Na posledných políčkach už nemáme k dispozícii všetky 3 skoky, treba kontrolovať ... buď pri kaýdom skoku alebo pri začiatku rekurzívnej funkcie
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma):
if pozicia >= len(myto):
return
#ukocenie rekurzie/baza, teda posledne policko ...
if pozicia == len(myto)-1:
print(suma)
return
suma += myto[pozicia] #potrebujeme platit za myto
skoky(pozicia+1, suma)
skoky(pozicia+2, suma)
skoky(pozicia+3, suma)
skoky(0, 0)
33 31 24 22 28 26 19 30 28 21 19 25 23 28 26 19 17 23 21 14 25 23 16 14 24 22 15 13 19 17 10 21 19 12 10 16 14 19 17 10 8 14 12 5
Koľko je možností?
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma):
global pocet
if pozicia >= len(myto):
return
#ukocenie rekurzie/baza, teda posledne policko ...
if pozicia == len(myto)-1:
print(suma)
pocet += 1
return
suma += myto[pozicia] #potrebujeme platit za myto
skoky(pozicia+1, suma)
skoky(pozicia+2, suma)
skoky(pozicia+3, suma)
pocet = 0
skoky(0, 0)
print(f'pocet moznosti {pocet}')
33 31 24 22 28 26 19 30 28 21 19 25 23 28 26 19 17 23 21 14 25 23 16 14 24 22 15 13 19 17 10 21 19 12 10 16 14 19 17 10 8 14 12 5 pocet moznosti 44
Ako sa pri nich skákalo? Aké hody padli?
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma, hody):
global pocet
if pozicia >= len(myto):
return
#ukocenie rekurzie/baza, teda posledne policko ...
if pozicia == len(myto)-1:
print(suma, hody) #okrem sumy vypíšeme aj hody
pocet += 1
return
suma += myto[pozicia] #potrebujeme platit za myto
skoky(pozicia+1, suma, hody+[1])
skoky(pozicia+2, suma, hody+[2])
skoky(pozicia+3, suma, hody+[3])
pocet = 0
skoky(0, 0, [])
print(f'pocet moznosti {pocet}')
33 [1, 1, 1, 1, 1, 1, 1] 31 [1, 1, 1, 1, 1, 2] 24 [1, 1, 1, 1, 2, 1] 22 [1, 1, 1, 1, 3] 28 [1, 1, 1, 2, 1, 1] 26 [1, 1, 1, 2, 2] 19 [1, 1, 1, 3, 1] 30 [1, 1, 2, 1, 1, 1] 28 [1, 1, 2, 1, 2] 21 [1, 1, 2, 2, 1] 19 [1, 1, 2, 3] 25 [1, 1, 3, 1, 1] 23 [1, 1, 3, 2] 28 [1, 2, 1, 1, 1, 1] 26 [1, 2, 1, 1, 2] 19 [1, 2, 1, 2, 1] 17 [1, 2, 1, 3] 23 [1, 2, 2, 1, 1] 21 [1, 2, 2, 2] 14 [1, 2, 3, 1] 25 [1, 3, 1, 1, 1] 23 [1, 3, 1, 2] 16 [1, 3, 2, 1] 14 [1, 3, 3] 24 [2, 1, 1, 1, 1, 1] 22 [2, 1, 1, 1, 2] 15 [2, 1, 1, 2, 1] 13 [2, 1, 1, 3] 19 [2, 1, 2, 1, 1] 17 [2, 1, 2, 2] 10 [2, 1, 3, 1] 21 [2, 2, 1, 1, 1] 19 [2, 2, 1, 2] 12 [2, 2, 2, 1] 10 [2, 2, 3] 16 [2, 3, 1, 1] 14 [2, 3, 2] 19 [3, 1, 1, 1, 1] 17 [3, 1, 1, 2] 10 [3, 1, 2, 1] 8 [3, 1, 3] 14 [3, 2, 1, 1] 12 [3, 2, 2] 5 [3, 3, 1] pocet moznosti 44
Koľko volaní rekurzie nastane?
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def skoky(pozicia, suma, hody):
global pocet, pocet_volani
pocet_volani += 1
if pozicia >= len(myto):
return
#ukocenie rekurzie/baza, teda posledne policko ...
if pozicia == len(myto)-1:
print(suma, hody) #okrem sumy vypíšeme aj hody
pocet += 1
return
suma += myto[pozicia] #potrebujeme platit za myto
skoky(pozicia+1, suma, hody+[1])
skoky(pozicia+2, suma, hody+[2])
skoky(pozicia+3, suma, hody+[3])
pocet = 0
pocet_volani = 0
skoky(0, 0, [])
print(f'{pocet} moznosti a {pocet_volani} volani')
33 [1, 1, 1, 1, 1, 1, 1] 31 [1, 1, 1, 1, 1, 2] 24 [1, 1, 1, 1, 2, 1] 22 [1, 1, 1, 1, 3] 28 [1, 1, 1, 2, 1, 1] 26 [1, 1, 1, 2, 2] 19 [1, 1, 1, 3, 1] 30 [1, 1, 2, 1, 1, 1] 28 [1, 1, 2, 1, 2] 21 [1, 1, 2, 2, 1] 19 [1, 1, 2, 3] 25 [1, 1, 3, 1, 1] 23 [1, 1, 3, 2] 28 [1, 2, 1, 1, 1, 1] 26 [1, 2, 1, 1, 2] 19 [1, 2, 1, 2, 1] 17 [1, 2, 1, 3] 23 [1, 2, 2, 1, 1] 21 [1, 2, 2, 2] 14 [1, 2, 3, 1] 25 [1, 3, 1, 1, 1] 23 [1, 3, 1, 2] 16 [1, 3, 2, 1] 14 [1, 3, 3] 24 [2, 1, 1, 1, 1, 1] 22 [2, 1, 1, 1, 2] 15 [2, 1, 1, 2, 1] 13 [2, 1, 1, 3] 19 [2, 1, 2, 1, 1] 17 [2, 1, 2, 2] 10 [2, 1, 3, 1] 21 [2, 2, 1, 1, 1] 19 [2, 2, 1, 2] 12 [2, 2, 2, 1] 10 [2, 2, 3] 16 [2, 3, 1, 1] 14 [2, 3, 2] 19 [3, 1, 1, 1, 1] 17 [3, 1, 1, 2] 10 [3, 1, 2, 1] 8 [3, 1, 3] 14 [3, 2, 1, 1] 12 [3, 2, 2] 5 [3, 3, 1] 44 moznosti a 157 volani
Namiesto opakovania výpočtov použijeme memoizáciu
, teda postup zhora-nadol:
#memoizacia
MEM = [None]*len(myto)
def myto_mem(policko):
#ak sme pocitali, tak pouzijeme zapamatanu hodnotu
#ak nie, tak vypocitame a zapamatame si ju
if MEM[policko] is None: #vypocitame, ak sme este nepocitali
MEM[policko] = ... #"magicky" vzorec
return MEM[policko]
myto_mem(len(myto)-1) #memoizacia ide od konca
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [None]*len(myto)
def myto_mem(policko):
#ukoncenie rekurzie
if policko <= 0: #zaciatok, resp. mimo hracie pole
return 0 #neplatili sme nic
#ak sme pocitali, tak pouzijeme zapamatanu hodnotu
#ak nie, tak vypocitame a zapamatame si ju
if MEM[policko] is None: #vypocitame, ak sme este nepocitali
MEM[policko] = min(myto_mem(policko-1),myto_mem(policko-2), myto_mem(policko-3))
return MEM[policko]
myto_mem(len(myto)-1) #memoizacia ide od konca
0
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [None]*len(myto)
def myto_mem(policko):
#ukoncenie rekurzie
if policko <= 0: #zaciatok, resp. mimo hracie pole
return 0 #neplatili sme nic
#ak sme pocitali, tak pouzijeme zapamatanu hodnotu
#ak nie, tak vypocitame a zapamatame si ju
if MEM[policko] is None: #vypocitame, ak sme este nepocitali
MEM[policko] = myto[policko]+min(myto_mem(policko-1),myto_mem(policko-2), myto_mem(policko-3))
return MEM[policko]
myto_mem(len(myto)-1) #memoizacia ide od konca
5
MEM
[None, 9, 5, 3, 8, 12, 5, 5]
from random import randrange
myto = [0]+[randrange(0,100) for i in range(28)]+[0]
print(*myto)
0 73 16 4 30 64 84 47 34 99 56 6 21 41 3 50 31 89 19 78 98 30 76 28 28 7 21 66 98 0
%%time
##rekurzivna funkcia
def memo(index):
if index < 4: #na prve tri policka mozeme skocit priamo
return myto[index]
return myto[index] + min(memo(index - i) for i in range(1, 4))
memo(len(myto) - 1)
Wall time: 6.14 s
240
from functools import cache
%%time
##rekurzivna funkcia
@cache #pouzi memoizaciu pre nasleduju funkciu ... memo = cache(memo)
def memo(index):
if index < 4: #na prve tri policka mozeme skocit priamo
return myto[index]
return myto[index] + min(memo(index - i) for i in range(1, 4))
memo(len(myto) - 1)
Wall time: 0 ns
240
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [None, 9, 5, 3, 8, 12, 5, 5]
Vieme tieto hodnoty vypočítať postupne od najmenších?
12 = 9 + min([5,3,8])
myto = [0, 9, 5, 3, 5, 9, 2, 0]
DP = [None]*len(myto)
DP[:4] = myto[:4] #prve styri hodnoty zostavaju
for policko in range(4, len(myto)):
DP[policko] = myto[policko] + min(DP[policko - i] for i in range(1, 4))
DP
[0, 9, 5, 3, 8, 12, 5, 5]
4 cukríky 3 deti
1. | 2. | 3. |
---|---|---|
4 | 0 | 0 |
3 | 1 | 0 |
2 | 2 | 0 |
2 | 1 | 1 |
$C$ cukríkov, $D$ detí ... koľko je možností ?