info  01  02  03  04  05  06  07 

Karel Solves Daily Problems

Ciele

  1. Osvojiť si návrh riešenia algoritmu pomocou techniky zhora-nadol.

Úvod

Úlohou tohto cvičenia je naučiť sa rozdeliť väčší problém na niekoľko menších a tieto potom postupne riešiť. Precvičíte si teda analýzu problému, jeho rozdelenie na menšie časti, návrh algoritmu a nakoniec celý problém naprogramujete.

Postup

Krok č. 1

Vytvorte pre robota Karla program, pomocou ktorého bude Karel vedieť zdvojnásobiť počet značiek, ktoré cestou nájde. Karel vždy začne na pozícii [1,1] a prejde celým svetom, pričom zdvojnásobí každú žnačku, ktorú nájde. Počet značiek, ktoré má Karel k dispozícii na riešenie tejto úlohy, je dostatočný.

Úloha 1.1:

Vytvorte analýzu uvedeného problému. Pokúste sa celý problém rozdeliť na čo najmenšie funkčné celky (funkcie).

Úloha 1.2:

Na základe analýzy vytvorte požadované funkcie, pomocou ktorých úlohu vyriešite.
Overte svoje riešenie na nasledujúcich mapách: multiplier1.kw, multiplier2.kw.
Počiatočná situácia:
Koncová situácia:

Krok č. 2

Robot Karel sa opäť vydal hľadať poklad. Tentokrát je jeho mapa plná značiek, ktoré mu napovedajú, ktorým smerom má ísť. Karel vždy začína na prázdnej pozícii a kráča rovno dovtedy, kým nenájde nejakú značku.

Úloha 2.1:

Naprogramujte robota Karla tak, aby našiel poklad, ak pre mapu sveta platí:
  • 1 značka znamená, ža Karel musí ísť na sever,
  • 2 značky znamenajú, že Karel musí ísť na západ,
  • 3 značky znamenajú, že Karel musí ísť na juh,
  • 4 značky znamenajú, že Karel musí ísť na východ,
  • 5 značiek znamená, že Karel našiel poklad.
  • Karel hľadá poklad, kým ho nenájde.
Poznámka:  Podstatou tejto úlohy je precvičiť si algoritmické myslenie. Daný problém by ste preto nemali riešiť pomocou premenných (ak premenné už poznáte).

Riešenie úlohy si môžete overiť na nasledujúcich mapách: treasuremap1.kw a treasuremap2.kw.

Počiatočná situácia:
Koncová situácia:

Doplňujúce úlohy

  1. Vytvorte pre Karla príkaz stairs(), pomocou ktorého Karel postaví zo značiek schodisko. Na začiatku sa pred Karlom nachádza stĺpik postavený zo značiek, ktorých počet je väčší ako 1. Úlohou Karla je postaviť vpravo od tohto stĺpika schody reprezentované z ďalších značiek, pričom na každej pozícii bude vždy o jednu značku menej ako na predchádzajúcej. Karel má na začiatku dostatočný počet značiek, aby túto úlohu úspešne zvládol a vpravo od stĺpika je vždy dostatok miesta pre vytvorenie schodiska. Po vytvorení schodiska sa Karel bude nachádzať na jeho najvyššom stupni.
    Poznámka:  Podstatou tejto úlohy je precvičiť si algoritmické myslenie. Daný problém by ste preto nemali riešiť pomocou premenných (ak premenné už poznáte).
    Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairsbuilder1.kw a stairsbuilder2.kw.
    Počiatočná situácia:
    Koncová situácia:
  2. Vašou úlohou je upraviť riešenie programu z druhej doplňujúcej úlohy prvého cvičenia tak, aby poradie každého poschodia bolo označené odpovedajúcim počtom značiek. Karel vždy začína na prízemí a končí na najvyššom poschodí. Pôvodné riešenie nájdete v súbore stairs2.c

    Pôvodný program by ste mali upraviť tak, aby Karel očísloval schodisko s ľubovoľným počtom poschodí a zároveň tak, aby číslovanie schodiska bolo správne bez ohľadu na pôvodný počet značiek na každom poschodí.

    Poznámka:  Podstatou tejto úlohy je precvičiť si algoritmické myslenie. Daný problém by ste preto nemali riešiť pomocou premenných (ak premenné už poznáte).
    Poznámka:  Pri riešení tejto úlohy je výhodné použiť rekurziu.
    Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairs1.kw a stairs2.kw.
    Počiatočná situácia:
    Koncová situácia:
  3. Upravte predchádzajúci program tak, aby Karlovi nezáležalo na výške jednotlivých schodov. Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairs3.kw a stairs4.kw.
    Počiatočná situácia:
    Koncová situácia:
  4. V spodnej rade Karlovho sveta sú ľubovoľne rozložené značky. Karel stojí na začiatku tejto rady (je doma). Vytvorte v rade nad ňou jej zrkadlový obraz. Napr. ak bude v pôvodnej rade značka (alebo značky) na ľavej krajnej pozícii, vo výslednej rade bude (budú) na pravej krajnej pozícii. Platí, že v spodnej rade Karlovho sveta sa na každej pozícii nachádza aspoň jedna značka. Riešenie úlohy si môžete overiť na mapách mirror1.kw a mirror2.kw.
    Počiatočná situácia:
    Koncová situácia:
    Poznámka:  Podstatou tejto úlohy je precvičiť si algoritmické myslenie. Daný problém by ste preto nemali riešiť pomocou premenných (ak premenné už poznáte).
  5. Upravte predchádzajúci program tak, aby v spodnej rade Karlovho sveta zostali pôvodne rozložené značky. Zároveň platí, že Karel má v batohu dostatočné množstvo značiek. Riešenie úlohy si môžete overiť na mapách mirror3.kw a mirror4.kw.
  6. Upravte program so šachovnicou tak, aby nezáležalo na rozmeroch sveta (párnosť resp. nepárnosť políčok). Riešenie úlohy si môžete overiť na mapách empty6.kw, empty7.kw a empty8.kw.
    Poznámka:  Podstatou tejto úlohy je precvičiť si algoritmické myslenie. Daný problém by ste preto nemali riešiť pomocou premenných (ak premenné už poznáte).
  7. Prejdite na stránku http://kplab.tuke.sk/opravma. Na základe svojho loginu si nechajte vygenerovať zdrojový kód a opravte v ňom všetky chyby, ktoré bránia tomu, aby bol výsledný kód úspešne preložený.
  8. Pokúste sa upraviť úlohu o nájdení stredu sveta s použitím premenných. Porovnajte náročnosť a zložitosť riešenia úlohy s použitím a bez použitia premenných.
    Poznámka:  Riešenie tejto úlohy je vhodné pre prípravu na nasledujúce cvičenie.
$Id$
© Copyright 2010-2012 KPI FEI TUKE Materiály pripravili: Miroslav Biňas, Emília Pietriková, Marek Paralič Na kofole s nami bol: Janči Švec ;)