Week 4

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

Video (18.10.2018, Paralelka B)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Spočítajme sa

  • Podobne ako v tomto videu, by sme sa mohli spočítať po dvojiciach, trojiciach a pod. Aby bol náš algoritmus čo najefektívnejší, musíme zvážiť koľka-tice ľudí vieme najrýchlejšie nájsť tak, aby sme na konci algoritmu nemali príliš veľa podmienok ohľadne zostávajúceho jedného, dvoch, troch ľuďoch.

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.
  • fibonacci.c, fibonacci.kw, fibonacci2.kw
  • 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í.

loop(N)

  • Pozná ho iba robot Karel.
  • Umožňuje N-krát zopakovať daný príkaz resp. dané príkazy.
  • Zmeníme nekonečný cyklus pomocou loop na 100x vykonaný cyklus (eternal_loop.c, empty.kw):
loop( 100 ){
    runMile();
    turnBack();
}

Podmienené výrazy

  • AND
    • Reprezentujú ho znaky &&
    • Pravdivostná tabuľka:
    • 1 && 1 vráti 1
    • 1 && 0 vráti 0
    • 0 && 1 vráti 0
    • 0 && 0 vráti 0
  • OR
    • Reprezentujú ho znaky ||
    • Pravdivostná tabuľka:
    • 1 || 1 vráti 1
    • 1 || 0 vráti 1
    • 0 || 1 vráti 1
    • 0 || 0 vráti 0
  • Negácia
    • Reprezentuje ju znak !
    • Pravdivostná tabuľka:
    • !1 vráti 0
    • !0 vráti 1
  • Pozrieme sa na podmienku v príklade (eternal_and.c, eternal_or.c, empty.kw):
notFacingNorth() && notFacingSouth()

vs

facingEast() && facingWest()

vs

!facingNorth() && !facingSouth()

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 facingHorizontal(){
    if( facingEast() || facingWest() ){
        return 1;
    }
    return 0;
}
  • Ak nechceme vrátiť celočíselnú hodnotu, môžeme vrátiť pravdivostnú hodotu true alebo false:
bool facingHorizontal(){
    if( facingEast() || facingWest() ){
        return true;
    }
    return false;
}
  • Avšak v takom prípade sa však musíme obrátiť na knižnicu, v ktorej je typ bool zadefinovaný: #define <stdbool.h> (eternal_bool.c)
  • Pozrime sa na iný príklad pre vyplnenie dier na ceste: road_incomplete.c. Na prvej mape road.kw sa algortimus zdá byť úplný, no na mape road2.kw vidíme, že algoritmus je neúplný. Opravíme ho pridaním podmienky pred hlavný cyklus:
int main(){
    turnOn("road2.kw");

    if( rightIsClear() ){    // this was added
        fillPothole();
    }

    while( frontIsClear() ){
        movek();
        if( rightIsClear() ){
            fillPothole();
        }
    }

    turnOff();

    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 fillPothole(){
    if( rightIsBlocked() ){
        return;
    }
    turnRight();
    movek();
    if( noBeepersPresent() ){
        putBeeper();
    }
    turnBack();
    movek();
    turnRight();
}

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 turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}

break vs continue

  • Skomplikujme si náš príklad: highway.c, highway.kw.
  • Čo sa však stane, ak chceme vynechať tú dieru na ceste, ktorá už je označená značkou (highway2.kw)?
  • Pozrime sa teraz na príkazy break a continue. Umožňujú predčasne ukončiť vykonávanie aktuálnej iterácie (slučky cyklu).
  • Avšak príkaz break navyše ukončí vykonávanie celého cyklu (highway_break.c, highway2.kw):
while( frontIsClear() ){
    movek();
    if( beepersPresent() ){
        break;
    }
    fillPothole();
}
while( frontIsClear() ){
    movek();
    if( beepersPresent() ){
        continue;
    }
    fillPothole();
}

Doplňujúce zdroje

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

Video