autor: Lucia Budinská
kategorie: Benjamin, obtížnost: lehká, rok: 2018, kód úlohy: 2018-SK-07

tematická oblast: algoritmická úloha

Zadání

Milan pracuje v hotelu. Majitel nechal vyrobit nové tabulky s čísly pokojů a Milan je rozvěšuje na dveře pokojů. Řídí se následujícími pravidly:

  • Pokud dojde ke dveřím s číslem, tak:
    • pokud s sebou nese číslo menší, než je na těch dveřích, půjde po chodbě doleva.
    • pokud s sebou nese číslo větší, než je na těch dveřích, půjde po chodbě doprava.
  • Pokud dojde k neoznačeným dveřím, připevní na ně číslo, které nese.

Milan stojí u dveří s číslem 50 a potřebuje připevnit číslo 29. Najdi pro číslo 29 správné dveře. Klikni na ně.


Zdůvodnění správné odpovědi

Cestu vedoucí ke správným dveřím ukazuje obrázek.

Začínáme u pokoje 50.
29 je menší než 50, proto jdeme doleva.
Přijdeme ke dveřím 24. 29 je větší než 24, proto jdeme chodbou doprava.
Přijdeme ke dveřím 34. 29 je menší než 34, takže jdeme doleva.
Dostali jsme se k dveřím bez čísla, proto na ně můžeme pověsit číslo 29.


Co má tato úloha společného s informatikou

V této úloze se zabýváme grafem nazývaným binární strom - v něm se vždy jedna větev větví do dvou menších. Binární strom je jedna ze základních datových struktur, používaná v informatice k ukládání a vyhledávání dat.

Hotelové dveře jsou vlastně uzly binárního stromu, čísla na dveřích jsou naše uložené údaje a my se snažíme najít správné místo, kam uložit další údaj - číslo 29. Binární stromy se řídí stejnými pravidly jako Milan v této úloze. Pokud je aktuální uzel (u kterého stojí) zaplněný, údaje s menší hodnotou jdou do uzlu nalevo a údaje s větší hodnotou do uzlu napravo.

Více o binárních stromech si můžeš přečíst zde: https://cs.wikipedia.org/wiki/Binární_strom/