PALMA junior
Úloha o vyčítanke

Autorské riešenie
[stiahni vycitanka.py]

• Počet riešiteľov: 19 /  =  %

• Úspešnosť riešenia: 5.38 / 6 = 90 %

Zistiť, kto bude žmúriť ako prvý v princípe nie je ťažké. Vedia to už aj malé deti, ktoré vyčítanky používajú. Našou úlohou je vytvoriť program, ktorého výsledok nám povie, kto bude žmúriť ako prvý.

Pre samotné riešenie je dôležité si ujasniť základné pravidlá a dátové štruktúry, ktoré budeme používať:

• mená detí budeme reprezentovať v zozname (mená v zozname majú svoje pozície a mená môžeme zo zoznamu postupne odstraňovať),

• vyčítanku začíname od mena na začiatku (pozor, jeho index je 0),

• simuláciu vyčítavania (recitovania vyčítanky a ukazovania prstom na deti) nahradíme postupným počítaním indexov v zozname mien (stačí vedieť, na akom indexe začíname a na akom indexe skončíme odriekanie jednej vyčítanky),

• ak dieťa vypadne, jeho meno zo zoznamu odstránime,

  • ak nasleduje vypočítavanie doprava, pomyselný prst presunieme na meno, ktoré sa od vypadnutého nachádza ihneď vpravo,

  • ak nasleduje vypočítavanie doľava, pomyselný prst presunieme na meno, ktorá sa od vypadnutého nachádza ihneď vľavo,

  • ak by sme sa mali presunúť za posledné meno, pokračovať budeme od začiatku, podobne ak by sme sa mali presunúť pred prvé meno, pokračovať budeme od konca.

Výsledná funkcie môže vyzerať nasledovne: 

def kto_zmuri_1(mena, pocet_slabik):
    mena = mena.copy()
    idx_prst = 0
    smer_vpravo = True

    while len(mena) > 1:
        if smer_vpravo:
            idx_prst = (idx_prst + (pocet_slabik - 1)) % len(mena)
            mena.pop(idx_prst)
            idx_prst = idx_prst - 1
        else:
            idx_prst = (idx_prst - (pocet_slabik - 1)) % len(mena)
            mena.pop(idx_prst)
        smer_vpravo = not smer_vpravo
    return mena[0] 

Všimnime si niekoľko detailov:

• zo zoznamu mien budeme mená postupne odstraňovať, pracujeme preto s kópiou tohto zoznamu,

• aktuálnu pozíciu (kam ukazuje prst pri vyčítanke) sme pomenovali idx_prst,

• hodnota premennej smer_vpravo určuje, či postupujeme vpravo (True) alebo vľavo (False),

• ak postupujeme vpravo, k aktuálnemu indexu pripočítame dĺžku vyčítanky,

•  ak postupujeme vľavo, od aktuálneho indexu odpočítame dĺžku vyčítanky,

• keďže aktuálny index je prvý na ktorý ukážeme, od dĺžky vyčítanky odpočítame 1,

• aby nový index neskončil mimo zoznamu, nahradíme ho zvyškom po delení dĺžkou zoznamu mien,

• odstránime prvok zoznamu, kde skončilo vypočítavanie,

• ak je aktuálny smer vpravo, index zmenšíme o 1, pretože prst by mal ukazovať na meno, od ktorého začneme daľšie kolo vyčítanky, pri opačnom smere to nie je nutné, keďže prvky v zozname sa automaticky posunú.

Ak si všimneme časti programu, ktoré sa realizujú pre rôzne smery tak vidíme, že sú si podobné. Rozdiel je v tom, či dĺžku vyčítanky pripočítavame alebo odpočítavame a v úprave nového indexu. Funkciu môžeme upraviť (zjednodušiť) aj nasledovne: 

def kto_zmuri_2(mena, pocet_slabik):
    mena = mena.copy()
    idx_prst = 0
    smer = 1

    while len(mena) > 1:
        idx_prst = (idx_prst + smer * (pocet_slabik - 1)) % len(mena)
        mena.pop(idx_prst)
        if smer == 1:
            idx_prst = idx_prst - 1
        smer = -smer
    return mena[0]

Vaše zaujímavé riešenia a najčastejšie chyby

S touto úlohou ste si poradili veľmi dobre. Často sa opakuje zbytočná chyba, keď namiesto vrátenie výsledku ho funkcia vypisuje. Zbytočne tak strácate cenné body.

Objavilo sa zaujímavé riešenie (null_guru), kde striedanie smerov vyčítanky nahradili otočením celého zoznamu mien, takže smer bol stále rovnaký. V princípe je to správne riešenie, ale nie veľmi efektívne.