Zadání úloh školního kola 45. ročníku
Všeobecné pokyny
Řešení každého příkladu musí obsahovat (není-li uvedeno
v textu zadání úlohy něco jiného):
- popis řešení, to znamená popis
použitého algoritmu, zdůvodění správnosti vašeho
řešení (případně důkaz algoritmu), diskusi o efektivitě
zvoleného řešení apod. Důležité je, aby byl popis řešení jasný
a srozumitelný i bez toho, že bylo třeba nahlédnout do samotného
programu.
- program je nutnou součástí řešení v případě, že to zadání
úlohy vyžaduje (tedy v prvním a třetím příkladu). Program může být
napsán buď v jazyce Pascal, nebo
v jazyce C. Program je nutno odevzdat v písemné formě a také
na disketě, aby bylo možné otestovat jeho funkčnost. Na jedné
disketě odevzdávejte program vždy jen k jednomu řešení.
Není tedy možné na stejné disketě odevzdat řešení prvního i
třetího příkladu. V rámci školy je ale možné domluvit, že řešení
téhož příkladu od více řešitelů budou zaslána společně na
jedné disketě (v tom případě je však třeba důkladně rozlišit
jednotlivé řešitele, nejlépe pomocí názvů podadresářů).
P-I-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 60 stupň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.
Napište a odlaďte program, který
- vykreslí tento N-úhelník na obrazovku
- vypíše zprávu o tom, zda je konvexní nebo ne (N-úhelník je konvexní,
jestliže úsečky spojující libovolné dva vrcholy leží celé uvnitř,
resp. na hranici N-úhelníka.)
Poznámka: Minimalizujte paměťovou a časovou složitost algoritmu.
Můžete předpokládat, že vstupní data jsou zadána korektně.
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. Prvky pole jsou na
začátku inicializovány na nulu. Do tohoto pole budeme postupně zařazovat L
celočíselných hodnot (navzájem různých a různých od nuly), kde 2 < L < N,
pomocí procedury
zarad
:
procedure zarad(X:integer);
var i:integer;
begin
i := (x div 10 + x mod 10) mod N;
while P[i] <> 0 do
i := (i+7) mod N;
P[i] := x;
end;
Tato procedura nejprve ze zařazované hodnoty X vypočítá předpokládanou
hodnotu indexu v poli P, a pokud je tento prvek pole již obsazen (je tam
nenulová hodnota), postupně hledá nejbližší volnou pozici v poli (pole je
přitom ``zacyklené'' - za posledním (N-1)-tým prvkem následuje nultý).
Jestliže je při hledání volného místa nutné postupně prohlížet následující
prvky, budeme tuto situaci nazývat
kolize a budeme počítat počet
vzniklých
kolizí. Počet kolizí při zařazování j-té hodnoty budeme označovat K[j]
(K[j] bude tedy rovno počtu průchodů cyklem
while
při zařazování
j-té hodnoty), celkový počet kolizí označíme C
K.
Navrhněte algoritmus, který pro daná tři čísla L, G
a CK najde takovou vstupní posloupnost hodnot H (délky L),
aby celkový počet kolizí pro tuto posloupnost byl CK a
poslední hodnota
byla H[L]=G, případně zjistí, že taková posloupnost neexistuje.
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):
- je to posloupnost parametrů uzavřená v '
[
' a ']
'
závorkách
- parametrem je buď číslo nebo opět posloupnost parametrů
- posloupnost parametrů je vždy sudé délky, přičemž na
lichých pozicích je vždy číslo
Tuto posloupnost bude kreslicí zařízení interpretovat následovně:
- je-li posloupnost prázdná, nekreslí se nic
- je-li neprázdná, zřejmě první parametr (P1) je číslo a druhý (P2)
je buď číslo, nebo opět posloupnost parametrů:
- pokud je P2 číslo, kreslicí pero přejde (se spuštěným perem)
v momentálním směru natočení vzdálenost P1 a potom se otočí
o úhel P2 vpravo (úhel je zadán ve stupních)
- pokud je P2 posloupnost, kreslicí
zařízení P1-krát zopakuje
posloupnost P2
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á.
Například posloupnost [4[100 90]]
nakreslí čtverec se stranou 100.
(Všimněte si, že číselné parametry jsou oddělené mezerou.)
Napište a odlaďte program, který přečte vstupní posloupnost
zadanou ve tvaru znakového řetězce a zinterpretuje ji na grafické ploše
obrazovky.
Můžete předpokládat, že vstupní posloupnost je zadána korektně, obsahuje
jen celočíselné hodnoty a že řetězec není delší než 255 znaků.
Vytvořte D0L systém, jehož růstová funkce je:
- f(n) = 4
- f(n) = n
- f(n) = 3n+2
- f(n) = n2
- f(n) = kn3, kde k je libovolné přirozené číslo
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, ...).
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
- A je abeceda
- P je množina pravidel, která pro každý znak a z abecedy A obsahuje
právě jedno pravidlo nad abecedou A tvaru a -> u
- w je slovo ze A, které nazýváme axiom
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
- w1 = w
- jestliže wi=a1a2...an,
potom wi+1=u1*u2*...*un,
kde aj -> uj jsou pravidla z množiny pravidel P
pro j=1,2,...,n
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.
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říklad
- {a,b} je abeceda obsahující dva znaky: a a b.
- Délka slova aabab je 5.
- Zřetězením slov ab a aab je slovo ab*aab=abaab.
- Nad touto abecedou můžeme vytvořit nekonečně mnoho slov:
_, a, b, aa, ab, bb, aaa, ...
- Pravidlem je například a -> aa.
- D0L systémem je například ({a,b}, {a -> aa,b -> ab}, ab).
- Posloupnost produkovaná tímto systémem je
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, ...).
- Růstová funkce tohoto D0L systému je f(n)=2n.
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.