PALMA junior
Úloha o falošných percentách

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 18 / 23 = 78%

• Úspešnosť riešenia:  4,4 / 6 = 73%

Úlohu bolo možné riešiť viacerými spôsobmi. Napríklad postupným prechodom všetkých možných hodnôt (lineárne vyhľadávanie), ale aj binárnym vyhľadávaním. Nasledujúci obrázok vyjadruje postup pri hľadaní percentuálnej hodnoty 87,5 pri triede s ôsmimi žiakmi. Môžeme vidieť, že kým pri postupnom prechode všetkých možných hodnôt (lineárne vyhľadávanie) sa pri výpočte vykoná až 8 porovnaní s hľadanou hodnotou, binárne vyhľadávanie vyžaduje len tri porovnania. Keďže v zadaní bola požiadavka na čo najefektívnejšie riešenie, v nasledujúcom uvedieme postup pomocou binárneho vyhľadávania.

Binárne vyhľadávanie je vyhľadávací algoritmus, ktorý môžeme využiť pri hľadaní konkrétnej hodnoty v usporiadanom zozname hodnôt. V každom kroku nájdeme stred prehľadávaného úseku zoznamu. Porovnáme hodnotu v stredeprehľadávanej časti s hľadanou hodnotou a následne upravíme hranice prehľadávanej časti zoznamu.

• Ak sa hodnoty rovnajú, hľadanú hodnotu sme našli a môžeme skončiť.

• Ak je hľadaná hodnota väčšia ako hodnota v strede, presunieme hranicu ľavej časti za stred.

• Ak je hľadaná hodnota menšia ako hodnota v strede, presunieme hranicu pravej časti pred stred. 

Tot opakujeme dovtedy,kým hľadanú hodnotu nenájdeme alebo kým prehľadávaný úsek má ešte aspoň jeden prvok.

Dá sa dokázať, že takéto vyhľadávanie je efektívnejšie ako lineárne vyhľadávanie (z hľadiska potrebného počtu porovnaní).

Nasleduje možné riešenie v jazyku Python.

    index_dole = 0
    index_hore = pocet_ziakov
    while index_dole<=index_hore:
        stred = (index_dole+index_hore)//2   # delenie so zaokruhlenim nadol

        hodnota_stred = round(((100/pocet_ziakov)*stred),2)

        if hodnota_stred == hodnota:
            return True
        if hodnota_stred < hodnota:
            index_dole = stred + 1
        else:
            index_hore = stred - 1

    return False

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

Úlohu riešilo 18 tímov. Žiaden tím nepoužil binárne vyhľadávanie, ale väčšina tímov úlohu vyriešila správne pomocou lineárneho vyhľadávania alebo priamym výpočtom. V niektorých riešeniach boli nedostatky v dôsledku chýbajúceho, resp. nesprávne použitého zaokrúhľovania na dve desatinné miesta. Niektoré riešenie pri percentuálnej hodnote umožňovali používať len celé kladné čísla. Jeden tím pri cykle while použil nesprávne nerovnosti, preto sa podmienka nevyhodnocovala korektne. Tím guru main.py správne poznamenal, že v zadaní nebolo úplne jasne definované, či sa percentuálna hodnota zaokrúhľuje alebo len odstriháva. Z tohto dôvodu vo svojom riešení doplnili ďalší vstupný parameter v podobe: #otazka - 1-zaukruhluje, 0-odstrihava.