4. týždeň

Super Karel rocks on

Pokročilé algoritmické problémy

O čom je lab

Na tomto cvičení budete ďalej pracovať s robotom Karlom. Vytvoríte zložitejšie programy, pomocou ktorých budete riešiť pokročilé algoritmické problémy robota Karla.

Ciele

  1. Rutinne riadiť robota Karla prostredníctvom všetkých príkazov a senzorov.
  2. Rutinne používať vlastné funkcie, dvojcestné vetvenie a logické cykly.
  3. Osvojiť si prácu s pokročilými algoritmickými problémami.

Postup

Krok 1: Setup

Úloha 1.1

Vytvorte adresár ~/labs/lab04 a skopírujte súbor potrebný k prekladu programu s robotom Karlom: Makefile.

Poznámka

Súbor Makefile nájdete v adresároch z minulých cvičení ~/labs/lab02 alebo ~/labs/lab03, a je potrebné ho skopírovať do adresára ~/labs/lab04.

Krok 2: Collector

V tomto programe bude Karel zbierať značky vo svete.

Úloha 2.1

Vytvorte program collector, v ktorom bude Karel prechádzať postupne celým svetom a zbierať všetky značky, ktoré nájde. Vaše riešenie otestujte na svete collector.kw.

Počiatočná situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST       0         3
ST.+---------------+
 5 | 2   .   2   . |
   |               |
 4 | .   .   .   3 |
   |               |
 3 | .   1   .   . |
   |               |
 2 | .   .   2   3 |
   |               |
 1 | >   .   2   . |
   +---------------+
     1   2   3   4   AVE.

Koncová situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (4, 5)   NORTH     18         0
ST.+---------------+
 5 | .   .   .   ^ |
   |               |
 4 | .   .   .   . |
   |               |
 3 | .   .   .   . |
   |               |
 2 | .   .   .   . |
   |               |
 1 | .   .   .   . |
   +---------------+
     1   2   3   4   AVE.

Úloha 2.2

Upravte program collector tak, aby Karel najskôr našiel ľavý dolný roh sveta a až potom vyzbieral všetky značky. Vaše riešenie otestujte na svete collector2.kw.

Krok 3: Multiplier

V tomto programe bude Karel zvojnásobovať značky vo svete.

Úloha 3.1

Vytvorte program multiplier, v ktorom bude Karel prechádzať postupne celým svetom a zdvojnásobovať počet značiek, ktoré nájde. Samozrejme, bez použitia premenných. Vaše riešenie otestujte na svete multiplier.kw.

Počiatočná situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      99         0
ST.+-------------------+
 5 | .   4   .   .   . |
   |                   |
 4 | 4   .   .   .   . |
   |                   |
 3 | .   3   .   .   1 |
   |                   |
 2 | .   .   .   .   . |
   |                   |
 1 | >   1   .   2   . |
   +-------------------+
     1   2   3   4   5   AVE.

Koncová situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 1)   EAST      84         0
ST.+-------------------+
 5 | .   8   .   .   . |
   |                   |
 4 | 8   .   .   .   . |
   |                   |
 3 | .   6   .   .   2 |
   |                   |
 2 | .   .   .   .   . |
   |                   |
 1 | >   2   .   4   . |
   +-------------------+
     1   2   3   4   5   AVE.

Doplňujúce úlohy

Úloha A.1

Vytvorte program highway, pomocou ktorého Karel prejde cestu na jej koniec (z východu na západ) a vyplní všetky diery, ktorých hĺbka môže byť rôzna. Vyplnené majú byť len tie diery alebo miesta v dierach, ktoré ešte nie sú vyplnené. Vaše riešenie otestujte na mape highway.kw.

Počiatočná situácia

 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.

Koncová situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (9, 4)   EAST      90         0
ST.+-----------------------------------+
 6 | .   .   .   .   .   .   .   .   . |
   |                                   |
 5 | .   .   .   .   .   .   .   .   . |
   |                                   |
 4 | .   .   .   .   .   .   .   .   > |
   |   +   +---+   +   +---+   +   +---|
 3 | 1 | 1 | . | 1 | 1 | . | 1 | 1 | . |
   |   |   |   +---+   |   |   |   |   |
 2 | 1 | 1 | .   . | 1 | . | 1 | 1 | . |
   |   +---+       |   |   +---+   |   |
 1 | 1 | .   .   . | 1 | .   . | 1 | . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Úloha A.2

Upravte program highway tak, aby nezáležalo, na ktorom konci cesty sa Karel na začiatku programu nachádza. Karel je na začiatku otočený smerom na otvorenú cestu. Karel teda bude prechádzať z východu na západ alebo zo západu na východ. Svoje riešenie tejto úlohy môžete otestovať na mape highway2.kw.

Počiatočná situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (8, 4)    WEST      99         0
ST.+-------------------------------+
 4 | .   .   .   .   .   .   .   < |
   |   +   +---+   +---+   +-------|
 3 | . | 1 | . | . | . | 1 | .   . |
   |   +---+   |   |   |   |       |
 2 | . | .   . | . | . | . | .   . |
   |   |       +---+   |   |       |
 1 | 1 | .   .   .   . | . | .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8  AVE.

Koncová situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 4)    WEST      93         0
ST.+-------------------------------+
 4 | <   .   .   .   .   .   .   . |
   |   +   +---+   +---+   +-------|
 3 | 1 | 1 | . | 1 | . | 1 | .   . |
   |   +---+   |   |   |   |       |
 2 | 1 | .   . | 1 | . | 1 | .   . |
   |   |       +---+   |   |       |
 1 | 1 | .   .   .   . | 1 | .   . |
   +-------------------------------+
     1   2   3   4   5   6   7   8  AVE.

Úloha A.3

Karel sa ocitol vo svete, ktorý je hore nohami. Otestujte program highway na svete, ktorý je otočený hore nohami a v prípade potreby ho upravte. Mapy: highway3.kw, highway4.kw.

Počiatočná situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (1, 3)   EAST      99         0
ST.+-----------------------------------+
 6 | . | .   .   . | . | .   . | . | . |
   |   +---+       |   |   +---+   |   |
 5 | . | 1 | .   . | 1 | . | 1 | . | . |
   |   |   |   +---+   |   |   |   |   |
 4 | . | 1 | . | . | . | . | . | 1 | . |
   |       +---+       +---+       +---|
 3 | >   .   .   .   .   .   .   .   . |
   |                                   |
 2 | .   .   .   .   .   .   .   .   . |
   |                                   |
 1 | .   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Koncová situácia

 CORNER  FACING  BEEP-BAG  BEEP-CORNER
 (9, 3)   EAST      90         0
ST.+-----------------------------------+
 6 | 1 | .   .   . | 1 | .   . | 1 | . |
   |   +---+       |   |   +---+   |   |
 5 | 1 | 1 | .   . | 1 | . | 1 | 1 | . |
   |   |   |   +---+   |   |   |   |   |
 4 | 1 | 1 | . | 1 | 1 | . | 1 | 1 | . |
   |       +---+       +---+       +---|
 3 | .   .   .   .   .   .   .   .   > |
   |                                   |
 2 | .   .   .   .   .   .   .   .   . |
   |                                   |
 1 | .   .   .   .   .   .   .   .   . |
   +-----------------------------------+
     1   2   3   4   5   6   7   8   9   AVE.

Doplňujúce zdroje

  1. Karel Language Reference
  2. Tu nájdete knižnicu robota Karla, vrátane návodu na inštaláciu knižnice.
  3. Rudolf Pecinovský: Základy algoritmizace - kapitola 10
  4. Pavel Herout: Učebnice jazyka C (1. díl) - kapitola 5.1, 5.4, 5.5
  5. Hlavičkový súbor robota Karla karel.h
  6. Hlavičkový súbor super robota Karla superkarel.h
  7. Súbor pre preklad Karlovho programu Makefile
  8. Súbor pre preklad super Karlovho programu Makefile-superkarel
  9. GNU Make Tutorial
  10. Náš VIM tutoriál
  11. ViM Quick Reference Card (.pdf)
  12. Tomášov konfigurák pre ViM
  13. Danielov konfigurák pre ViM

Video