Zoznam úloh

3. Ako nájsť najmenšie?

Kolo už skončilo. Môžeš si pozrieť vzorové riešenie.

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:

  • vložiť do nej číslo,
  • pozrieť sa, ktoré číslo je v nej aktuálne najmenšie,
  • a dať z nej preč toto najmenšie číslo.

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.

Pre odovzdávanie sa musíš prihlásiť.