Ciele
- 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
Ú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:
0
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 1) EAST 99 0
ST.+-------------------+
5 | . 4 . . . |
| |
4 | . . . . . |
| |
3 | 4 3 . . 1 |
| |
2 | . . . . . |
| |
1 | > . 1 2 . |
+-------------------+
1 2 3 4 5 AVE.
Koncová situácia:
86
CORNER FACING BEEP-BAG BEEP-CORNER
(5, 5) NORTH 84 0
ST.+-------------------+
5 | . 8 . . ^ |
| |
4 | . . . . . |
| |
3 | 8 6 . . 2 |
| |
2 | . . . . . |
| |
1 | . . 2 4 . |
+-------------------+
1 2 3 4 5 AVE.
Krok č. 2
Ú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.
Riešenie úlohy si môžete overiť na nasledujúcich mapách: treasuremap1.kw a treasuremap2.kw.
Počiatočná situácia:
0
CORNER FACING BEEP-BAG BEEP-CORNER
(2, 2) NORTH 0 0
ST.+---------------------------------------+
8 | . . . . . . . . . . |
| |
7 | . 4 . . . 3 . . . . |
| |
6 | . . . . . . . . . . |
| |
5 | . . . . . . . . . . |
| |
4 | . . . 5 . . . . 2 . |
| |
3 | . . . . . . . . . . |
| |
2 | . ^ . . . 4 . . 1 . |
| |
1 | . . . . . . . . . . |
+---------------------------------------+
1 2 3 4 5 6 7 8 9 10 AVE.
Koncová situácia:
70
CORNER FACING BEEP-BAG BEEP-CORNER
(4, 4) NORTH 0 0
ST.+---------------------------------------+
8 | . . . . . . . . . . |
| |
7 | . > > > > v . . . . |
| |
6 | . ^ . . . v . . . . |
| |
5 | . ^ . . . v . . . . |
| |
4 | . ^ . > < < < < < . |
| |
3 | . ^ . . . v . . ^ . |
| |
2 | . ^ . . . > > > ^ . |
| |
1 | . . . . . . . . . . |
+---------------------------------------+
1 2 3 4 5 6 7 8 9 10 AVE.
Doplňujúce úlohy
-
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.
Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairsbuilder1.kw a stairsbuilder2.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).Počiatočná situácia:0 CORNER FACING BEEP-BAG BEEP-CORNER (1, 3) NORTH 99 0 ST.+---------------------------+ 6 | . . . . . . . | | | 5 | . . . . . . . | | | 4 | 5 . . . . . . | | | 3 | ^ . . . . . . | | | 2 | . . . . . . . | | | 1 | . . . . . . . | +---------------------------+ 1 2 3 4 5 6 7 AVE.Koncová situácia:36 CORNER FACING BEEP-BAG BEEP-CORNER (1, 4) WEST 89 5 ST.+---------------------------+ 6 | . . . . . . . | | | 5 | . . . . . . . | | | 4 | < 4 3 2 1 . . | | | 3 | . . . . . . . | | | 2 | . . . . . . . | | | 1 | . . . . . . . | +---------------------------+ 1 2 3 4 5 6 7 AVE. -
Vašou úlohou je upraviť riešenie stairs 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ý 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).Riešenie úlohy si môžete overiť na nasledujúcich mapách: stairs1.kw a stairs2.kw.Poznámka:
Pri riešení tejto úlohy je výhodné použiť rekurziu.Počiatočná situácia:0 CORNER FACING BEEP-BAG BEEP-CORNER (1, 1) EAST 90 0 ST.+-----------------------------------+ 6 | . . . . . . . . . | | | 5 | . . . . . . . . . | | +---+ | 4 | . . . . . | . | . . . | | +---+ | | 3 | . . . . | . . | . . . | | +---+ | | 2 | . . . | . . . | . . . | | +---+ | | 1 | > . | . . . . | . . . | +-----------------------------------+ 1 2 3 4 5 6 7 8 9 AVE.Koncová situácia:167 CORNER FACING BEEP-BAG BEEP-CORNER (6, 5) EAST 80 4 ST.+-----------------------------------+ 6 | . . . . . . . . . | | | 5 | . . . . . > . . . | | +---+ | 4 | . . . . 3 | . | . . . | | +---+ | | 3 | . . . 2 | . . | . . . | | +---+ | | 2 | . . 1 | . . . | . . . | | +---+ | | 1 | . . | . . . . | . . . | +-----------------------------------+ 1 2 3 4 5 6 7 8 9 AVE. -
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:
0 CORNER FACING BEEP-BAG BEEP-CORNER (1, 1) EAST 90 0 ST.+-----------------------------------+ 9 | . . . . . . . . . | | | 8 | . . . . . . . . . | | +---+ | 7 | . . . . . . | . | . . | | | | | 6 | . . . . . . | . | . . | | +---+ | | 5 | . . . . 1 | . . | . . | | +---+ | | 4 | . . . . | . . . | . . | | | | | 3 | . . . . | . . . | . . | | +---+ | | 2 | . . 1 | . . . . | . . | | +---+ | | 1 | > . | . . . . . | . . | +-----------------------------------+ 1 2 3 4 5 6 7 8 9 AVE.Koncová situácia:266 CORNER FACING BEEP-BAG BEEP-CORNER (7, 8) EAST 77 5 ST.+-----------------------------------+ 9 | . . . . . . . . . | | | 8 | . . . . . . > . . | | +---+ | 7 | . . . . . . | . | . . | | | | | 6 | . . . . . 4 | . | . . | | +---+ | | 5 | . . . . 3 | . . | . . | | +---+ | | 4 | . . . . | . . . | . . | | | | | 3 | . . . 2 | . . . | . . | | +---+ | | 2 | . . 1 | . . . . | . . | | +---+ | | 1 | . . | . . . . . | . . | +-----------------------------------+ 1 2 3 4 5 6 7 8 9 AVE. -
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:
0 CORNER FACING BEEP-BAG BEEP-CORNER (1, 1) EAST 0 1 ST.+---------------------------+ 3 | . . . . . . . | | | 2 | . . . . . . . | | | 1 | > 2 3 4 5 6 7 | +---------------------------+ 1 2 3 4 5 6 7 AVE.Koncová situácia:177 CORNER FACING BEEP-BAG BEEP-CORNER (1, 2) WEST 0 7 ST.+---------------------------+ 3 | . . . . . . . | | | 2 | < 6 5 4 3 2 1 | | | 1 | . . . . . . . | +---------------------------+ 1 2 3 4 5 6 7 AVE.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). - 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.
-
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). - 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ý.
-
Vytvorte program, pomocou ktorého bude Karel vedieť vytvoriť vo svete, v ktorom sa nachádza, Fibonacciho postupnosť. O svete platí, že je vysoký práve 2 riadky a široký n stĺpcov, pričom n>3.
Počiatočná situácia:
0 CORNER FACING BEEP-BAG BEEP-CORNER (1, 1) EAST 0 1 ST.+-------------------------------+ 2 | . . . . . . . . | | | 1 | > . . . . . . . | +-------------------------------+ 1 2 3 4 5 6 7 8 AVE.Koncová situácia:556 TURNOFF CORNER FACING BEEP-BAG BEEP-CORNER (8, 1) EAST 67 0 ST.+-------------------------------+ 2 | . . . . . . . . | | | 1 | 1 1 2 3 5 8 13 > | +-------------------------------+ 1 2 3 4 5 6 7 8 AVE.
Ďalšie zdroje
- PDCurses - verzia knižnice curses pre operačný systém Windows (pdcurses.lib, pdcurses.dll)
- Knižnica Karel the Robot (Hlavičkový súbor, Windows, Linux 32b, Linux 64b)
- Rudolf Pecinovský: Základy algoritmizace - kapitoly 8, 10
- Pavel Herout: Učebnice jazyka C (1. díl) - kapitoly 5.1, 5.4, 5.5
Poznámka: