2. týždeň

Algorithm Properties

Super Karel, vetvenie (if, if/else), iterácia a cyklus (while, do-while), maze & harvest problem

Video (01.10.2024)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Vlastnosti algoritmov

  • Na tejto prednáške budeme riešiť rôzne úlohy pomocou robota Karla, pričom sa pokúsime zamerať na rôzne vlastnosti algoritmov.

Super Karel

  • V nasledujúcich úlohách sa z Karla sa stane Super Karel použitím superkarel.h.
  • K prekladu bude potrebné zmeniť prepínač -lkarel na -lsuperkarel.

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.
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      10         0
ST.+-----------------------+
 6 | .   .   .   .   . | 1 |
   |----   |   |   +---+   |
 5 | .   . | . | . | .   . |
   |   +---+   |   |   +---|
 4 | . | .   . | . | . | . |
   |   |   ----+---+   |   |
 3 | . | .   .   . | .   . |
   |   +---+----   +---+   |
 2 | .   . | .   .   . | . |
   |   +---+   ----+   |   |
 1 | > | .   .   . | .   . |
   +-----------------------+
     1   2   3   4   5   6   AVE.

#include <superkarel.h>
#define SPEED 100

void turn_right();

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

    set_step_delay(SPEED);

    while (no_beepers_present()) {
        if (right_is_clear()) {
            turn_right();
        }
        else if (left_is_clear() && front_is_blocked()) {
            turn_left();
        }
        else if (front_is_blocked()) {
            turn_left();
            turn_left();
        }
        step();
    }

    turn_off();

    return 0;
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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 <superkarel.h>
#define SPEED 100

void turn_right();
void turn();

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

    set_step_delay(SPEED);

    while (no_beepers_present()) {
        turn();
        step();
    }

    turn_off();

    return 0;
}

void turn() {
    if (right_is_clear()) {
        turn_right();
    }
    else if (left_is_clear() && front_is_blocked()) {
        turn_left();
    }
    else if (front_is_blocked()) {
        turn_left();
        turn_left();
    }
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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 <superkarel.h>
#define SPEED 100

void turn_right();
void turn();

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

    set_step_delay(SPEED);

    while (no_beepers_present()) {
        turn();
        step();
    }

    turn_off();

    return 0;
}

void turn() {
    if (left_is_clear()) {
        turn_left();
    }
    else if (right_is_clear() && front_is_blocked()) {
        turn_right();
    }
    else if (front_is_blocked()) {
        turn_left();
        turn_left();
    }
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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.
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST       0         0
ST.+-----------------------------------------------+
 6 | .   .   .   .   . | . | . | .   .   .   .   . |
   |----   |   |   +---+   |   +---+   |   |   ----|
 5 | .   . | . | . | .   .   .   . | . | . | .   . |
   |   +---+   |   |   +---+---+   |   |   +---+   |
 4 | . | .   . | . | . | . | . | . | . | .   . | . |
   |   |   ----+---+   |   |   |   +---+----   |   |
 3 | . | .   .   . | .   1 | .   . | .   .   . | . |
   |   +---+----   +---+   |   +---+   ----+---+   |
 2 | .   . | .   .   . | . | . | .   .   . | .   . |
   |   +---+   ----+   |   |   |   +----   +---+   |
 1 | > | .   .   . | .   . | .   . | .   .   . | . |
   +-----------------------------------------------+
     1   2   3   4   5   6   7   8   9   10  11  12  AVE.

#include <superkarel.h>
#define SPEED 100

void turn_right();
void turn();

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

    set_step_delay(SPEED);

    while (no_beepers_present()) {
        turn();
        step();
        while (left_is_clear()) {
            turn_left();
            step();
        }
    }

    turn_off();

    return 0;
}

void turn() {
    while (left_is_clear() || front_is_blocked()) {
        turn_left();
    }
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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 <superkarel.h>
#define SPEED 100

void turn_right();
void turn();

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

    set_step_delay(SPEED);

    while (no_beepers_present()) {
        turn();
        step();
        while (left_is_clear() && no_beepers_present()) {
            turn_left();
            step();
        }
    }

    turn_off();

    return 0;
}

void turn() {
    while (left_is_clear() || front_is_blocked()) {
        turn_left();
    }
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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 <superkarel.h>
#define SPEED 100

void turn_right();
void turn();

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

    set_step_delay(SPEED);

    while (1) {
        turn();
        step();
        while (left_is_clear() && no_beepers_present()) {
            turn_left();
            step();
        }
        if (beepers_present()) {
            break;
        }
    }

    turn_off();

    return 0;
}

void turn() {
    while (left_is_clear() || front_is_blocked()) {
        turn_left();
    }
}

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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á.
  • Avšak v prípade bludiska nemáme vždy zaručenú konečnosť, ak je samotné bludisko cyklické. Pozrime sa na mapu sveta maze4.kw:
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 3)   NORTH      0         0
ST.+-------------------+
 5 | .   .   .   .   . |
   |   +---+   +---+   |
 4 | ^ | . | 1 | . | . |
   |   |   +---+   |   |
 3 | . | .   .   . | . |
   |   |           |   |
 2 | . | .   .   . | . |
   |   +-----------+   |
 1 | .   .   .   .   . |
   +-------------------+
     1   2   3   4   5   AVE.
  • Ak sa držíme ľavej steny, program sa zacyklí a robot Karel nenájde značku. Ak program upravíme tak, aby sa robot opäť držal pravej steny, značku síce nájde, ale po zmene mapy sveta sa opäť zacyklí - ak na začiatku robot smeruje na juh. V tomto prípade sa musíme spoliehať na mapu sveta, že problém na nej je riešiteľný.
  • Ďalším typickým príkladom je postupný prechod svetom (harvest problem).
 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (2, 3)   EAST      10         0
ST.+-------------------------------+
 8 | .   .   .   .   .   .   .   . |
   |                               |
 7 | .   .   .   .   .   .   .   . |
   |                               |
 6 | .   .   1   1   1   1   .   . |
   |                               |
 5 | .   .   1   1   1   1   .   . |
   |                               |
 4 | .   .   1   1   1   1   .   . |
   |                               |
 3 | .   >   1   1   1   1   .   . |
   |                               |
 2 | .   .   .   .   .   .   .   . |
   |                               |
 1 | .   .   .   .   .   .   .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8   AVE.
  • Niektorí uprednostňujú prechod po špirále, ale my si ukážeme postupný prechod po riadkoch (harvest.c, harvest.kw):
#include <superkarel.h>
#define SPEED 200

void turn_right();
void turn_back();
void run_mile();

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

    set_step_delay(SPEED);

    step();
    while (beepers_present()) {
        run_mile();
        turn_back();
        step();
        if (facing_west()) {
            turn_right();
            step();
            turn_left();
        }
        else {
            turn_left();
            step();
            turn_right();
        }
    }

    turn_off();

    return 0;
}

void run_mile() {
    while (beepers_present()) {
        step();
    }
}

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

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • 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 <superkarel.h>
#define SPEED 200

void turn_right();
void turn_back();
void run_mile();
void up();

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

    set_step_delay(SPEED);

    step();
    while (beepers_present()) {
        run_mile();
        turn_back();
        step();
        up();
    }

    turn_off();

    return 0;
}

void up() {
    if (facing_west()) {
        turn_right();
        step();
        turn_left();
    }
    else {
        turn_left();
        step();
        turn_right();
    }
}

void run_mile() {
    while (beepers_present()) {
        step();
    }
}

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

void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(SPEED);
    turn_left();
}
  • Uvažujme o modifikácii, kde by robot Karel postupne prešiel celým svetom. Začiatok jeho cesty nech je na súradnici (1,1). Keďže povaha úlohy sa zmenila, najskôr zmeníme funkciu run_mile() tak, aby Karel nepozeral na značky, ale na hranice sveta:
void run_mile() {
    while (front_is_clear()) {
        step();
    }
}
  • Aby sa robot premiestnil na súradnicu (1,1), naprogramujeme si novú funkciu find_south_west(), pomocou ktorej sa robot najskôr otočí smerom na západ bez ohľadu na to, kam smeruje na začiatku programu. Následne sa premiestni k západnej hranici sveta, otočí sa na juh a opäľ sa premiestni k južnej hranici sveta. Napokon sa otočí na východ v smere cesty:
void find_south_west();

// main() goes here

void find_south_west() {
    while (not_facing_west()) {
        turn_left();
    }
    run_mile();
    turn_left();
    run_mile();
    turn_left();
}
  • Ďalšia modifikácia sa bude týkať funkcie up(). Je potrebné zohľadniť spôsob otočenia do nového riadku, ale aj fakt, že pri prechode na vyšší riadok môže robot natrafiť na hranice sveta:
void up() {
    if (facing_west()) { // turn to north
        turn_right();
    }
    else {
        turn_left();
    }
    if (front_is_clear()) {      // if possible,
        step();                  // move to upper line
        if (left_is_blocked()) { // and turn to the line
            turn_right();
        }
        else {
            turn_left();
        }
    }
}
  • Posledná modifikácia sa bude dotýkať hlavnej funkcie programu. Robot Karel sa najskôr premiestni na začiatok sveta. Dôležitý je aj hlavný cyklus programu. Tentokrát sa nepohybujeme podľa značiek, ale podľa hraníc sveta:
int main() {
    turn_on("harvest.kw");

    set_step_delay(SPEED);

    find_south_west();
    while (front_is_clear()) {
        run_mile();
        up();
    }

    turn_off();

    return 0;
}
  • Celý program sa nachádza v súbore harvest2.c.
  • Uvažujme o ďalšej modifikácii programu. Chceme, aby robot Karel pozbieral značky, ktoré cestou nájde, a aby ich všetky vyložil von z batohu na jeho koncovej pozícii.
  • V programe nastanú dve modifikácie: Zbieranie značiek v rámci funkcie run_mile() a vyloženie všetkých značiek na konci programu (harvest3.c):
int main() {
    turn_on("harvest.kw");

    set_step_delay(SPEED);

    find_south_west();
    while (front_is_clear()) {
        run_mile();
        up();
    }
    while (beepers_in_bag()) {
        put_beeper();
    }

    turn_off();

    return 0;
}

void run_mile() {
    while (front_is_clear()) {
        step();
        if (beepers_present()) {
            pick_beeper(); // collect beepers on your way
        }
    }
}
  • Na záver si ešte spomenieme ďalšie dve vlastnosti algoritmov - 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