*Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Mariánovi Horňákovi na *
Pracovitým KSP vedúcim, ktorí študujú na matfyze, počas písania nových zadaní vysmädlo. Avšak sú príliš zaneprázdnení a preto si kofolu nestíhajú ísť kúpiť sami. Postavili si preto robota, ktorý kofolu prinesie za nich.
Matfyz je ale miesto veľmi zradné1. Na kľukatých chodbách z podlahy niekedy šľahá oheň (to je bežné, tak sa tam kúri) a preto robot prechádzajúci takým miestom musí najskôr kúrenie pomocou tlačítka vypnúť. Vieš im pomôcť tohoto robota naprogramovať?
Dostanete prístup k programovaciemu rozhraniu robota, spolu s náhľadom na level. V tomto rozhraní môžete pomocou jednoduchého programovacieho jazyka napísať pre robota program. Po napísaní si program môžete hneď aj spustiť, a uvidíte ako sa robot vďaka nemu pohybuje.
Vašou úlohou bude napísať program, pomocou ktorého robot bez ujmy na obvodoch prejde bludiskom. Samozrejme mu musí vydržať batéria a stačiť pamäť.
Celý návod k hre ako aj k programovaciemu jazyku nájdete v hlavnom menu hry, kliknutím na veľké tlačítko Návod.
V súťažnej sérií bude 5 levelov, každý za 3 body. Akonáhle spustíte správny program a robot sa s jeho pomocou dostane do cieľa, budú vám automaticky pripísané body za daný príklad. To znamená, že k tejto úlohe nie je nutné odovzdávať žiaden popis alebo tradičným spôsobom odovzdávať program.
Hru nájdete na stránke ksp.sk/specialne/ksp/32/3/1.
Tu stačilo robota odnavigovať na správne tlačidlo, prepnúť ho a odnavigovať do cieľa. To, ktoré tlačidlo je správne, sa dalo zistiť napríklad tak, že ste postupne vyskúšali všetky. Správne bolo tretie tlačidlo zdola.
Kód:
`doprava
krok
krok
doprava
krok
prepni
doprava
krok
krok
doprava
krok
krok
krok`
V tomto leveli je na prvý pohľad jasné, čo má robot urobiť. Problém ale je, že nemá dosť pamäte na všetky príkazy. Môžeme si však všimnúť, že U-čko sa skladá z troch rovnakých častí. Napíšeme si teda funkciu, ktorá nám prejde jednu časť U-čka a túto funkciu potom zavoláme trikrát za sebou. Treba si však dať pozor, aby bol robot po dokončení jedného ramena U-čka správne otočený, na konci funkcie ho preto otočíme doprava.
Kód:
`funkcia0
funkcia0
funkcia0
aha funkcia0:
krok
prepni
krok
krok
doprava`
Potrebujeme prejsť veľa rovnakých schodov, preto sa nám oplatí napísať si funkciu na prejdenie jedného schodu:
`aha funkcia0:
krok
doprava
krok
dolava`
Teraz však narazíme na problém: môžeme použiť už iba dva príkazy a schodov je oveľa viac, než dva.
Použijeme preto jeden zaujímavý trik: napíšeme funkciu, ktorá prejde jeden schod a potom zavolá sama seba. Keď sa táto funkcia začne vykonávať, prejde jeden schod a sama sa zavolá znovu. Opäť prejde jeden schod a znovu sa zavolá. A takto bude náš program pokračovať až do nekonečna, resp. kým robotovi nedôjde batéria alebo nepríde do cieľa.
Kód:
`funkcia0
aha funkcia0:
krok
doprava
krok
dolava
funkcia0`
Ako už viete zo študíjneho textu, tento princíp sa volá rekurzia. V našom prípade ide o nekonečnú rekurziu, čo pekne vystihuje Obr. 4. Na našu funkcia0 sa môžeme pozerať tak, že je to funkcia, ktorá prejde nekonečne veľa schodov. Urobí to tak, že najprv prejde jeden schod (prvé 4 príkazy) a potom ešte nekonečne veľa ďalších (posledný príkaz).
Najjednoduchšie asi bude ísť po riadkoch a cestou prepnúť správne políčka.
Existuje viacero spôsobov, ako prejsť takúto cestu. Jednou z možností je napísať si štyri funkcie, ktoré sa navzájom volajú v nekonečnej rekurzii. My si ale vystačíme aj s niečím jednoduchším.
Budeme potrebovať, aby robot prepol prepínač na každom druhom políčku, cez ktoré prejde. Napíšme si teda funkciu, ktorá prejde dve políčka, pričom to, na ktoré stúpi skôr, prepne:
`aha funkcia0:
krok
prepni
krok`
S jej pomocou si môžeme napísať funkciu, ktorá prejde jeden riadok šachovnice a prepne pri tom potrebné políčka – za predpokladu, že štartujeme na tom konci riadka, ktorý nemá byť zapnutý:
`aha funkcia1:
funkcia0
funkcia0
funkcia0
funkcia0`
Všimnime si, že táto funkcia sa po zapnutí posledného prepínača v riadku bude snažiť urobiť ešte jeden krok. To nám ale neprekáža, robot sa iba pokúsi urobiť krok do steny (alebo na JetTorch, ktorý už v tom čase bude vypnutý).
Aj na prejdenie ľavotočivej a pravotočivej zákruty si môžeme napísať funkcie:
`aha funkcia2:
dolava
krok
dolava
aha funkcia3:
doprava
krok
doprava`
Na ceste, po ktorej má robot prejsť, sa striedajú rovné úseky a zákruty, pričom zákruty sú striedavo ľavotočivé a pravotočivé. Napíšme si teda funkciu, ktorá nám prejde dva rovné úseky a zákruty nasledujúce po nich:
`aha funkcia4:
funkcia1
funkcia2
funkcia1
funkcia3`
Keď túto funkciu zavoláme štyrikrát po sebe, robot by mal prejsť celú šachovnicu. Problém ale je, že po prejdení posledného riadka sa bude snažiť prejsť ešte jednu pravotočivú zákrutu. Preto ju radšej zavoláme iba trikrát a posledné dva rovné úseky (aj so zákrutou medzi nimi) rozpíšeme. Robot by potom skončil na políčku s JetTorchom (nezabúdajte, že funkcia1 sa po prejdení riadka snaží urobiť ešte jeden krok), preto na koniec pridáme ešte jeden krok.
Hlavný kód:
`funkcia4
funkcia4
funkcia4
funkcia1
funkcia2
funkcia1
krok`
Kľúčovým pozorovaním v tomto leveli je to, že po zapnutom tlačidle treba ísť najbližšie dva kroky smerom na juh a po vypnutom prepínači treba ísť najbližšie dva kroky smerom na východ. Po urobení dvoch krokov správnym smerom sa bude robot nachádzať na nasledujúcom prepínači.
Tiež si môžeme všimnúť, že máme povolených iba veľmi málo príkazov. Preto opäť využijeme nekonečnú rekurziu: napíšeme si funkciu, ktorá (za predpokladu, že robot stojí na prepínači) urobí dva kroky správnym smerom, a potom sa zavolá znovu.
Tu ale narazíme na jeden problém: robot nevie zistiť, ktorým smerom je práve otočený, teda nebude vedieť, ktorým smerom je východ a ktorým smerom je juh. To môžeme vyriešiť tak, že vždy potom, čo robot prejde na ďalší vypínač, sa otočí na východ (teda ak išiel na juh, otočí sa doľava a ak išiel na východ, ostane tak, ako je). Na to si ale bude musieť pamätať, či bolo predošlé tlačidlo stlačené alebo nie. To docielime tak, že namiesto toho, aby sa robot na tlačidle iba otočil alebo neotočil (podľa toho, či je zapnuté), a potom urobil dva kroky, sa na tlačidle zavolá buď funkcia, ktorá urobí dva kroky smerom na východ, alebo funkcia, ktorá urobí dva kroky smerom na juh a potom sa otočí na východ.
Kód:
`funkcia0
aha funkcia0:
funkcia1 ak svieti
funkcia2 ak nesvieti
funkcia0
aha funkcia1:
doprava
krok
krok
dolava
aha funkcia2:
krok
krok`
Počas behu programu si môžeme všimnúť, že niekedy sa v jednom volaní funkcia0 zavolá aj funkcia1 aj funkcia2 (nastane to vtedy, keď je robot na zapnutom tlačidle, ale po vykonaní funkcia1 sa ocitne na vypnutom tlačidle). To nám v našom prípade neškodí, ale keby sme chceli, aby sa v jednom volaní funkcia0 zavolala vždy iba jedna z funkcií 1 a 2, mohli by sme to docieliť napríklad tak, že by sme funkcia0 zavolali aj na konci funkcia1. Teda ak by tlačidlo bolo zapnuté, netestovalo by sa, či sa má spustiť funkcia2. [text o rekurzii]: TO_DO