3. týždeň

Recursion

Karel the Robot - Fibonacciho postupnosť, rekurzia, logické výrazy (AND, OR, NOT), makrá, return, break vs continue

Video (08.10.2024)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Vlastnosti algoritmov - Karel goes Fibonacci

  • Dnes budeme pokračovať riešením rôznych úloh pomocou robota Karla, pričom sa pokúsime zamerať na rôzne vlastnosti algoritmov.
  • Fibonacciho postupnosť je typickým problémom, ktorý sa rieši počas základov algoritmizácie. Viac info tu.
  • Pozrime sa na nasledujúci príklad, kde robot Karel na prázdnej ulici položí značky tak, aby vyjadrovali Fibonacciho postupnosť (fibonacci.c, fibonacci.kw, fibonacci2.kw):
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      100         0
ST.+-------------------------------+
 2 | .   .   .   .   .   .   .   . |
   |                               |
 1 | >   .   .   .   .   .   .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8   AVE.
  • Príklad rieši Fibonacciho postupnosť pomocou robota Karla, ktorý ale nevie počítať. Podstatou príkladu je ukázať, ako je v Karlovom svete možné spočítať dve čísla bez toho, aby bolo nutné použiť premenné a matematiku.
  • Príklad je riešený pomocou rekurzie. Prvok je rekurzívny, ak sa čiastočne skladá, alebo je definovaný pomocou samého seba.
  • Rekurzia je silným nástrojom najmä pri matematických definíciách, napr. prirodzené čísla, stromové štruktúry, funkcie (faktoriál, Fibonacciho čísla, atď.).
  • Prostriedkom pre vyjadrenie rekurzie v programoch je podprogram (funkcia), ktorej identifikátor slúži na rekurzívnu aktiváciu jeho tela.
  • Rekurzívne funkcie dávajú možnosť nekonečných výpočtov a je potrebné riešiť problém ukončenia výpočtu.
  • Kedy používať rekurziu:
    • Rekurzívny program je vhodný, ak riešený problém alebo používané údaje sú definované rekurzívne.
    • Použitie rekurzie nezaručuje, že algoritmus predstavuje najlepšie riešenie problému.
    • Každý rekurzívny program možno transformovať na iteratívny tvar (pomocou cyklov).
    • Pri zložitejších rekurzívnych schémach je však transformácia na iteratívny tvar veľmi nepraktická.
    • Programy, ktoré sú svojou podstatou rekurzívne (skôr než iteratívne), majú byť implementované pomocou rekurzívnych funkcií.

Podmienené výrazy

  • AND
    • Reprezentujú ho znaky &&
    • Pravdivostná tabuľka:
    • 1 && 1 vráti 1, true && true vráti true
    • 1 && 0 vráti 0, true && false vráti false
    • 0 && 1 vráti 0, false && true vráti false
    • 0 && 0 vráti 0, false && false vráti false
  • OR
    • Reprezentujú ho znaky ||
    • Pravdivostná tabuľka:
    • 1 || 1 vráti 1, true || true vráti true
    • 1 || 0 vráti 1, true || false vráti true
    • 0 || 1 vráti 1, false || true vráti true
    • 0 || 0 vráti 0, false || false vráti false
  • NOT (negácia)
    • Reprezentuje ju znak !
    • Pravdivostná tabuľka:
    • !1 vráti 0, !true vráti false
    • !0 vráti 1, !false vráti true
  • V nasledujúcom príklade chceme, aby robot Karel neustále prechádzal od jednej hranice sveta k druhej vo vertikálnom smere. Podmienku otočenia robota na začiatku programu (do vertikálneho smeru) môžeme zapísať rôznymi spôsobmi (eternal_and.c, empty.kw):
not_facing_north() && not_facing_south()

vs

facing_east() || facing_west()

vs

!facing_north() && !facing_south()

return

  • Umožňuje predčasne ukončiť vykonávanie aktuálnej funkcie.
  • Ak funkcia má návratovú hodnotu, return sa použije spolu s konkrétnou návratovou hodnotou (eternal_or.c, empty.kw):
int facing_horizontal() {
    if (facing_east() || facing_west()) {
        return 1;
    }
    return 0;
}
  • Ak nechceme vrátiť celočíselnú hodnotu, môžeme vrátiť pravdivostnú hodnotu true alebo false:
bool facing_horizontal() {
    if (facing_east() || facing_west()) {
        return true;
    }
    return false;
}
  • Avšak v takom prípade sa musíme obrátiť na knižnicu, v ktorej je typ bool zadefinovaný: #include <stdbool.h>.
  • V prípade robota Karla je knižnica stdbool už zahrnutá v rámci hlavičkových súborov karel.h a superkarel.h.
  • Pozrime sa na iný príklad pre vyplnenie dier na ceste: road_incomplete.c. Na prvej mape road.kw sa algortimus zdá byť úplný:
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 2)   EAST       2         0
ST.+-------------------+
 2 | >   .   .   .   . |
   |---+   +---+   +---|
 1 | . | 1 | . | . | . |
   +-------------------+
     1   2   3   4   5   AVE.
  • No na mape road2.kw vidíme, že algoritmus je neúplný:
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 2)   EAST       5         0
ST.+---------------------------+
 2 | >   .   .   .   .   .   . |
   |   |   +-------+   +---+   |
 1 | . | . | .   . | 1 | . | . |
   +---------------------------+
     1   2   3   4   5   6   7   AVE.
  • Opravíme ho pridaním podmienky pred hlavný cyklus:
int main(){
    turn_on("road2.kw");

    if (right_is_clear()) {    // this was added
        fill_pothole();
    }

    while (front_is_clear()) {
        step();
        if (right_is_clear()) {
            fill_pothole();
        }
    }

    turn_off();

    return 0;
}
  • Vráťme sa však k príkazu return. Ak funkcia nemá návratovú hodnotu, return sa použije ako samostatný príkaz (road_return.c, road2.kw):
void fill_pothole() {
    if (right_is_blocked()) {
        return;
    }
    turn_right();
    step();
    if (no_beepers_present()) {
        put_beeper();
    }
    turn_back();
    step();
    turn_right();
}

Object-like Macros

  • Čo je to makro? Príkaz preprocesora.
  • Makrá používame, ak potrebujeme zjednotiť výskyt hodnôt v kóde, napr. (road_macro.c, road2.kw):
#define SPEED 200

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}

break vs continue

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 4)   EAST      99         0
ST.+-----------------------------------+
 6 | .   .   .   .   .   .   .   .   . |
   |                                   |
 5 | .   .   .   .   .   .   .   .   . |
   |                                   |
 4 | >   .   .   .   .   .   .   .   . |
   |   |   +---+   |   +---+   |   |   |
 3 | . | 1 | . | . | . | . | . | 1 | . |
   |   |   |   +---+   |   |   |   |   |
 2 | . | 1 | .   . | 1 | . | 1 | . | . |
   |   +---+	   |   |   +---+   |   |
 1 | . | .   .   . | . | .   . | . | . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.
  • Čo sa stane, ak chceme vynechať tú dieru na ceste, ktorá už je označená značkou (highway2.kw)?
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 4)   EAST      99         0
ST.+-----------------------------------+
 6 | .   .   .   .   .   .   .   .   . |
   |                                   |
 5 | .   .   .   .   .   .   .   .   . |
   |                                   |
 4 | >   .   .   .   1   .   1   .   . |
   |   |   +---+   |   +---+   |   |   |
 3 | . | 1 | . | . | . | . | . | 1 | . |
   |   |   |   +---+   |   |   |   |   |
 2 | . | 1 | .   . | 1 | . | 1 | . | . |
   |   +---+	   |   |   +---+   |   |
 1 | . | .   .   . | . | .   . | . | . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.
  • Pozrime sa teraz na príkazy break a continue. Umožňujú predčasne ukončiť vykonávanie aktuálnej iterácie (slučky cyklu).
  • Príkaz break ukončí vykonávanie aktuálnej slučky cyklu a navyše ukončí vykonávanie celého cyklu (highway_break.c, highway2.kw):
while (front_is_clear()) {
    step();
    if (beepers_present()) {
        break;
    }
    fill_pothole();
}
  • Kým príkaz continue ukončí vykonávanie aktuálnej slučky cyklu a pokračuje opäť podmienkou cyklu (neukončí vykonávanie cyklu) (highway_continue.c, highway2.kw):
while (front_is_clear()) {
    step();
    if (beepers_present()) {
        continue;
    }
    fill_pothole();
}
  • Samozrejme, aj tu platí, že úloha má viac riešení. V našom prípade sa dokonca môžeme vyhnúť príkazom break či continue:
while (front_is_clear()) {
    step();
    if (no_beepers_present()) {
        fill_pothole();
    }
}

Doplňujúce zdroje

  1. Break vs continue
  2. Typ bool: c-reference, cplusplus.com

Video