Úvod 1 2 3 4 Příklady Testy

Lekce 3

Obsah


Anotace kapitoly
V této kapitole se seznámíte s obecnými postupy, které programátor potřebuje nutně znát a to na řešených příkladech. Příklady podobného typu, ale neřešené naleznete v kapitole ÚLOHY. Po prostudování této kapitoly byste měli řešit běžné úlohy s využitím programu FERDA. Jednotlivé typy úloh se vám objeví opět a znovu při řešení algoritmů v kapitole o základech programování v prostředí Pascal.

Řešené úlohy


Zadání 1.1 - téma kreslení značek

Ferda v prázdném městě nakreslí ze značek čtverec 4x4.
Řešení:
Aby výsledek byl visuálně příjemný, necháme Ferdu odejít kousek do města a tam vytvoříme čtverec. Vlastní počáteční pochod Ferdy složíme ze dvou příkazů, které bez použití procedur napíšeme jako cykly s pevným počtem opakování a pak zopakujeme čtyřikrát složený příkaz, kde Ferda provede čtyřkrok a pokládá značku. V druhé variantě využijeme procedur, které sestavíme a pak použijeme v programu. Programy opatříme potřebnými komentáři. Více než slovní popis vždy pomůže prostudovat si jak je program utvořen.
program CTVEREC4x4 var. 1
rem uložen v adresáři EXAPML jako soubor CVTR4x4.frd
rekni Jdu na místo
cyklus 5
 krok
konec cyklus
vlevo vbok
cyklus 5
 krok
konec cyklus
vpravo vbok
rekni Jsem na místě, kreslím čtverec
cyklus 4
 cyklus 4
  poloz
  krok
 konec cyklus
 vlevo vbok
konec cyklus
domu
rekni Hotovo
konec programu
Takto zapsán, je i tento jednoduchý program dosti nepřehledný. Zkusme zápis programu zjednodušit s tím, že opakující se příkazy převedeme na příkazy typu procedura.
program CTVEREC4x4 var. 2
rem uložen v adresáři EXAPML jako soubor CVTR4x4P.frd
rekni Jdu na místo
proc_5krok
vlevo vbok
proc_5krok
vpravo vbok
rekni Jsem na místě, kreslím čtverec
cyklus 4
 proc_4krokpoloz 
 vlevo vbok
konec cyklus
domu
rekni Hotovo
konec programu

rem definice procedur
df_5krok
cyklus 5
  krok
konec cyklus
konecproc

df_4krokpoloz 
 cyklus 4
  poloz
  krok
 konec cyklus
konecproc
Pro konečný tvar programu zvolíme ještě zápis, který využívá možnosti psát v tělě procedur volání jiných procedur a funkcí a tak poté napsat vlastní tělo programu velmi stručně a ostatní příkazy zapsat pouze v procedurách.
program CTVEREC4x4 var. 3
rem uložen v adresáři EXAPML jako soubor CVTR4x4U.frd
rekni Jdu na místo
proc_namisto
rekni Jsem na místě, kreslím čtverec
proc_ctverec
domu
rekni Hotovo
konec programu

rem definice procedur

df_namisto
 proc_5krok
 vlevo vbok
 proc_5krok
 vpravo vbok
konecproc

df_ctverec
cyklus 4
 proc_4krokpoloz 
 vlevo vbok
konec cyklus
konecproc

df_5krok
cyklus 5
  krok
konec cyklus
konecproc

df_4krokpoloz 
 cyklus 4
  poloz
  krok
 konec cyklus
konecproc
rem konec zápisu programu
Postup, kterým jsme došli od první až ke třetí variantě programu se nazývá konstrukce algoritmu zezdola (od nejsloľitějąí varianty) nahoru - po nejjednodušší variantu. V praxi se používá pro zpřehlednění zápisu celého algoritmu poté, co byl program napsán bez procedur. Pro návrh řešení úloh se běžně používá i postup opačný, postup shora dolů. Tento postup si ukážeme na následující úloze.

Zadání 1.2 - téma kreslení značek

Ferda v prázdném městě nakreslí ze značek rovnoramenný trojúhelník se základnou o velikosti 8 značek.

Řešení této úlohy budeme provádět metodou konstrukce shora. Celkový rozvrh řešení této úlohy si můžeme rozepsat do tří hlavních kroků
1. Ferda dojde na místo
2. Ferda nakreslí trojúhelník
3. Ferda se vrátí domů
Pro první krok můžeme využít proceduru proc_namisto z předcházejícího příkladu. Třetí krok je přímo základní příkaz. Druhý krok ovšem si musíme rozepsat na tři kroky, kdy Ferda kreslí jednotlivé strany trojúhelníka.
Rozepsání druhého kroku bude tedy vypadat takto:
1. kreslím základnu
2. otáčím se do vhodného směru
3. kreslím šikmou stranu
4. otáčím se do vhodného směru
5. kreslím šikmou stranu
Řešení bodu 1 je jasná procedura s cyklem s pevným počtem osmi opakování, kde v těle procedury budou již základní příkazy:

DF_8krokpoloz
cyklus 8
 poloz
 krok
konecproc
Po vhodném otočení Ferdy je možné, aby i jeho šikmá chůze byla řešena cyklem s pevným počtem 4 opakování, ale s tím, že místo jednoduchého kroku musí Ferda udělat krok šikmo. (Proč je zde číslo 4 a ne 8 ?)
DF_4krokpoloz
cyklus 4
 poloz
 sikmokrok
konecproc
Krok šikmo vyřešíme pak také procedurou DF_sikmokrok, která bude složena z elementárních příkazů.
DF_sikmokrok
 krok
 vlevo vbok
 krok
 vpravo vbok
 krok
konecproc
Celý program bude poté zapsán takto:
program TROJUHELNIK8 var. 1
rem uložen v adresáři EXAPML jako soubor TROJ8.frd
rem hlavni program - main program
proc_namisto
proc_trojuhelnik
domu
konec programu

rem definice procedur

DF_trojuhelnik
 proc_8krokpoloz
 vlevo vbok
 proc_4sikmokrokpoloz
 vlevo vbok
 proc_4sikmokrokpoloz
konecproc

DF_namisto
 proc_5krok
 vlevo vbok
 proc_5krok
 vpravo vbok
konecproc

DF_5krok
cyklus 5
  krok
konec cyklus
konecproc

DF_8krokpoloz
cyklus 8
 poloz
 krok
konec cyklus
konecproc

DF_4sikmokrokpoloz
cyklus 4
 poloz
 proc_sikmokrok
konec cyklus
konecproc

DF_sikmokrok
 krok
 vlevo vbok
 krok
 vpravo vbok
konecproc
rem konec celého programu
Program si nahrajte a spusťte. Zkuste kreslit trojúhelníky i větší a třeba i jinak natočené.
Jak může město vypadat po ukončení úkolu je na obrázku:

Zadání 1.3 - téma kreslení značek

Ferda nakreslí vyplněný obdélník značek s tím, že obvod čtverce budou tvořit políčka se třemi značkami. Dvě strany obdélníku Ferdovi ve městě předem vyznačíme - viz obrázek města CTV00.MST
Řešení:
program PLNÝ ČTVEREC var. 1
rem uložen jako PLNCTV0.FRD v adresáři EXAMPL
rekni Jdu to vyplnit značkami
proc_vyplnoblast
rekni Tak jsem skončil
domu
konec programu

rem definice procedur

DF_vyplnoblast
poloz
opakuj
 proc_vyplnradek1 
 vlevo vbok 
 kdyz nebude znacka
  krok
  poloz
 konec kdyz
 vlevo vbok
 kdyz nebude znacka
  proc_vyplnradek2
  vpravo vbok
 konec kdyz 
 kdyz nebude znacka
   krok
   poloz
 vpravo vbok
 konec kdyz
az do bude znacka
konecproc

DF_vyplnradek1
dokud nebude znacka
 krok
 poloz
konec dokud
konecproc

DF_vyplnradek2
dokud nebude zed
 krok
 poloz
konec dokud
konecproc
Jak může město vypadat po ukončení úkolu je na obrázku:

Zadání 1.4 - téma kreslení značek

Ferda vyplní obdélník značkami. Konec oblasti Ferdovi předem označíme ve městě třemi značkami na konci prvního řádku a posledního sloupce. Příklad takto vyznačeného města naleznete v souboru města CTV01.MST
Řešení:
Ponevadž Ferda ví, že má položit značku a že se má otočit, když dojde ke třem značkám nebo ke zdi, zdá se úkol jednoduchý. Rozeberme si tento algoritmus podrobněji. První řadu Ferda položí jednoduše (proc_znackakrok) než narazí na tři značky. Tam se otočí a přejde na další řadu. Zde půjde až ke zdi, pak se otočí a půjde ..., ale teď nebude vědět, kde má skončit, protože nezná přesný počet kroků, které má udělat. Tedy tuto úlohu budeme muset řešit jinak, neboť náš první náhled na řešení algoritmu nebyl správný. Musíme tedy uvažovat od toho kroku, který nám způsobil problém. Tedy aby Ferda věděl, kde se má otočit, tak na tom místě musí mít nějaké znamení - značku. Poněvadž, vyjma prvního řádku, tam žádná značka není, musí si je do města položit sám. Teprve poté se může vrátit domů a začít s pokládáním značek, jak jsme naznačili shora.
Algoritmus pak lze rozepsat takto:
1. označ si oblast
2. vrať se domů
3. vyplň vyznačenou oblast značkami
4. vrať se domů
Vlastní program může pak vypadat třeba takto:
program PLNÝ ČTVEREC var. 1
rem uložen jako PLNCTV1.FRD v adresáři EXAMPL
rekni Jdu si vyznačit oblast
proc_oznacoblast
rekni Vyplňuju oblast
proc_vyplnoblast
rekni Tak jsem skončil
domu
konec programu

rem definice procedur
DF_oznacoblast
proc_keznacce
zvedni
zvedni
vlevo vbok
proc_carakzn
krok
zvedni
zvedni
vlevo vbok
proc_carakezdi
vlevo vbok
proc_carakezdi
vlevo vbok
konecproc

DF_vyplnoblast
opakuj
 proc_vyplnradek 
 vlevo vbok 
 kdyz nebude znacka
  krok
  poloz
 konec kdyz
 vlevo vbok
 proc_vyplnradek
 vpravo vbok
 kdyz nebude znacka
   krok
  poloz
 vpravo vbok
 konec kdyz
az do bude znacka
konecproc

DF_vyplnradek
dokud nebude znacka
 krok
 poloz
konec dokud
konecproc

DF_keznacce
dokud neni 3
 krok
konec dokud
konecproc

DF_carakzn
dokud nebude 3
 krok
 poloz
konec dokud
konecproc

DF_carakezdi
dokud nebude zed
 krok
 poloz
konec dokud
konecproc
Program si vyzkoušejte a zkuste ho modifikovat - upravit třeba tak, že Ferda bude pokládat jen každou druhou značku. A opět ukázka města po ukončení programu.

Zadání 1.5 - téma nalezení a přinesení značky

V prázdném městě je náhodně umístěna značka. Ferda ji nalezne a odnese domů. Pak ukončí program. Řešení:
program SBĚR ZNAČEK var.1
rem program je uložen jako soubor SEBER0.FRD v adresáři EXAMPL
rekni Jdu hledat
proc_najdiznacku
rekni Už ji nesu
proc_jdidomu
rekni Už jí mám v pelíšku
konec programu

rem  definice procedur
df_najdiznacku
 dokud neni znacka
  krok
  kdyz bude zed
      vlevo vbok
        kdyz je jih
           celem vzad
        konec kdyz
      krok
      vlevo vbok
        kdyz bude zed
           celem vzad
        konec kdyz
  konec kdyz
 konec dokud
konecproc

df_jdidomu
zvedni
dokud neni zapad
 vlevo vbok
konec dokud
proc_kezdi
vlevo vbok
proc_kezdi
vlevo vbok
konecproc

df_kezdi
dokud nebude zed
 krok
konec dokud
konecproc
rem konec textu programu

Zadání 1.6 - téma řazení značek podle počtu

Ve městě jsou na prvním řádku položeny náhodně do dvou políček 1, 2 nebo 3 značky. Ferda tyto značky přenáší tak, že je seřadí podle velikosti - podle jejich počtu. To znamená, že na konci programu bude v řádku nejprve políčko s nejméně značkami a poslední s nejvíce značkami.
Řešení:
program POČÍTÁNÍ ZNAČEK var.1
rem program je uložen jako soubor POCIT0.FRD v adresáři EXAMPL
rekni Jdu hledat jednu značku
proc_najdiznacku1
rekni Jdu hledat dvě značky
proc_najdiznacku2
rekni Jdu hledat tři značky
proc_najdiznacku3
domu
konec programu

rem definice procedur
DF_najdiznacku1
dokud  neni 1 A nebude zed 
  krok
konec dokud
kdyz je 1
   proc_prines1
konec kdyz
kdyz bude zed
  celem vzad
  proc_kezdi
  celem vzad
konec kdyz
konecproc 

DF_najdiznacku2
 dokud neni  2  A  nebude zed
  krok
 konec dokud
 kdyz je 2
   proc_prines2
 konec kdyz
 kdyz bude zed
  celem vzad
  proc_kezdi
  celem vzad
 konec kdyz
konecproc 

DF_najdiznacku3
dokud neni 3  A  nebude zed
  krok
 konec dokud
 kdyz je 3
   proc_prines3
 konec kdyz
 kdyz bude zed
  celem vzad
  proc_kezdi
  celem vzad
 konec kdyz
konecproc 

DF_prines1
zvedni
celem vzad
rekni Už je nesu
proc_kezdi
celem vzad
krok
poloz
konecproc

DF_prines2
zvedni
zvedni
celem vzad
rekni Už je nesu
proc_kezdi
celem vzad
krok
krok
poloz
poloz
konecproc

DF_prines3
zvedni
zvedni
zvedni
celem vzad
rekni Už je nesu
proc_kezdi
celem vzad
krok
krok
krok
poloz
poloz
poloz
konecproc

DF_kezdi
dokud nebude zed
krok
konec dokud
konecproc
rem konec zápisu programu

Zadání 1.7 - téma sledování vyznačené cesty

Ve městě je pomocí značek vyznačena cesta. Cesta může vést i úhlopříčně a klikatě. Na konci cesty je zeď. Ferda jde po cestě a když dojde ke zdi zastaví se.

Řešení:
 
program jdi po šikmé cestě
rem program je uložen jako soubor CESTAX.FRD
rem mesto je ulozeno v souboru cestax.mst
rem v adresáři EXAMPL
rekni Jdu po cestě
dokud nebude zed
 kdyz bude znacka
  krok
 jinak
 vlevo vbok
  kdyz nebude znacka
  celem vzad
   kdyz nebude znacka
    vlevo vbok
    kdyz nebude zed
      krok
      vlevo vbok
       kdyz nebude znacka
         celem vzad
       konec kdyz
    konec kdyz
  konec kdyz
 konec kdyz
konec kdyz
konec dokud
rekni Končím s putováním
konec programu
rem konec zápisu algoritmu
Zkuste si načrtnout vývojový diagram tohoto algoritmu. Popřemýšlejte, zda by tento algoritmus nešel zapsat přehlednějším způsobem.


Zadání 1.8 - vyplňování oblastí

Ferda vyplní město značkami tak, že bude jeho obvod obcházet ve spirále.

Řešení:
 
program SPIRALA var. 1
rem program je uložen v souboru spirala.frd
rem v adresáři EXAMPL
cyklus 4
rekni Jdu vyplnit obvod města
 proc_polkezdi
 vlevo vbok
konec cyklus
 krok
 vlevo vbok
 krok
 vpravo vbok
rekni A teď už jdu po spirále
opakuj
dokud nebude znacka
 proc_polkezn
 vlevo vbok
konec dokud
az do bude znacka
poloz
domu
rekni A konečně hotovo
konec programu

rem definice procedur
DF_polkezdi
dokud nebude zed
poloz
krok
konec dokud
konecproc

DF_polkezn
dokud nebude znacka
poloz
krok
konec dokud
konecproc
rem konec definic
rem konec zápisu algoritmu
Zkuste tento algoritmus analyzovat a zefektivnit. Lze ho napsat jednodušším způsobem.


Zadání 1.8 - téma průchod souvislým bludištěm

Město je tvořeno souvislým bludištěm, t.j. každá zeď navazuje na jinou zeď nebo na okraj města. Ve městě je umístěna  značka. Ferda tuto značku nalezne a program ukončí. Jedna z možností řešení tohoti úkolu je znázorněna ma následujícím vývojovém diagramu.
Řešení:
rem program bludiste
rekni Tak odcházím  hledat ten poklad.
dokud neni znacka
rychle
vpravo vbok
kdyz nebude zed
krok
jinak 
vlevo vbok
kdyz nebude zed
krok
jinak
vlevo vbok
konec kdyz
konec kdyz
pomalu
konec dokud
rekni Tak ho mám.
konec programu
Přepis vývojového diagramu do programu pro Ferdu je nepřesný a má dvě změny. Naleznete je? Proč jsou v programu použity příkazy RYCHLE a POMALU?
Při studiu tohoto algoritmu zjistíte, že je zbytečně dlouhý a opakují se dvakrát tytéž algoritmické struktury. Zkuste napsat algoritmus jednodušší, přesnější a rychlejší.


Zadání 1.9 - téma průchod souvislým bludištěm s návratem

Město je tvořeno souvislým bludištěm, t.j. každá zeď navazuje na jinou zeď nebo na okraj města. Ve městě je umístěna  3 - značka. Ferda tuto 3 - značku nalezne a vrátí se nejkratší cestou zpět. Poté program ukončí. Konečný stav programu je na obrázku.
 
program bludiste s návratem
rem program je uložen v souboru BLUD2.FRD
rem soubor mesta je uložen v souboru BLUD1.MST
rekni Tak odcházím  hledat ten poklad.
poloz
poloz
dokud nebude 3
 kdyz neni znacka
    poloz
  jinak
    kdyz bude znacka 
      zvedni
    konec kdyz
  konec kdyz
krok
vpravo vbok
 dokud bude zed
   vlevo vbok
 konec dokud
konec dokud
rekni Tak ho mám.
poloz
krok
zvedni
zvedni
zvedni
dokud nebude znacka
 vlevo vbok
konec dokud
opakuj
 kdyz bude znacka
  krok
 jinak
  vlevo vbok
  kdyz nebude znacka
   celem vzad
  konec kdyz
  kdyz nebude znacka
   celem vzad
  konec kdyz
 konec kdyz
az do je 2
konec programu


Zadání 1.10 - téma generátor náhodných čísel

Ferda položí náhodně do prvního řádku značky.
Jediná možnost, kterou Ferda má ke generování náhodných hodnot je příkaz RANDOM VBOK. Na tento příkaz provede Ferda náhodně buď vlevo nebo vpravo vbok. Procedura, která převede náhodný pohyb na položení značky je uvedena v programu. Řešení:
program Náhodný generátor
rem program je uložen v souboru GENE0.FRD
rem v adresáři EXAMPL
opakuj
 proc_nahzn
 krok
az do bude zed
konec programu

rem definice procedur
DF_nahzn
random vbok
kdyz je sever
 kdyz neni 2
  poloz
 konec kdyz
konec kdyz
proc_navychod
konecproc

DF_navychod
kdyz je sever
 vpravo vbok
konec kdyz
kdyz je jih
 vlevo vbok
konec kdyz
konecproc

rem konec algoritmu
Pokuste se modifikovat tento program tak aby Ferda pokládal náhodně 1 až tři značky do první řady, do více řad. Pokud si představíte tiket sportky (7x7 políček), je možné napsat program, v kterém Ferda náhodně položí na různá místa právě šest značek? Zkuste to.