Zootechnik

4th Nov 2026

V košickej zoologickej záhrade chcú zlepšiť elektronické služby pre návštevníkov. Pomocou otázok a odpovedí chcú odporučiť návštevníkovi, ktoré zviera v záhrade si má ísť pozrieť.

Nanešťastie, v rozpočte nie sú peniaze na nákup cloudových kreditov ani kúpu GPU. Preto nie je možné použiť inteligentného agenta, ktorý by vedel všetko.

Vaša úloha je navrhnúť jednoduchý dialógový systém, založený na binárnych rozhodovacích stromoch. Bude vedieť napísať otázku a očakáva odpoveď áno alebo nie.

Takýto systém vie bežať aj na tom najjednoduchšom hardvéri. Dokonca sa uvažuje o tom, že ním vybavia ubytovacie zariadenia pre opice, lebo sa najlepšie vedia pohybovať po stromoch.

Vytvorte znalostný systém, ktorý pomôže návštevníkom košickej zoologickej záhrady vybrať zviera, ktoré si chcú pozrieť. Program načíta bázu znalostí zo štandardného vstupu, vypíše počet načítaných otázok a konečných odpovedí a podľa volieb používateľa nájde zviera.

Báza znalostí a vstup

Každý uzol stromu obsahuje jeden riadok textu:

  • Otázka sa končí znakom ? a má presne dvoch potomkov.
  • Konečná odpoveď (názov zvieraťa) sa nekončí znakom ? a nemá potomkov.

Strom je zapísaný vo formáte preorder: najprv uzol, potom celý ľavý podstrom (áno), potom celý pravý podstrom (nie). Voľba áno platí pre prvú možnosť uvedenú v otázke. Každá otázka alebo konečná odpoveď je na samostatnom riadku.

Bázu pravidiel ukončuje povinný prázdny riadok. Aj strom obsahujúci iba jednu konečnú odpoveď je platný. Program musí pracovať s ľubovoľnou platnou bázou v tomto formáte; názvy zvierat ani poradie otázok nezapisujte priamo do programu.

Po prázdnom riadku nasledujú voľby používateľa, každá na samostatnom riadku:

  • a znamená áno: pokračujte do ľavého podstromu;
  • n znamená nie: pokračujte do pravého podstromu.

Platná voľba obsahuje presne jeden znak a alebo n. Rozlišujte malé a veľké písmená; medzery navyše nie sú povolené.

Výstup a priebeh programu

Na začiatku vždy vypíšte:

Expert zo zoo to vie.

Načítajte a skontrolujte celú bázu. Po úspešnom načítaní vypíšte:

Pocet otazok: Q
Pocet odpovedi: A
Odpovedajte 'a' pre prvu moznost alebo 'n' pre druhu moznost.

Namiesto Q a A vypíšte počet všetkých otázok a všetkých konečných odpovedí v načítanej báze, nielen na vybranej ceste. Potom vypíšte text koreňa. Ak je to otázka, načítajte voľbu a vypíšte text vybraného potomka. Opakujte tento postup, kým nevypíšete konečnú odpoveď. Za ňou vypíšte Koniec a program ukončite. Pri strome s jedinou konečnou odpoveďou nečítajte žiadnu voľbu. Po nájdení zvieraťa ignorujte zvyšok vstupu. Texty uzlov vypisujte presne tak, ako boli načítané, bez znakov konca vstupného riadka; každý výstupný riadok ukončite novým riadkom. Hlásenia vypisujte presne podľa zadania, bez diakritiky.

Postup

Jeden riadok bude zodpovedať jednému uzlu v rozhodovacom strome.

V Pythone si jeden uzol môžeme predstaviť ako jednoduchú dátovú triedu:

from dataclasses import dataclass

@dataclass
class Node:
    text: str
    left: "Node | None" = None
    right: "Node | None" = None

Ako rekurzívne načítať strom

Rekurzia je postup, pri ktorom funkcia pri riešení úlohy zavolá samu seba pre menšiu časť problému. Pri stromoch je touto menšou časťou podstrom.

Rekurzívny postup potrebuje dve veci:

  • Ukončovaciu podmienku (triviálny prípad): situáciu, ktorú vieme vyriešiť bez ďalšieho volania, napríklad spracovanie listu.
  • Rekurzívny krok: spracovanie menších podstromov a prípadné spojenie ich výsledkov.

Každé volanie má vlastné lokálne premenné. Keď funkcia zavolá samu seba, pôvodné volanie čaká na výsledok. Po návrate pokračuje na mieste za volaním. Tieto čakajúce volania si program pamätá v zásobníku volaní.

Najprv sa naučte načítať text jediného uzla. Môžete využiť funkcie:

  • input()
  • readline()

Biele znaky na konci reťazca odstránite pomocou funkcie rsrip()

Pri načítaní vstupu rozlišujete druh uzla podľa posledného znaku: otázka sa končí ?, konečná odpoveď nie. Funkcie načítania ale spravidla na koniec pridávajú znaku pre koniec riadka, tieto je potrebné odstrániť, napr. pomocou funkcie rstrip().

Keď je strom vytvorený, uzly ktoré majú potomkov obsahujú otázku. Uzly ktoré nemajú potomkov, obsahujú odpoveď.

Môžete použiť túto šablóonu funkcie:

def read_node():
    # Načítajte riadok zo súboru
    text = read_line()
    if text is None or text == "":
        raise ValueError("Chýba očakávaný uzol")
    # Vytvorte nový uzol z textu. ľavý a pravý podstrom je zatiaľ prázdny
    # node =  ...
    # toto je ukončovacia podmienka. V prípade, že aktuány riadok 
    # je konečná odpoveď tak rekurzia končí.
    if node.text.endswith("?"):
        # TODO: načítajte a pripojte celý ľavý podstrom.
        # node.left = ..
        # TODO: potom načítajte a pripojte celý pravý podstrom.
        # node.right = ... 
        pass
    return node

Rekurzívne počítanie prvkov

Počítanie uzlov môžete riešiť samostatne pre každý podstrom. Výsledok musí závisieť od druhu aktuálneho uzla aj od výsledkov pre jeho podstromy.

Listový uzol, skrátene, nemá žiadnych potomkov. Predstavuje konečnú odpoveď, teda názov zvieraťa. Vnútorný uzol (nelistový uzol) má aspoň jedného potomka; v tomto zadaní má presne dvoch a obsahuje otázku. Koreň môže byť vnútorným uzlom aj listom. Strom s jediným zvieraťom má iba koreň, ktorý je zároveň listom.

Pre zistenie typu uzla si môžete napísať metódu is_leaf() ktorá zistí, či je aktuálny uzol listový alebo nie.

V našej báze počet listov zodpovedá počtu konečných odpovedí a počet vnútorných uzlov počtu otázok.

Pre riešení tohto problému navrhneme rekurzívnu funkciu. Triviálnym prípadom je prázdny (neexistujúci) uzol:

def conut_nodes(node):
    if node is None:
        return 0
     # Potom zistíme počet v na ľavej a na pravej strane:
     count = count_nodes(node.left) + count_nodes(node.right)
     # Ak počítame listové uzly, zistíme či je uzol listový.
     # Počet zväčšíme o jedna v prípade že sa jedná o typ uzla ktorý nás pri počítaní zaujíma.
     # count = count +  ...
     return count

Ako hľadať odpoveď v strome

Po načítaní databázy začnite jej prehľadávanie.

Začnite koreňom a vypíšte jeho text. Ak je uzol listový, už poznáte výsledok a ďalšiu voľbu nečítajte. Pri otázke načítajte presne jednu voľbu a pokračujte do vybraného podstromu na ľavej alebo na pravej strane.

Najprv skúste funkciu, ktorá vypíše text nájdeného zvieraťa. Čítanie voľby používateľa, výber potomka a spracovanie chýb si doplňte sami:

def search(node):
    print(node.text)
    # V prípade, že ste našli odpoveď, ukončite vyhľadávanie.
    if is_leaf(node):
        return node.text
    # TODO: načítajte odpoveď zo štandardného vstupu a overte ju.
    # TODO: Podľa odpovede pokračuje v prehľadávaní vľavo alebo v pravo.
    raise NotImplementedError("Doplňte rozhodovanie podľa voľby") # tento riadok vymažte

Na rozdiel od preorder, inorder a postorder sa pri jednom rozhovore nenavštívi celý strom, ale iba jedna cesta od koreňa k listu. Napríklad cesta n, potom a v ilustračnom strome navštívi A, C a D. Počty otázok a odpovedí však musia zahŕňať celú bázu, aj nenavštívené vetvy.

Neplatná voľba a koniec vstupu sú odlišné situácie; spracujte ich podľa zadania a ďalej už nepokračujte.

Previous Post Next Post

Zootechnik