Logo2 – operace, rekurze, větvení výpočtu Operace Je naše vlastní operace, jejím výsledkem je nějaká hodnota. Na určení tohoto výsledku musíme použít základní příkaz jazyka Imagine logo. A tím je – výsledek. Vždy když program Imagine při vykonávání procedury najde příkaz výsledek, zastaví výpočet této procedury a hodnotu výrazu za příkazem výsledek vrátí jako výstup procedury. Příkaz výsledek má vlastně stejný význam jako příkaz konec. Příklad 1 Porovnáme dvě hodnoty a určíme, která je menší. Tu pak označíme jako min. Běžně se samozřejmě pracuje s větším množstvím čísel – např. s posloupností n čísel. Tento příklad je tu pro názornost. Příkaz min :a :b kdyžJinak :a < :b [výsledek :a] [výsledek :b] konec V Imagine logo existují tyto druhy operací – číselné - logické - operace jejichž výsledkem je ano nebo ne, podmínky, predikáty Číselné operace Číselné operace jsou procedury s jedním, dvěma nebo více číselnými vstupy a číselným výsledkem. Tento výsledek lze, obdobně jako u funkcí v Delphi, použít pro jiné operace nebo příkaz jako jejich vstup např. logická operace, operace náhodně. Podmínkou může být jakákoliv operace, ať už základní nebo definovaná námi, která vyhodnotí určitou podmínku či vztah mezi svými vstupy a podle pravdivosti vrátí jako výsledek ano nebo ne. Logické operace Logické operace. Ty vykonávají bitové operace na celočíselných vstupech. Každý z níže vypsaných očekává jako svůj vstup jedno, dvě nebo i několik celých čísel. Jsou to bitAnd bitNot bitOr bitXor Některé další z logických operací umožňují kombinovat jednoduché podmínky a vytvářet z nich složitější. Vstupy pro tyto operace jsou logické hodnoty. Imagine nejprve vyhodnotí všechny vstupní výrazy a jejich hodnoty potom pošle jako vstupy operacím nebo,zároveň apod. např. zároveň číslo ? :p prvočíslo? :p. 1
Nesmíme však zapomenout, že někdy je výhodnější nevyhodnocovat všechny vstupní výrazy napřed, ale až v té chvíli než je začne zpracovávat operace zároveň, nebo atd. Proč? Protože pokud by např. zadané prvočíslo nebylo číslo, je potom zbytečné vykonávat ostatní příkazy. Lepší je zadat celou podmínku v jiném tvaru a to - zároveň číslo? :p [prvočíslo? :p]. To znamená, že druhý výraz/příkaz se vyhodnotí až operací zároveň (t.j. ne před samotným jádrem Imagine)a to i v případě, jestliže je první hodnota slovo ano. Operace jejichž výsledkem je ano nebo ne Operace jejichž výsledkem je ano nebo ne, nazýváme podmínky nebo predikáty. Příkladem takovýchto podmínek jsou číselné operace <, >, <=, >=, <>, = , a nebo predikáty jako slovo? seznam? atd. Slovo ano znamená, že určitá podmínka je pravdivá. Ne pak znamená, že podmínka je nepravdivá. Některé procedury prostředí Imagine očekávají jako jeden ze svých vstupů buď ano nebo ne, když, když2 nebo otestuj, a získávají je testováním určitých podmínek. Procedury jako slovo? nebo stejné? prázdný? Jsou jednoduché základní podmínky. Někdy však potřebujeme otestovat/zjistit složitější podmínku složenou z více jednoduchých. Imagine má několik operací, kterými můžeme spojovat jednoduché podmínky do složitějších. Jsou jimi např. zároveň, nebo, není a xor. Příklady Příklad 2 Máme za úkol vykreslit na plochu obdelník. Pak necháme želvu libovolně chodit po ploše. Pokud se bude nacházet v obdelníku vypíše se do příkazového řádku Ano, pokud bude mimo obdelník vypíše se Ne. - želva příkaz lib.procházka.pozice:a:b // dvě proměnné a,b = strany obdelníka pn // pero nahoru do 20 vp lib // do libovolně, vpravo libovolně => želva si chodí kde chce tp! 3 // tloušťka pera číslo 3 kdyz nebo (abs poz < :a/2) (abs poz < :b/2) [pis "Ano.]
kdyz nebo (abs poz > :a/2) (abs poz > :b/2) [pis "Ne.] * konec
// když nebo = buď nebo; když je absolutní pozice želvy menší než polovina strany „a“ tak vypiš [Ano.] nebo i případě když je absolutní pozice želvy menší než strana „b“ 2 // opak když je absolutní pozice želvy větší než polovina strany „a“ tak vypiš [Ne.] ….
Pokud bychom chtěli mít z této operace koncovou/ocasovou rekurzi, museli bychom zavolat operaci před koncem viz.*. Zápis - lib.procházka.pozice:a:b . Další variantu řešení najdete u větvení. Rekurze Definice rekurze Funkce, jejíž definice se odkazuje na sebe samu. Rekurzivní programy bývají stručnější a jednoduší pro pochopení než jiné modely, protože vystihují podstatu funkce. Zvláštním případem rekurze je iterace tzn. Rekurze se objevuje na začátku nebo konci sady instrukcí. Hloubka rekurze musí být konečná, ale ve skutečnosti i malá. Operuje na lineárních seznamech, stromech, grafech. Realizace rekurze Důležitým a účinným prostředkem na vyjádření rekurze v programování je procedura (nebo podprogram), které identifikátor slouží na rekurzivní aktivaci jejího těla. A podle zvoleného způsobu volání pak označujeme rekurzi buď jako přímou nebo nepřímou (viz. níže). Podmínky ukončení rekurze Protože u rekurzivních procedur je možnost nekonečných výpočtů, musíme se zaobírat my otázkou ukončení výpočtu. Základním požadavkem je, aby se rekurzivní volání procedury P řídilo podmínkou, která je za určité situace nesplnitelná. Např. dokud n > 0 opakuj Rozdělení rekurzí Rozeznáváme dva druhy rekurze – -
přímá rekurze – procedura volá sama sebe nepřímá rekurze – procedura volá jinou proceduru a ta volá opět původní proceduru
Kdy nepoužívat rekurzy Rekurzi bychom neměli používat, pokud již samotný charakter úlohy nevede přirozeným způsobem k rekurzivnímu řešení. Nesprávné a nevhodné je použití také tehdy, jestliže úlohu dokážeme stejně dobře, nebo dokonce i lépe řešit bez rekurze. V takovém případě je rekurze zbytečná a zpravidla vede jenom ke zvýšení časových a paměťových nároků programu při výpočtu. Naproti tomu se můžeme setkat s úlohami, které se pomocí rekurze řešily naprosto přirozeně a u nichž bylo použití rekurze zcela na místě. Jako příklad můžeme uvést techniku 3 prohledávání do hloubky včetně její aplikace při řešení grafových úloh na rekurzi je založena metoda „rozděl a panuj“, která se využívá například v některých třídících algoritmech. Výhody rekurze Hlavními výhodou rekurze je to, že -
- často poskytuje elegantnější a jednodušší řešení problému než u jiných nerekurzivních programů např. iterace - je mocným nástrojem pro řešení problémů, které jsou rekurzivně definovány - může být ekonomickým řešením problému, pokud není hloubka rekurzivního volání příliš velká -
můžeme realizovat vše od matematických úloh až po obrazce umožní zapsat podobně složité úlohy srovnatelně jednoduše, i jednodušeji pomocí rekurzivního algoritmu
Nevýhody rekurze – malá efektivita výpočtu - velké nároky na paměť Důvod je ten, že při každém volání rekurzivní procedury P vyžaduje procedura přidělení určitého množství paměti potřebné na lokální proměnné. Kromě těchto lokálních proměnných potřebujeme ještě paměť na uchování momentálního stavu výpočtu procedury. Praxe Pokud chceme psát jakýkoli program, a to i rekurzivní, musíme chápat jeho princip. Snad nejlépe se rekurze dá pochopit na rekurzivní proceduře na výpočet faktoriálu (n) nebo Fibonacciho čísla. Pokud tyto příklady chápete, tak vám psaní rekurze, ať už jakékoliv nebude dělat problémy. A nyní jeden z mnoha rekurzních příkladů z Imagine Loga. U každé operace je popis, co v programu vykoná. Další příklady naleznete na konci textu. Příklad 1 Náhodná procházka je jedna z nejvíce známých procedur v Imagine Logo. Želva má v tomto případě omezený prostor pro vykreslování. Samozřejmě můžeme želvu nechat chodit i volně, ale takto se dají vytvořit pěkné obrázky. Co má želva vykreslit vidíte na obrázku. Nezapomeňte želvu „zneviditelnit“.
příkaz proch.kruh100 // libovolná procházka, kruh průměr 100 do lib vp lib // dopředu lib vpravo libovolně => želva si jde o náhodně zvolenou vzdálenost dopředu a o náhodně zvolený úhel doprava barvaPera! "žlutá // nezapomínejte psát vykřičník a před barvou uvozovky kdyz abs poz > 50 [bp! "červená]
4 // pokud želva absolutní pozice želvy bude větší než 50 změní barvu pera na červenou
kdyz abs poz > 101 // pokud absolutní pozice želvy bude větší než 101 želva se vrátí [domu barvaPera! "žlutá] domu (do středu stránky)a barva pera se jí změní zpět na žlutou lib.procházka.kruh100 // zavoláním procedury A v proceduře A vytvoříme nikdy
konec
nekončící rekurzi; tím že umístíme toto zavolání těsně před konec procedury vytvoříme rekurzi ocasovou
Větvení Často potřebujeme při vytváření programu zajistit, aby se určité příkazy provedly jen tehdy, když je splněna nějaká podmínka. Podmínka = tvrzení, o kterém lze jednoznačně rozhodnout, zda je pravdivé či nepravdivé. (V Delphi používáme slova true, false). Příkaz = označuje jak jednoduchý, tak strukturovaný příkaz; např. příkaz cyklu, více příkazů – posloupnost příkazů, ale i další příkaz větvení. Rozeznáváme dva druhy větvení a to neúplné a úplné. Neúplné větvení Používáme v případě, chceme-li, aby se určitý příkaz vykonal/ provedl jen v případě, že je splněna zadaná podmínka. Zápis obecně – jestliže podmínka pak příkaz ; Co se stane ? Počítač si v programu „přečte“ podmínku a jestliže je splněna provede příkaz. Jestliže není splněna, program se ukončí. Nestane se nic. Úplné větvení U úplného větvení je to trochu jinak. Používáme jej v případě, že chceme, aby se při splnění podmínky vykonal nějaký příkaz. Když se nesplní vykoná s jiný nebo jiná sada příkazů. Zápis obecně – Jestliže podmínka pak příkaz1 jinak příkaz2 konec Co se stane v tomto případě je popsáno výše. 5 Praxe Příklad 1 Druhá verze v určení pozice želvy pomocí příkazu kdyžJinak. Neprve vykreslíme obdelník a poté, co přesuneme želvu na pozici domu můžeme se začít ptát, zda je v obdelníku či ne. příkaz obdelnik smaž
domů pn vl 90 do 100 vl 90 do 50 vp 180 pd opakuj 2 [do 100 90 do 200 90] domů konec příkaz kd obdelnik // voláme proceduru obdelník, aby se nám na ploše vykreslil kdyžJinak mimo? [-100 50] // ptáme se je-li želva mimo pozici zapsanou v hranaté [text"ano] závorce když není vypíše se „Ano.“; jinak se vypíše „Ne.“ [text"ne] konec Další příklady Příklad 1 Vykreslí sněhovou vločku. Jednu z rekurzivních křivek. Viz. obr. příkaz vločka1 :a do :a vl 60 do :a vp 120 do :a vl 60 do :a konec příkaz vločka3 pn vl 90 do 25 vp 90 do 15 pd opakuj 6 [vlocka1 20 vp 120 vlocka1 20 vl 60] pn do 100 pd konec 6 příkaz vločka4 příkaz vločka2 pn opakuj 6 [vlocka1 10 vp 120 vlocka1 10 vl 60] vl 90 konec do 50 vp 90 do 25 pd
opakuj 6 [vlocka1 30 vp 120 vlocka1 30 vl 60] pn do 100 pd konec příkaz vločkaC smaž domů tp! 2 vlocka2 cekej 500 pn domů pd vlocka3 cekej 500 pn domu pd vlocka4 konec Zavoláním vločkyC vznikne obrázek. Příklad 2 Vykreslí trojúhelníkovou spirálu. příkaz troj :d dosad ":d 10 tp! 3 bp! lib do :d vp 119 cekej 100 troj.spir :d + 5 konec Při jiném nastavení úhlu otáčení vznikají úplně jiné obrazce. Navíc je tato procedura rekurzivní – tzn. Vidíte jen část spirály. 7 Příklad 3 Rekurzivní program pro vykreslení nekonečného počtu bodu. příkaz body smaž
domů do 1 vp lib tp! 33 bp! lib pn do 20 pd body konec
8
