Program je nutnou součástí řešení pouze v případě, je-li to v zadání výslovně uvedeno. Program může být napsán buď v jazyce Pascal nebo v jazyce C. Program nemusí realizovat všechny části řešení. Zejména je možné vynechat ty části, které zabezpečují vstupy, výstupy a jednoduché operace (např. operace s množinami, implementaci jednoduchých geometrických vztahů apod.).
P-II-1
Trojúhelníková síť se skládá z rovnostranných trojúhelníků
jednotkové velikosti. Soustavu souřadnic si nyní trochu
pozměníme: x-ová osa bude orientována stejně, jako jsme zvyklí
z kartézské soustavy souřadnic, y-ová osa svírá s x-ovou
60stupňový úhel. Například vrcholy jednoho z jednotkových
trojúhelníků mají souřadnice (0,0), (1,0), (0,1).
V této síti zadáme N-úhelník - jeho vrcholy leží ve vrcholech sítě, jsou navzájem různé, přičemž každé dva sousední vrcholy v N-úhelníku mají jednotkovou vzdálenost. N-úhelník je zadán na vstupu tak, že první řádek vstupu obsahuje číslo N a dalších N řádků obsahuje souřadnice vrcholů, přičemž tyto vrcholy jsou zadány postupně po obvodu.
Například posloupnost '[4[100 90]]' nakreslí čtverec se stranou
100. (Všimněte si, že číselné parametry jsou oddělené mezerou.)
Starší kreslicí zařízení obvykle mají rozsynchronizované ovládací
obvody. Proto se stává, že často nakreslí místo čáry délky P čáru
délky P+1 nebo P-1. V důsledku toho kreslicí pero obvykle skončí
na jiném místě, než kde mělo skončit podle zadané posloupnosti.
Délkou slova w rozumíme počet znaků, z nichž se slovo skládá,
označujeme ji |w|. Zřetězením slov
v=a1a2...an
a u=b1b2...bm
rozumíme slovo
v*u=a1a2...anb1b2...bm.
Množinu všech slov,
která se dají vytvořit ze znaků abecedy A, označujeme A*.
Tato množina obsahuje také prázdné slovo, t.j. slovo nulové délky,
které označujeme _ .
Pravidlem nad abecedou A nazýváme uspořádanou dvojici (a,v),
kde a je prkem A a v je prvkem A*.
Pravidlo zapisujeme ve tvaru a -> v.
Deterministický Lindermayerův systém bez interakce (D0L systém)
je uspořádaná trojice (A,P,w), kde
Růstovou funkcí D0L systému nazýváme takovou funkci
f: N -> N0 (N={1,2,...}, N0={0,1,2,...}), která
pro pořadí slova v posloupnosti produkované D0L systémem udává
délku tohoto slova. Přesněji f(i)=|wi|.
P-II-2
Pro danou konstantu N (N je prvočíslo, např. 991) máme vyhrazeno
N-prvkové celočíselné pole P s indexy 0 až N-1. V tomto poli máme
uloženo M různých kladných čísel (M
Úloha
P-II-3
Máme kreslicí zařízení schopné kreslit různé obrázky. Jejich
popis však musí být zadán ve speciálním tvaru (jako znakový
řetězec):
Tuto posloupnost bude kreslicí zařízení interpretovat následovně:
Kreslicí pero je stále natočeno nějakým směrem (na začátku
algoritmu na sever) a podle parametrů posloupnosti buď mění toto
natočení, nebo se v aktuálním směru pohybuje dopředu nebo dozadu
(kreslí čáru) podle toho, zda je tato vzdálenost kladná nebo
záporná.Úloha
Nalezněte a dokažte algoritmus, který pro danou vstupní
posloupnost (ve tvaru znakového řetězce) určí, jak nejdále může
pero staršího kreslicího zařízení skončit od místa, kde mělo
skončit podle zadané posloupnosti.P-II-4
Vytvořte D0L systém (nebo dokažte, že to není možné), jehož
růstová funkce je:
D0L systémy
Abecedou nazýváme libovolnou konečnou neprázdnou množinu. Prvky
této množiny nazýváme znaky.
Konečnou posloupnost znaků z nějaké abecedy
nazýváme slovo. Znaky označujeme zpravidla písmeny ze začátku
abecedy (a, b, c, ...), slova písmeny z konce abecedy (u, v, w, ...)
a abecedy velkými písmeny ( A, B, ...).
Takovýto D0L systém produkuje posloupnost slov w1, w2, w3, ..., která
začíná axiomem a pokračuje vždy slovem, jenž dostaneme z předcházejícího
slova současným nahrazením všech znaků za slova podle
pravidel. Tedy
Uvědomte si, že pro každý znak máme právě jedno pravidlo a tedy
právě jedno slovo, kterým budeme tento znak nahrazovat. Posloupnost
produkovaná D0L systémem je proto jednoznačně určena.Příklad
Poznámka: Při konstrukci D0L systému dáváme přednost takovým systémům,
které mají co nejmenší počet pravidel.
ab, aaab, aaaaaaab, aaaaaaaaaaaaaaab, ...
(Když slovo obsahuje více stejných písmen za sebou, můžeme nahradit
tato písmena jedním písmenem, u kterého uvedeme počet písmen,
která zastupuje. Zkráceně můžeme tedy psát posloupnost tohoto
D0L systému: ab, a3b, a7b, a15b, ...).