Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí, ako vieš svoje riešenia zlepšiť.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected]
Tomáš dostal na Vianoce zázračnú krabičku, do ktorej si vie ukladať čísla. Krabička si pamätá zoznam čísel, ktoré sú v nej. Jedno číslo môže byť v zozname aj viackrát. Navyše vie krabička rýchlo zistiť, ktoré číslo je v nej najmenšie.
Presnejšie, s krabičkou sa dajú robiť tieto tri veci:
Ak je krabička prázdna, tak keď sa pozrieme, čo je v nej najmenšie, zistíme, že tam nič nie je, a samozrejme z nej už nemôžeme nič dať preč.
Napríklad ak je krabička na začiatku prázdna, môžeš do nej dať postupne $3$, $5$, $1$, $1$, potom najmenšie číslo bude $1$. Potom z nej vieš dať preč $1$, ale ešte je tam druhá jednotka, takže najmenšie číslo bude stále $1$. Ak dáš preč aj druhú jednotku, po novom bude najmenšie číslo $3$.
Tomáša by teraz zaujímalo, či sa dá krabička použiť aj na nejaké zložitejšie úlohy. Pre každú úlohu vymyslite, ako môže Tomáš využiť krabičku (alebo kľudne aj viacero krabičiek), aby vedel efektívne robiť to, čo od neho úloha chce. Efektívne znamená, že to chce urobiť na čo najmenej použití krabičky, teda čo najmenej krát s ňou robiť tie operácie, čo boli popísané na začiatku zadania.
Tomáš vie robiť s číslami to, čo by ste od neho čakali: teda vie sčítavať, odčítavať, násobiť, deliť, porovnávať čísla, vie používať krabičky (má ich ľubovoľne veľa, koľko si povie na začiatku), a vie si pamätať zopár čísel aj mimo krabičiek. Tomáš ale má len obmedzenú pamäť, takže keď si chce pamätať zoznam čísel, ktorý môže byť ľubovoľne dlhý, musí na to použiť krabičku.
a. Krabička vie hľadať najmenšie číslo v nej, ale čo ak by chcel Tomáš vedieť vždy to najväčšie číslo?
Teda Tomáš si chce nejakým spôsobom pamätať zoznam čísel, vedieť do neho pridávať čísla, povedať, čo je v ňom najväčšie, a toto najväčšie číslo z neho dať preč.
Samozrejme, mohol by vždy vybrať všetky čísla von, pozrieť sa na to, ktoré tam ostalo ako posledné, a potom ich všetky vrátiť späť dovnútra, ale to by trvalo dlho, a Tomáš chce používať krabičku čo najmenej.
b. Krabička vie odstrániť najmenšie číslo, ktoré je v nej, ale čo ak chce Tomáš odstrániť nejaké iné konkrétne číslo?
Teda Tomáš si chce pamätať zoznam čísel, vedieť do neho pridávať čísla a povedať, čo je v ňom najmenšie, a vedieť z neho dať preč ľubovoľné konkrétne číslo.
c. Keď máme postupnosť čísel, niekedy sa hodí vedieť jej medián. To je také číslo, že keď si tie čísla usporiadame, tak medián je to, ktoré bude uprostred (keď je čísel párny počet, tak sú uprostred dve čísla, tak môžeme zobrať to viac vľavo). Napríklad pre postupnosť $1, 3, 3, 5, 6, 8, 9$ je jej medián $5$.
No a čo keby sme chceli robiť niečo podobné ako krabička, ale vedieť povedať aj medián?
Teda Tomáš si chce pamätať zoznam čísel, vedieť doňho pridávať a odoberať konkrétne čísla, a vedieť povedať ich medián.
Niekedy sa môže stať, že sa ti riešenie nejakej podúlohy zíde pri riešení tej ďalšej. Napríklad ak vyriešiš podúlohu a., tak si môžeš predstaviť, že už má Tomáš novú zázračnú krabičku, ktorá vie hľadať a dávať preč najväčšie číslo z nej (lebo to vie dosiahnuť pomocou tých pôvodných krabičiek). Potom to teda môžeš kľudne používať pri riešení tých ďalších úloh.
Záporné čísla sú usporiadané opačne ako kladné, napríklad keď $3 < 5$, tak $-5 < -3$. Stačí teda do krabičky dávať namiesto čísla $x$ číslo $-x$. Potom najmenšie z tých $-x$-ov bude zodpovedať najväčšiemu $x$-u.
Aby sa to ľahšie popisovalo, budeme hovoriť, že najmenšie číslo v krabičke je “na vrchu”. Dajme tomu, že chceme dať preč nejaké číslo $x$.
Ak $x$ nie je na vrchu, tak ho nemôžeme dať preč hneď. Nás ale zaujíma iba, ktoré číslo je na vrchu, takže $x$ tam zatiaľ môžeme nechať, a až keď sa dostane na vrch, potom ho dáme preč.
Na to, aby sme toto vedeli robiť, si ale potrebujeme pamätať, ktoré sú tie čísla (ako $x$), ktoré čakajú na odstránenie. No a na to použijeme – hádaj čo – ďalšiu krabičku.
Nás totiž vždy zaujíma, či to číslo, ktoré je práve na vrchu, čaká na odstránenie alebo nie. To znamená, že nám stačí v každom momente vedieť iba najmenšie číslo, ktoré čaká na odstránenie. Označme toto číslo $m$.
Toto $m$ nemôže byť menšie ako najmenšie číslo v krabičke ($m$ musí byť v krabičke, inak nemáme čo dávať preč). Ak je $m$ presne číslo na vrchu krabičky, tak ho môžeme dať preč z krabičky aj zo zoznamu čakajúcich čísel. Ak je $m$ väčšie ako číslo na vrchu krabičky, tak všetky ostatné čakajúce čísla sú ešte väčšie, takže nerobíme nič.
Hlavná myšlienka je, že si chceme pamätať “dolnú” a “hornú” polovicu čísel. Medián bude to najväčšie z dolnej polovice.
Budeme mať dve krabičky, dolnú a hornú. Dolná si bude pamätať najväčšie číslo a horná najmenšie (tak, ako je to popísané v úlohe a.) Keď pridávame číslo, tak ho pridáme do tej správnej krabičky (ak je menšie ako aktuálny medián, tak do dolnej, inak do hornej). Ak je v dolnej krabičke o $2$ čísla viac ako v hornej, tak z dolnej dáme preč to najväčšie číslo a pridáme ho do hornej – a naopak, ak je v hornej o $1$ číslo viac. Tým dosiahneme, že v oboch krabičkách rovnaký počet čísel (+ možno v dolnej o $1$ viac, ak je ich nepárny počet). Číslo na vrchu dolnej krabičky teda bude medián.
Odoberanie konkrétnych čísel už vieme dorobiť jednoducho, tak ako v úlohe b. K obom krabičkám si teda pamätáme ešte čísla, ktoré čakajú na vyhodenie (v ďalších dvoch krabičkách). Potom, čo dáme preč nejaké číslo z vrchu jednej z krabičiek, sa vždy musíme postarať, aby boli krabičky vyvážené (teda ak je príliš veľa čísel v dolnej, tak ich presunúť do hornej, a naopak).
Akurát je tu ešte jeden detail, že si musíme pamätať, koľko čísel máme v každej krabičke (bez tých, ktoré čakajú na vyhodenie), aby sme vedeli, kedy a ako treba dolnú a hornú krabičku vyvažovať.
Asi ťa neprekvapí, že niečo ako tieto zázračné krabičky vie byť užitočné pri programovaní. Takejto krabičke sa hovorí halda alebo prioritná fronta (angl. heap alebo priority queue, keby si chcel(a) googliť). Vo väčšine známych programovacích jazykov je halda súčasť štandardnej knižnice, takže si ju stačí importovať a môžeš použiť.
V Pythone je halda obyčajné pole, ale používajú sa špeciálne funkcie na vkladanie a odoberanie prvkov, ktoré zabezpečia, že to je rýchle.
from heapq import heappush, heappop
heap = []
heappush(halda, 3) # pridám do haldy 3
heappush(halda, 2)
heap[0] # => 2, najmenšie číslo je vždy na začiatku
heappop(halda) # => 2, dám preč najmenšie číslo a vrátim ho
heap[0] # => 3
Pre ostatné jazyky si vygoogli :)
Samozrejme, aby to malo zmysel, tak tá halda musí byť naprogramovaná tak, aby tie operácie vedela robiť rýchlo. Ak ťa zaujíma, ako sa to robí, môžeš si o tom prečítať napríklad v KSP kuchárke.