Algoritmy s rozhodovaním Nezačaté

0. Kľúčové fakty

1. Algoritmus — Algoritmus je presný, konečný postup krokov, ktorým vyriešime nejakú úlohu alebo problém. Každý algoritmus má jasný začiatok, určené poradie krokov a koniec, v ktorom dostaneme výsledok. Bez algoritmu by počítač nevedel, čo má robiť — práve algoritmus je „recept", podľa ktorého program pracuje.

2. Rozhodovanie (vetvenie) — Vetvenie je časť algoritmu, kde sa postup rozdelí na viac možností podľa toho, či je splnená nejaká podmienka. Vďaka vetveniu sa program nespráva vždy rovnako, ale vie reagovať na rôzne situácie a vstupy. Je to jeden zo základných stavebných prvkov algoritmov popri postupnosti (sekvencii) a cykle (opakovaní).

3. Príkaz ak – tak (if – then) — Konštrukcia „ak – tak" vykoná určitý krok len vtedy, keď je podmienka splnená (pravdivá). Ak podmienka splnená nie je, tento krok sa preskočí a pokračuje sa ďalej. Príklad: ak je číslo väčšie ako 100, tak vypíš „veľké číslo" — výpis sa stane iba pri číslach nad 100.

4. Príkaz ak – tak – inak (if – then – else) — Rozšírené vetvenie má dve vetvy: jednu pre prípad, keď je podmienka pravdivá, a druhú (inak) pre prípad, keď je nepravdivá. Vždy sa vykoná práve jedna z dvoch vetiev, nikdy obe naraz. Príklad: ak je vek ≥ 18, tak vypíš „dospelý", inak vypíš „neplnoletý".

5. Podmienka — Podmienka je tvrdenie, ktoré môže byť buď pravdivé, alebo nepravdivé, a podľa jeho výsledku sa algoritmus rozhodne, ktorou cestou pokračovať. Najčastejšie porovnáva hodnoty, napríklad „je vek väčší ako 12?". Správne sformulovaná podmienka je kľúčová — chybná podmienka vedie k nesprávnemu rozhodnutiu programu.

6. Porovnávacie (relačné) operátory — Na zápis podmienok používame operátory porovnania: rovná sa (=), nerovná sa (≠), väčšie (>), menšie (<), väčšie alebo rovné (≥) a menšie alebo rovné (≤). Pomocou nich vieme porovnať dve čísla alebo hodnoty a získať výsledok pravda/nepravda. Napríklad podmienka „body ≥ 90" je pravdivá, keď žiak získal aspoň 90 bodov.

7. Logické hodnoty pravda a nepravda — Každá podmienka má len dva možné výsledky: pravda (true) alebo nepravda (false). Tieto dve hodnoty rozhodujú o tom, ktorá vetva algoritmu sa vykoná. Práca s pravdou a nepravdou je základom všetkého rozhodovania v informatike a nazýva sa logika.

8. Logické spojky (a, alebo, nie) — Niekedy potrebujeme spojiť viac podmienok naraz pomocou spojok „a" (oba musia platiť), „alebo" (stačí jedna) a „nie" (otočí pravdivosť). Napríklad ak je vek ≥ 13 a má súhlas rodiča, tak povoľ registráciu. Vďaka logickým spojkám vieme zapísať aj zložitejšie rozhodnutia.

9. Vnorené vetvenie — Vnorené vetvenie znamená, že vo vnútri jednej vetvy je ďalšie rozhodovanie (ak vo vnútri ak). Takto vieme postupne rozdeliť situáciu na viac úrovní, napríklad pri prevode bodov na známky 1 až 5. Treba dávať pozor na poradie podmienok, aby sa každý prípad vyhodnotil správne.

10. Vývojový diagram — Vývojový diagram je grafické znázornenie algoritmu pomocou symbolov: ovál pre začiatok a koniec, obdĺžnik pre príkaz a kosoštvorec (romb) pre rozhodovanie. Z kosoštvorca vychádzajú dve šípky označené „áno" a „nie", ktoré ukazujú, kadiaľ ísť podľa výsledku podmienky. Diagram pomáha pochopiť a naplánovať algoritmus skôr, než ho zapíšeme do programu.

11. Testovanie a ladenie (debugovanie) — Testovanie znamená vyskúšať algoritmus na rôznych vstupoch a overiť, či dáva správne výsledky. Dôležité je vyskúšať aj hraničné a netypické prípady, napríklad presne hodnotu 18 pri podmienke veku. Ak nájdeme chybu, opravíme ju — tomuto hľadaniu a odstraňovaniu chýb sa hovorí ladenie alebo debugovanie.

12. Hraničné hodnoty — Hraničné hodnoty sú čísla presne na okraji podmienky, napríklad pri „body ≥ 80" je hranicou číslo 80. Práve na hraniciach vznikajú najčastejšie chyby, lebo si pomýlime > a ≥ alebo < a ≤. Preto pri testovaní algoritmu vždy skúšame hodnoty tesne pod hranicou, na hranici a tesne nad ňou.

1. Poučka

Vetvenie (rozhodovanie) je časť algoritmu, v ktorej sa podľa splnenia podmienky rozhodne, ktoré kroky sa vykonajú. Zapisuje sa príkazom ak – tak (prípadne ak – tak – inak). Podmienka môže byť splnená (pravda), alebo nesplnená (nepravda). Po napísaní algoritmu treba otestovať jeho správnosť — vyskúšať ho na rôznych vstupoch vrátane krajných hodnôt.

2. Vysvetlenie

Algoritmus je presný postup, ako vyriešiť úlohu. Niekedy sa však postup musí rozhodnúť — podľa situácie urobiť jednu alebo druhú vec.

Postupuj takto: 1. Polož otázku (podmienku) — niečo, čo je buď pravda, alebo nepravda. Napr. „Je číslo väčšie ako 10?" 2. ak je podmienka pravda, tak sa vykonajú kroky v časti tak. 3. inak (ak je podmienka nepravda) sa vykonajú iné kroky — alebo sa nevykoná nič. 4. Po vetvení algoritmus pokračuje ďalej.

Nakoniec algoritmus otestuj: zadaj rôzne vstupy a over, či dáva správny výsledok. Skúšaj aj krajné (hraničné) hodnoty — napr. presne číslo 10, nulu, alebo prázdny vstup. Ak nájdeš chybu, oprav ju (to sa volá ladenie).

3. Príklady a prečo je to dôležité

Príklad 1 — ak – tak – inak na hranici: Algoritmus: ak body ≥ 90, tak vypíš „výborný", inak vypíš „skús to nabudúce". Čo vypíše pre 90 bodov a pre 89 bodov?
Vstup 90: podmienka 90 ≥ 90 je pravda (≥ znamená „väčšie alebo rovné") → vykoná sa vetva tak.
Vstup 89: podmienka 89 ≥ 90 je nepravda → vykoná sa vetva inak.
Vždy sa vykoná práve jedna vetva → 90 bodov: „výborný", 89 bodov: „skús to nabudúce"

Príklad 2 — jednoduché ak – tak: Algoritmus pri atrakcii: ak výška ≥ 120 cm, tak vypíš „môžeš ísť". Čo sa stane, keď dieťa meria 115 cm?
Podmienka 115 ≥ 120 je nepravda.
Pri jednoduchom vetvení chýba časť inak, takže sa krok „vypíš" preskočí.
Algoritmus pokračuje ďalej bez výpisu → nevypíše sa nič

Príklad 3 — vnorené vetvenie: Algoritmus: ak body ≥ 80, tak „známka 1", inak (ak body ≥ 60, tak „známka 2", inak „známka 3"). Akú známku dostane žiak so 65 bodmi?
Prvá podmienka: 65 ≥ 80 je nepravda → ideme do vetvy inak.
Vo vnútri je druhá podmienka: 65 ≥ 60 je pravda → vykoná sa jej vetva tak.
Výsledok → známka 2

Príklad 4 — spojka „a": Registrácia: ak vek ≥ 13 a má súhlas rodiča, tak povoľ registráciu, inak ju zamietni. Rozhodni pre Jana (14 rokov, bez súhlasu).
Prvá časť: 14 ≥ 13 je pravda.
Druhá časť: súhlas rodiča nemá, to je nepravda.
Spojka „a" vyžaduje, aby platili obe časti; jedna neplatí, celá podmienka je nepravda → registrácia sa zamietne

Príklad 5 — testovanie a hľadanie chyby: Na úspech v teste treba aspoň 50 bodov. Programátor napísal ak body > 50, tak „prešiel", inak „neprešiel". Otestuj ho na hraničných hodnotách 49, 50, 51.
49 > 50 nepravda → „neprešiel" (správne).
50 > 50 nepravda → „neprešiel" (zle, 50 bodov stačí).
51 > 50 pravda → „prešiel" (správne).
Chyba je presne na hranici, operátor > treba zmeniť na ≥ → správna podmienka je body ≥ 50

Príklad 6 — z bežného života: Ráno sa pozrieš na teplomer: 4 °C. Algoritmus: ak je teplota menšia ako 10 °C, tak obleč bundu, inak obleč mikinu. Čo si oblečieš?
Vstup: teplota 4 °C.
Podmienka 4 < 10 je pravda → vykoná sa vetva tak.
Výsledok → bundu

Prečo je to dôležité: Bez vetvenia by program vždy robil to isté a nevedel by reagovať na situáciu. Vetvenie používa každá aplikácia, hra či robot — vďaka nemu sa počítač „rozhoduje". A testovanie je dôležité preto, aby sme odhalili chyby skôr, než program použijú ľudia (napr. aby hra nepustila na atrakciu niekoho príliš malého).

Precvič si

1. Aké dve hodnoty môže mať každá podmienka?
2. Ktorý symbol vo vývojovom diagrame označuje rozhodovanie?
3. Algoritmus: ak číslo > 100, tak vypíš „veľké". Čo vypíše pre číslo 100?
4. Je podmienka (vek ≥ 10) a (vek ≤ 15) pravdivá pre vek 16?
5. Podmienka prší alebo sneží – je pravdivá, keď neprší, ale sneží?
6. Na zľavu má nárok človek do 26 rokov vrátane. Ktoré tri hodnoty veku použiješ na test hranice?