Vetvenie, cyklus a metóda návrhu algoritmov zhora-nadol.

Ciele
  1. Precvičiť si vetvenie toku programu na základe podmienok v programovacom jazyku C.
  2. Naučiť sa používať logické cykly v programovacom jazyku C.
  3. Osvojiť si návrh riešenia algoritmu pomocou techniky zhora-nadol.
Úvod
    Na tomto cvičení si opäť precvičíte rozhodovanie v Karlových programoch na základe senzorov, ktoré obsahuje. Úlohou tohto cvičenia je naučiť sa vytvárať jednoduché cykly a s ich pomocou efektívne vyriešiť problém. Zároveň si precvičíte rozdelenie väčšieho problému na niekoľko menších a tieto potom budete 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
  1. Karlove prípravy na RobOlympiádu vrcholia. V tomto kroku pomôžete Karlovi dotiahnuť prípravy a naučiť ho zdolať v rámci prekážkového behu prekážky ľubovoľne od seba vzdialené aj ľubovoľne vysoké prekážky. Na začiatku každého behu sa Karel vždy bude nachádzať na pozícii [1,1]. Karlov beh sa opäť zastaví vtedy, keď vo svojom behu nájde značku.
    Úloha: Otvorte si riešenie olympics z minulého cvičenia.
    Úloha: Upravte program tak, aby Karel zvládol prebehnúť ľubovoľne vysoké prekážky. Karel svoj beh zastaví vtedy, keď vo svojej trati natrafí na značku, pričom značka sa bude v Karlovej ceste vždy nachádzať. Svoje riešenie tejto úlohy si môžete otestovať na nasledujúcich mapách, ktoré predstavujú predkolá veľkého finále RobOlympiády: olympics3.kw, olympics4.kw.
    Úloha: Upravte program tak, aby robot Karel vedel preskočiť aj ľubovoľne široké prekážky. Karel svoj beh zastaví vtedy, keď vo svojej trati natrafí na značku, pričom značka sa bude v Karlovej ceste vždy nachádzať. Svoje riešenie tejto úlohy si môžete otestovať na nasledujúcich mapách, ktoré predstavujú posledné kolá veľkého finále RobOlympiády: olympics5.kw, olympics6.kw.
  2. Nasledujúcu úlohu riešte dôsledne metodológiou zhora nadol. Najskôr navrhnite hrubý algoritmus, ktorý používa aj nateraz neznáme riešenia (napr. skopírovanie značiek na susednú pozíciu) a až potom riešte identifikované podúlohy.
    Úloha: Naučiť Karola postaviť 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).
    Úloha: Navrhnite hrubý algoritmus riešenia. Aké čiastkové úlohy ste identifikovali pre prvú a druhú úroveň abstrakcie? Čo je podmienka ukončenia?
    Zobraziť výsledok
    Úloha: Navrhnutý hrubý algoritmus implementujte ako funkciu main() v novom implementačnom súbore stairsBuilder.c.
    Úloha: Pre každú identifikovanú čiastkovú úlohu vytvorte samostatnú funkciu a vložte ju do súboru stairsBuilder.c.
    Poznámka: Nezabudnite za riadok #include <karel.h> vložiť deklarácie navrhnutých funkcií.
    Úloha: Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairsbuilder1.kw a stairsbuilder2.kw.
Doplňujúce úlohy
    Úloha: 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ý. Zároveň môžete predpokladať, že najbližšie miesto na sever nad každým miestom so značkami je prázdne. Overte svoje riešenie na nasledujúcich mapách: multiplier1.kw a multiplier2.kw.
Doplňujúce zdroje
  1. Rudolf Pecinovský: Základy algoritmizace - kapitola 10 (úvod), 10.2, 10.3, 11 (celá kapitola)
  2. Pavel Herout: Učebnice jazyka C (1. díl) - kapitoly 5.1, 5.4 a 5.5
comments powered by Disqus