14 riešení - 12x Java
, 2x Python
RUN ERROR
- java.lang.OutOfMemoryError: Java heap space
- treba binárne vyhľadávať, pričom si priebežné výsledky nemôžeme ukladaťint
, ale odpoveď v druhom riadku v extrémnom prípade nemusíint
, ale operácia súčet pri binárnom vyhľadávaní už pretečie a výsledkom je WRONG ANSWER
int lavy = 1999999998, pravy=1999999999;
System.out.println((lavy+pravy)/2);
//vysledok je -147483649
dá sa
pre $\text{velkost}= 0$ a nedá sa
pre $\text{velkost}=1+\min\left(\max\left(p_i\right), \left\lfloor\frac{ \sum\limits_{i=1}^{k}p_i }{k}\right\rfloor \right)$NO OUTPUT
v okrajovom prípade $n = 1$int(x/2)
namiesto x//2
)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?
hody | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Suma |
---|---|---|---|---|---|---|---|---|---|
Š | 9 | 5 | 3 | 5 | 9 | 2 | C | ||
3,3,1 | * | - | - | * | - | - | * | * | 5 |
2,2,3 | * | - | * | - | * | - | - | * | 10 |
myto = [0, 9, 5, 3, 5, 9, 2, 0]
hody | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Suma |
---|---|---|---|---|---|---|---|---|---|
Š | 9 | 5 | 3 | 5 | 9 | 2 | C | ||
3,3,1 | * | - | - | * | - | - | * | * | 11 |
2,2,3 | * | - | * | - | * | - | - | * | 10 |
hody | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Suma |
---|---|---|---|---|---|---|---|---|---|
Š | 9 | 3 | 5 | 5 | 9 | 2 | C | ||
2,2,3 | * | - | * | - | * | - | - | * | 8 |
3,3,1 | * | - | - | * | - | - | * | * | 7 |
myto = [0, 9, 5, 3, 5, 9, 2, 0]
def sim(pozicia, suma): #som na pozicii a doteraz som zaplatil sumu (vratane pozicie kde som)
if pozicia == len(myto)-1:
print(suma) #nasli sme riesenie
return
for skok in range(1, min(4, len(myto)-pozicia)):
sim(pozicia+skok, suma+myto[pozicia+skok]) #zaplatime myto na policku kde skaceme
sim(0, 0) #zaciname na lavom policku a neplatili sme zatial nic
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
Celkovo ide o 96 volaní sim
a nájde sa 44 spôsobov ako rôzne skákať zo štaru do cieľa.
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [None]*len(myto) #Medzivysledky ... None/-1 znamena ze sme nepocitali
MEM[:4] = myto[:4]
def memo(pozicia):
#ak sme este nepocitali, tak vypocitaj a zapamataj si
if MEM[pozicia] is None:
MEM[pozicia] = myto[pozicia]+min(memo(pozicia-1), memo(pozicia-2), memo(pozicia-3))
return MEM[pozicia]
print(MEM)
print(memo(len(myto)-1)) #posledne, cielove policko
print(MEM)
[0, 9, 5, 3, None, None, None, None] 5 [0, 9, 5, 3, 8, 12, 5, 5]
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [myto[i] if i < 4 else None for i in range(len(myto))] #Medzivysledky ... None/-1 znamena ze sme nepocitali
def memo(pozicia):
#ak sme este nepocitali, tak vypocitaj a zapamataj si
if MEM[pozicia] is None:
MEM[pozicia] = myto[pozicia]+min([memo(pozicia-skok) for skok in range(1, 4)])
return MEM[pozicia]
print(MEM)
print(memo(len(myto)-1)) #posledne, cielove policko
print(MEM)
[0, 9, 5, 3, None, None, None, None] 5 [0, 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 4 30 16 12 5 24 45 3 51 20 95 0 7 73 5 69 47 60 37 36 91 11 73 82 20 84 52 80 0
%%time
##rekurzivna funkcia
def memo(index):
if index < 4:
return myto[index]
return myto[index] + min(memo(index - i) for i in range(1, 4))
memo(len(myto) - 1)
Wall time: 11.8 s
215
%%time
from functools import cache
#zapnuta memoizacia
@cache
def memoCache(index):
if index < 4:
return myto[index]
return myto[index] + min(memoCache(index - i) for i in range(1, 4))
memoCache(len(myto) - 1)
--------------------------------------------------------------------------- ImportError Traceback (most recent call last) <timed exec> in <module> ImportError: cannot import name 'cache' from 'functools' (C:\ProgramData\Anaconda3\lib\functools.py)
Iba od verzie Python 3.9
%%time
from functools import lru_cache
#zapnuta memoizacia
@lru_cache(maxsize=None)
def memoLRU(index):
if index < 4:
return myto[index]
return myto[index] + min(memoLRU(index - i) for i in range(1, 4))
memoLRU(len(myto) - 1)
Wall time: 995 µs
215
OPT = [myto[i] if i < 4 else None for i in range(len(myto))]
for i in range(4, len(myto)):
#magicky vzorec na vypocet i-tej hodnoty
OPT[i] = myto[i]+min(OPT[i-hod] for hod in range(1,4))
print(OPT[-1])
215
$T(n)=O(n)$
https://en.wikipedia.org/wiki/Fibonacci_number
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
%%time
def fib_rek(n):
if n < 2:
return n
return fib_rek(n-1)+fib_rek(n-2)
fib_rek(40)
Wall time: 55.6 s
102334155
$ T(n) = T(n-1)+T(n-2)+1 $
$x^2=x+1$, $x^2-x-1=0$
$T(n)=\phi^n$, kde $\phi$ je zlatý rez
$\phi = \frac{1+\sqrt{5}}{2} = 1.618$
$\frac{a+b}{a}=\frac{a}{b}=\phi$
Majk Spirit - Primetime (Official Video)
https://www.youtube.com/watch?v=rruOu2nIPHc
A trpezlivo staral sa oň ho kým stal sa veľkým,
Bol mu všetkým, takže bol občas ničím,
Ale to musí. Či sa ti to páčí má to
Postupnosť jak Fibonacci
Primetime!
Život bez umenia- hlúposť, na čo je tvor čo netvorí,
Kto klope tomu sa otvorí jak hovorí múdra kniha,
Inteligentný rapper alias moja Odysea,
Rap moja profesia, zlatý rez 1, 6 moje mystérium
%%time
def fib_dp(n):
F = [ i if i < 2 else None for i in range(n+1)]
for i in range(2, n+1):
F[i] = F[i-1]+F[i-2] #! O(n) bitov
return F[-1]
fib_dp(1000)
Wall time: 999 µs
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
n.-té Fibonacciho číslo má približne n bitov, teda nevojde do štandardnej premenej
long
. Sčítanie teda nie je jednoduchá operácia a netrvá $O(1)$, ale až $O(n)$.
Algoritmus | "Časová" zložitosť | Skutočná časová zložitosť |
---|---|---|
rekurzia | $O(\phi^n)$ | $$T(n)=T(n-1)+T(n-2)+n$$, $$T(n)\in O(\phi^n)$$ |
dynamické programovanie | $O(n)$ | $$O(n^2)$$ |
#lepsia pamatova zlozitost O(1)
def fib_pz(n):
a, b = 0, 1
for i in range(n-1):
a, b = b, a+b #Python vyhodnoti vypocty vpravo a potom zapise
return b
fib_pz(40)
102334155
Najrýchlejší spôsob výpočtu $n$-tého Fibonacciho čísla je cez mocninu matice
Algoritmus | "Časová" zložitosť | Skutočná časová zložitosť |
---|---|---|
rekurzia | $O(\phi^n)$ | $$T(n)=T(n-1)+T(n-2)+n$$, $$T(n)\in O(\phi^n)$$ |
dynamické programovanie | $O(n)$ | $$O(n^2)$$ |
rýchle umocňovanie | $O(\log n)$ | $$T(n)=T(n/2)+O(n \log n)$$, $$T(n) \in O(n \cdot \log n)$$ |
Vstupom je číslom $n$, teda veľkosť vstupu je $v = \Theta(\log n)$, zložitosť $O(n^2)$, to je $2^{2*v}$ ako funkcia veľkosti vstupu $v$.
Tento algoritmus je pseudopolynomiálny ... pre číslo $n$ na vstupe je časová zložitosť $T(n) \subset O(n^k)$.
Máme dané rozmery $n$ matíc. Koľko najmenej násobení je potrebné urobiť, aby sme vypočítali výsledný súčin $A_1 \cdot A_2 \cdots A_n $. Rozmery označme $D[i], i=0,\dots,n$, teda matica $A_i$ má rozmery $D[i-1] \times D[i]$.
Násobenie dvoch matíc $A \cdot B = C$. Rozmery matíc $A...a \times b, B ... b \times c, C ... a \times c$. Prvok výslednej matice je skalárny súčin riadku prvej a stĺpca druhej matice
$$ c_{ij} = \sum_{k=1}^{b} a_{ik} \cdot b_{kj}$$$\Theta(a \cdot c \cdot b)$ - pre všetky prvky výslednej matice musíme vypočítať danú sumu.
3
10 30 5 60
$A_1 \cdot A_2 \cdot A_3 = (A_1 \cdot A_2) \cdot A_3 = A_1 \cdot (A_2 \cdot A_3)$
$(A_1 \cdot A_2) \cdot A_3$:
prvým násobením vznikne matica $10 \times 5$ s použitím $10*30*5=1500$ násobení
dalším násobením vznikne matica $10 \times 60$ s použitím $10*5*60=3000$ násobení
$A_1 \cdot (A_2 \cdot A_3)$:
prvým násobením vznikne matica $30 \times 60$ s použitím $30*5*60=9000$ násobení
dalším násobením vznikne matica $10 \times 60$ s použitím $10*30*60=18000$ násobení
V závislosti od poradia násobenia vykonáme buď 4500 alebo 27000 násobení.
$A_1 \cdot A_2 \cdot A_3 \cdot A_4$
$(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)$
$((A_1 \cdot A_2) \cdot A_3) \cdot A_4$
$A_1 \cdot (A_2 \cdot (A_3 \cdot A_4))$
$(A_1 \cdot (A_2 \cdot A_3)) \cdot A_4$
$A_1 \cdot ((A_2 \cdot A_3) \cdot A_4)$
Koľko máme možností na ozátvorkovanie pre 5 matíc?
Koľko máme možností na ozátvorkovanie pre n matíc?
Vieme využiť dynamické programovanie, teda násobenie menšieho počtu matíc ?
$A_1 \cdot (A_2 \cdot (A_3 \cdot A_4))$
$A_1 \cdot ((A_2 \cdot A_3) \cdot A_4)$
$(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)$
$((A_1 \cdot A_2) \cdot A_3) \cdot A_4$
$(A_1 \cdot (A_2 \cdot A_3)) \cdot A_4$
Posledné dve možnosti reprezentujú dva spôsoby ozátvorkovania prvých troch matíc.
$A_1 \cdot (A_2 \cdot (A_3 \cdot A_4))$
$A_1 \cdot ((A_2 \cdot A_3) \cdot A_4)$
$(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)$
$(A_1 \cdot A_2 \cdot A_3) \cdot A_4$
Rovnako prvé dva prípady sú rôzne spôsoby ozátvorkovania posledných troch matíc.
$A_1 \cdot (A_2 \cdot A_3 \cdot A_4)$
$(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)$ ... počet násobení vľavo ?+vpravo ?+posledné násobenie $D[0]*D[2]*D[4]$
$(A_1 \cdot A_2 \cdot A_3) \cdot A_4$
Možnosti sú význačné tým, ktoré násobenie je ako posledné vo výpočte.