Week 3

Algoritmus, Karel the Robot, základná štruktúra programu, preklad a spustenie programu, Don't Repeat Yourself (DRY), funkcia, typ void, definícia/deklarácia, sekvencia, vetvenie (if, if/else), iterácia a cyklus (while, do-while), maze & harvest problem

Video (10.10.2018, Paralelka A)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Úvod

  • Predmet sa volá Zaklady algoritmizácie a programovania. Programovať budeme v jazyku C.
  • Naša stránka: http://it4kt.cnl.sk/c/zap
    • tu nájdete zadania (Problem Sets), cvičenia (Labs), prednášky (Lectures), príklady použité na prednáškach aj všetko potrebné pre úspešné absolvovanie tohto kurzu.
    • vybrané časti našej stránky budú v ruskom jazyk
  • Ak hľadáte literatúru pre tento predmet, môžete použiť:
  • Inšpirovať sa môžete aj inými kurzami, napr.
  • Pravidlá hodnotenia nájdete tu
  • Pri absolvovaní predmetu budeme dbať na to, aby ste postupovali podľa etického kódexu a to hlavne pri práci na Vašich zadaniach. Včas Vás naň budeme opätovne upozorňovať.

Algoritmus

  • Popis postupného riešenia problému (kódom alebo vývojovým diagramom
  • Postupne počas semestra si tento termín upresníme

Karel the Robot

  • Jednoduchý úvod do programovania, už ste sa s ním stretli na cvičeniach
  • Svet - dvojrozmerný
  • Steny - objekty vo svete, komplikujú nám vykonávanie úloh
  • Značky - objekty vo svete, môžeme ich zbierať alebo ukladať
  • Karel - objekt vo svete, pomocou neho riešime rôzne úlohy
  • Stavový riadok - obsahuje informácie o aktuálnej pozícii Karla, jeho smerovaní, počte značiek v jeho batohu a počte značiek na aktuálnej pozícii (keďže vidíme Karla, ale značky pod ním nie)
  CORNER  FACING  BEEP-BAG  BEEP-CORNER
  (3, 2)   EAST       0         1
 ST.+-----------------------------------+
  9 | .   .   .   .   .   .   .   .   . |
    |                                   |
  8 | .   .   .   .   .   .   .   .   . |
    |                                   |
  7 | .   .   .   .   .   .   .   .   . |
    |                                   |
  6 | .   .   .   .   .   .   .   .   . |
    |                       +---+       |
  5 | .   .   .   .   .   . | . | .   . |
    |                   +---+   |       |
  4 | .   .   .   .   2 | .   . | .   . |
    |               +---+       |       |
  3 | .   .   .   . | .   .   . | .   . |
    |           +---+           |       |
  2 | .   .   > | .   .   .   . | .   . |
    |       +---+               |       |
  1 | .   . | .   .   .   .   . | .   . |
    +-----------------------------------+
      1   2   3   4   5   6   7   8   9   AVE.
  • Primitívy (základné príkazy):

    • turnOn("world.kw")
    • movek()
    • turnLeft()
    • pickBeeper()
    • putBeeper()
    • turnOff()
  • Základná štruktúra programu:

#include <karel.h>

int main(){
    turnOn("world.kw");

    turnLeft();
    pickBeeper();

    turnOff();
}

Preklad a spustenie programu

  • Práve sme napísali zdrojový kód v jazyku C. Aby sme však "ochutnali" výsledok, musíme zo zdrojového kódu vytvoriť spustiteľný kód procesom prekladu (kompilácie)
  • Prekladač je nástroj, ktorý zo zdrojového kódu vytvorí objektový kód. Objektovému kódu rozumie samotný procesor a je možné ho už vykonať (spustiť)
  • Pre preklad budeme používať prekladač GNU C Compiler (gcc)
  • Program môžete prekladať aj použitím nástroja make. Predvolené správanie však funguje bez použitia extra prepínačov. Ak chcete dosiahnuť správne správanie, potrebujete nastaviť minimálne premenné prostredia alebo použiť predpripravený Makefile:
make karel
  • Program následne spustíte napísaním príkazu ./karel z príkazového riadku. Ak budete používať vývojové prostredie, budete mať možnosť spustiť výslednú aplikáciu priamo z neho
  • Bug - chyba v programe
    • In 1946, when Hopper was released from active duty, she joined the Harvard Faculty at the Computation Laboratory where she continued her work on the Mark II and Mark III. Operators traced an error in the Mark II to a moth trapped in a relay, coining the term bug. This bug was carefully removed and taped to the log book. Stemming from the first bug, today we call errors or glitch's [sic] in a program a bug.
    • zdroj: wikipedia: software bug

DRY

  • V programovaní existuje jeden princíp s názvom DRY - Don't Repeat Yourself. A aj keď je jeho význam možné aplikovať v rozličných oblastiach vývoja softvéru, dnes sa sústredíme na jeden z nich - na izoláciu opakujúcich sa častí kódu do funkcií.
  • Funkcie nám teda pomôžu v znovupoužiteľnosti našej časti programu v programe.
  • Funkcie už pritom dávno používame - akýkoľvek zápis v tvare name() ako napr. pickBeeper(), movek() je volaním funkcie. Dnes si ale ukážeme to, ako vytvárať vlastné funkcie.

Čo je to funkcia?

  • Čo je to teda funkcia?
    • Sequence of program instructions that perform a specific task, packaged as a unit
    • zdroj: wikipedia
  • Aby sme neostali nič dlžní ani pascalistom:
    • Jazyk Pascal rozpoznáva dva termíny: funkcie a procedúry. Funkcia je v ponímaní Pascal-u analógiou ku matematickej funkcii - po zavolaní a vykonaní svojej činnosti, vráti hodnotu (výsledok), napr.: cos(x), abs(x), ale aj scanf(). Procedúra naopak po svojom vykonaní žiadnu hodnotu nevráti, napr.: zmaž obrazovku alebo turnRight().

void

  • Jazyk C pozná iba termín funkcia, ale docieliť, aby funkcia nevrátila žiadnu hodnotu, je veľmi jednoduché: Ak nechceme, aby funkcia mala nejakú návratovú hodnotu, zapíšeme to v riadku jej deklarácie slovom void.
  • Vytvorme jednoduchú "procedúru" s názvom turnRight():
void turnRight(){
    turnLeft();
    turnLeft();
    turnLeft();
}

Definícia a deklarácia funkcie

  • Na mieste, kde chceme funkciu volať, už musí byť funkcia známa. Ak teda prekladač dôjde na miesto, kde sa má volať funkcia, o ktorej nič nevie, dôjde ku chybe aj napriek tomu, že sa definícia tejto funkcie nachádza v programe neskôr:
#include <karel.h>

// definicia funkcie
void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(400);
    turnLeft();
}

int main(){
    turnOn("stairs1.kw");

    setStepDelay(400);

    pickBeeper();
    turnLeft();
    movek();
    // volanie funkcie
    turnRight();
    movek();

    turnOff();
}
  • Spôsob, ktorým je možné sa tomuto problému vyhnúť okrem samotnej definície funkcie pred jej prvým použitím, je aj jej deklarácia pred prvým použitím. Tým prekladaču povieme, že táto funkcia bude zadefinovaná neskôr.
  • To isté musí platiť aj o volaní funkcie z inej funkcie - funkcia, ktorá volá inú funkciu, musí poznať v dobe jej volania aspoň jej deklaráciu.
  • Častý spôsob, ktorý sa používa je, že pred funkciou main() sa nachádza zoznam všetkých deklarácií funkcií, ktoré budú zadefinované v programe neskôr (za funkciou main()). Na poradí deklarovaných funkcií pritom nezáleží:
#include <karel.h>

// deklaracia
void turnRight();

int main(){
    turnOn("stairs1.kw");

    setStepDelay(400);

    pickBeeper();
    turnLeft();
    movek();
    // volanie funkcie
    turnRight();
    movek();

    turnOff();
}

// definicia funkcie
void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(400);
    turnLeft();
}

Sekvencia, vetvenie, cyklus

  • Ak píšeme algoritmus krok za krokom, hovoríme o sekvencii.
  • Avšak nie vždy je výhodné zapísať celý algorimus krok po kroku. Ak sa v programe potrebujeme rozhodnúť, t.j. rozdeliť ho na viac častí, hovoríme o vetvení. Programy vetvíme na základe rôznych podmienok.
  • Robot Karel sa v programoch môže rozhodovať podľa senzorov:

    • frontIsClear()
    • frontIsBlocked()
    • leftIsClear()
    • leftIsBlocked()
    • rightIsClear()
    • rightIsBlocked()
    • beepersPresent()
    • noBeepersPresent()
    • beepersInBag()
    • noBeepersInBag()
  • V jazyku C môžeme program vetviť pomocou podmienky if:

if( frontIsClear() ){
    movek();
    turnLeft();
}
  • Ak je podmienka splnená, vykonajú sa obidva príkazy (movek() aj turnLeft()). Ak podmienka nie je splnená, obidva príkazy sa preskočia a program pokračuje ďalej.
  • Avšak netreba zabúdať na ohraničenie tela cyklu. V tomto prípade ak je podmienka splnená, vykonajú sa síce obidva príkazy, no ak podmienka nie je splnená, preskočí sa iba prvý príkaz (funkcia) a turnLeft() sa vykoná, pretože už nie je súčasťou tela podmienky if:
if( frontIsClear() )
    movek();
    turnLeft();
  • Ak potrebujeme program rozdeliť do dvoch vetiev, k if pridáme vetvu else:
if( frontIsClear() ){
    movek();
}
else{
    turnLeft();
    turnLeft();
    turnLeft();
}
  • Opať si dajme pozor na ohraničenie príkazov

Iterácia

  • Opakovanie určitého procesu
  • Vyskytuje sa v cykloch, my si ukážeme cyklus while a do-while
  • Cyklus while nám umožňuje opakovať určitý proces, kým je podmienka splnená. Typické príklady pre robota Karla:
// chod na koniec ulice
while( frontIsClear() ){
    movek();
}

// pozbieraj vsetky znacky na danej pozicii
while( beepersPresent() ){
    pickBeeper();
}
  • Pri prvom nesplnení podmienky sa vykonávanie iterácií cyklu ukončí. Cyklus while má podmienku uvedenú na jeho začiatku, a teda je možné, že telo cyklu sa nevykoná ani raz.
  • Cyklus do-while nám tiež umožňuje opakovať určitý proces, kým je podmienka splnená. Avšak podmienku má uvedenú na konci, čo znamená, že telo cyklu sa vykoná minimálne raz. Príklad:
do{
    movek();
    if( beepersInBag() ){
        putBeeper();
    }
} while( frontIsClear() );

Vlastnosti algoritmov

  • Ďalej budeme riešiť rôzne úlohy pomocou robota Karla, pričom sa pokúsime zamerať na rôzne vlastnosti algoritmov.

Bludisko

  • Existuje veľa spôsobov, ako prejsť bludiskom. Jeden z nich je chytiť sa niektorej strany, napr. pravej, a tej sa držať počas celého prechodu bludiskom.
  • To sa dá naprogramovať rôznymi spôsobmi a tu je jeden z nich (maze(complete).c, maze1.kw):
#include <karel.h>
#define SPEED 100

void turnRight();

int main(){
    turnOn("maze1.kw");

    setStepDelay(SPEED);

    while( noBeepersPresent() ){
        if( rightIsClear() ){
            turnRight();
        }
        else if( leftIsClear() && frontIsBlocked() ){
            turnLeft();
        }
        else if( frontIsBlocked() ){
            turnLeft();
            turnLeft();
        }
        movek();
    }

    turnOff();

    return 0;
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Aby sme prešli celým svetom a nielen jednou jeho časťou, algoritmus musí byť úplný.
  • Ďalšou dôležitou vlastnosťou algoritmov je ich prehľadnosť. Preto si upravíme algoritmus nasledovne (maze(clear).c, maze1.kw):
#include <karel.h>
#define SPEED 100

void turnRight();
void turn();

int main(){
    turnOn("maze1.kw");

    setStepDelay(SPEED);

    while( noBeepersPresent() ){
        turn();
        movek();
    }

    turnOff();

    return 0;
}

void turn(){
    if( rightIsClear() ){
        turnRight();
    }
    else if( leftIsClear() && frontIsBlocked() ){
        turnLeft();
    }
    else if( frontIsBlocked() ){
        turnLeft();
        turnLeft();
    }
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Zavedením novej funkcie sme sprehľadnili kód, ktorý je teraz ľahšie čitateľný. Karel vie prejsť svetom a zastaví sa na značke po 97 krokoch. Avšak ak upravíme riešenie tak, aby sa Karel orientoval podľa ľavej ruky, riešenie je iba na 71 krokov (maze(effective_versatile).c, maze1.kw):
#include <karel.h>
#define SPEED 100

void turnRight();
void turn();

int main(){
    turnOn("maze1.kw");

    setStepDelay(SPEED);

    while( noBeepersPresent() ){
        turn();
        movek();
    }

    turnOff();

    return 0;
}

void turn(){
    if( leftIsClear() ){
        turnLeft();
    }
    else if( rightIsClear() && frontIsBlocked() ){
        turnRight();
    }
    else if( frontIsBlocked() ){
        turnLeft();
        turnLeft();
    }
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Takto upravený algoritmus prejde menej krokov, a preto je viac efektívny ako ten predchádzajúci. Navyše ak ho otestujeme na inej mape, napr. maze2.kw, algoritmus stále funguje, čo znamená, že algoritmus je univerzálny.
  • Pozrime sa však na takéto riešenie (maze_2(incorrect).c, maze2.kw):
#include <karel.h>
#define SPEED 100

void turnRight();
void turn();

int main(){
    turnOn("maze2.kw");

    setStepDelay(SPEED);

    while( noBeepersPresent() ){
        turn();
        movek();
        while( leftIsClear() ){
            turnLeft();
            movek();
        }
    }

    turnOff();

    return 0;
}

void turn(){
    while( leftIsClear() || frontIsBlocked() ){
        turnLeft();
    }
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Riešenie sa na našej mape zdá byť funkčné, avšak ak zmeníme umiestnenie značky na B 6 3 1 (z B 12 6 1), Karel sa na značke zastaví až pri treťom prechode touto značkou. Problém je v tom, že algoritmus nie je správny. V iterácii cyklu totiž môže vykonať hneď niekoľko krokov vo svete, no medzi týmito krokmi nezisťuje, či našiel značku. Preto program upravíme (maze_2(correct_versatile).c, maze2.kw):
#include <karel.h>
#define SPEED 100

void turnRight();
void turn();

int main(){
    turnOn("maze2.kw");

    setStepDelay(SPEED);

    while( noBeepersPresent() ){
        turn();
        movek();
        while( leftIsClear() && noBeepersPresent() ){
            turnLeft();
            movek();
        }
    }

    turnOff();

    return 0;
}

void turn(){
    while( leftIsClear() || frontIsBlocked() ){
        turnLeft();
    }
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Takto upravený algoritmus je správny a univerzálny. Často však v študentských riešeniach vidieť riešenie prostredníctvom nekonečného cyklu, ktorý sa zastaví len za určitých podmienok (maze_2(bad_practice).c, maze2.kw):
#include <karel.h>
#define SPEED 100

void turnRight();
void turn();

int main(){
    turnOn("maze2.kw");

    setStepDelay(SPEED);

    while( 1 ){
        turn();
        movek();
        while( leftIsClear() && noBeepersPresent() ){
            turnLeft();
            movek();
        }
        if( beepersPresent() ){
            break;
        }
    }

    turnOff();

    return 0;
}

void turn(){
    while( leftIsClear() || frontIsBlocked() ){
        turnLeft();
    }
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Pokiaľ to nie je nevyhnutné, takému riešeniu sa vyhýbame. Problémom je jeho konečnosť, ktorá nemusí byť vždy zaručená.
  • Ďalším typickým príkladom je postupný prechod svetom (harvest problem). Niektorí uprednostňujú prechod svetom po špirále, ale my si ukážeme postupný prechod svetom postupne po riadkoch (harvest.c, harvest.kw):
#include <karel.h>
#define SPEED 200

void turnRight();
void turnBack();
void runMile();

int main(){
    turnOn("harvest.kw");

    setStepDelay(SPEED);

    movek();
    while( beepersPresent() ){
        runMile();
        turnBack();
        movek();
        if( facingWest() ){
            turnRight();
            movek();
            turnLeft();
        }
        else{
            turnLeft();
            movek();
            turnRight();
        }
    }

    turnOff();

    return 0;
}

void runMile(){
    while( beepersPresent() ){
        movek();
    }
}

void turnBack(){
    setStepDelay(0);
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Vďaka podmienke if je algoritmus funkčný nielen na párnom, ale aj na nepárnom počte riadkov a zastaví sa na začiatku prázdneho riadku. Avšak opäť je možné algoritmus ešte viac sprehľadniť (harvest(clear).c, harvest.kw):
#include <karel.h>
#define SPEED 200

void turnRight();
void turnBack();
void runMile();
void up();

int main(){
    turnOn("harvest.kw");

    setStepDelay(SPEED);

    movek();
    while( beepersPresent() ){
        runMile();
        turnBack();
        movek();
        up();
    }

    turnOff();

    return 0;
}

void up(){
    if( facingWest() ){
        turnRight();
        movek();
        turnLeft();
    }
    else{
        turnLeft();
        movek();
        turnRight();
    }
}

void runMile(){
    while( beepersPresent() ){
        movek();
    }
}

void turnBack(){
    setStepDelay(0);
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}

void turnRight(){
    setStepDelay(0);
    turnLeft();
    turnLeft();
    setStepDelay(SPEED);
    turnLeft();
}
  • Medzi ďalšie vlastnosti algoritmov patrí rezultatívnosť, t.j. algoritmus má výsledok (Karel vyrieši problém, algoritmus vypočíta hodnotu), a deterministickosť, t.j. v každom momente vieme jednoznačne povedať, čo bude v programe nasledovať.

Doplňujúce zdroje

  1. Herout: Učebnica jazyka C
  2. Kernighan, Ritchie: Programovací jazyk C
  3. Pattis: Karel The Robot: A Gentle Introduction to the Art of Programming, 2nd Edition

Video