Druhá série druhého ročníku KSP
Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.Zadání úloh
2-2-1 Ďábelské mocniny
Napište program, který k zadanému celému číslu n vytiskne prvních n kladných celých čísel takových, že se dají vyjádřit jako součin mocnin 3i4j5k, kde i,j,k≥ 0 jsou celá čísla.
Příklad: Pro n=10 program vytiskne čísla 1 3 4 5 9 12 15 16 20 25.
2-2-2 Sčítancové
Napište program, který k zadané posloupnosti kladných celých čísel vytiskne rostoucí posloupnost (navzájem různých!) všech takových čísel, která vzniknou sečtením některých dvou čísel obsažených v zadané posloupnosti.
Například pro posloupnost 2 11 1 3 2 program vypíše posloupnost 2 3 4 5 6 12 13 14 22, neboť 2=1+1, 3=1+2, 4=2+2, 5=2+3, 6=3+3, 12=1+11, 13=2+11, 14=3+11, 22=11+11.
Předpokládejte, že zadaná posloupnost se vejde do paměti, ale výsledná se vejít nemusí (může totiž obsahovat až kvadraticky víc prvků než zadaná posloupnost).
2-2-3 Nechutné výrazy
Některé posloupnosti znaků nazveme N-výrazy (nechutnými výrazy) a přiřadíme jim určité celé číslo jako jejich hodnotu:
- Každá konečná posloupnost číslic je N-výraz, jehož hodnotou je nezáporné celé číslo zapsané touto posloupností.
- Jsou-li V a W dva N-výrazy, pak také:
- +(V,W) je N-výraz, jehož hodnotou je součet hodnot N-výrazů V a W
- -(V,W) je N-výraz, jehož hodnotou je rozdíl hodnot N-výrazů V a W
- *(V,W) je N-výraz, jehož hodnotou je součin hodnot N-výrazů V a W
- Je-li hodnota N-výrazu W různá od nuly, je /(V,W) N-výraz, jehož hodnotou je celočíselný podíl hodnot N-výrazů V a W, což je největší celé číslo menší nebo rovné podílu hodnot V a W.
Příklad: Posloupnost +(*(5,/(6,3)),-(1,4)) je N-výrazem a má hodnotu 7.
2-2-4 Mlaskal
Programovací jazyk MLASKAL'89 je jednoduchý jazyk algolského
typu. Programy v MLASKALu'89 pracují pouze s celými čísly
z rozsahu -32767 až 32767. Mají k dispozici 26 celočíselných
proměnných označených A až Z, které mají při spuštění programu
nulovou hodnotu.
Syntaxe a sémantika jazyka MLASKAL'89:
- program jest posloupnost_příkazů
- posloupnost_příkazů jest jeden nebo více příkazů zapsaných za sebou
- příkaz jest:
- buď proměnná
=výraz (vyhodnotí výraz a výsledek dosadí do proměnné) - nebo
[podmínka posloupnost_příkazů](while-cyklus – vyhodnotí podmínku, je-li splněna, vykoná posloupnost příkazů a opakuje totéž od začátku; není-li splněna, vykonávání příkazu končí) - nebo
}proměnná (načte ze vstupu celé číslo do proměnné) - nebo
{proměnná (vypíše na výstup hodnotu proměnné) - anebo (prázdný příkaz, nedělá nic)
- buď proměnná
- podmínka jest:
- buď výraz
=výraz - nebo výraz < výraz
- nebo výraz > výraz
- buď výraz
- výraz jest:
- buď operand
- nebo operand operátor operand
- operand jest buď proměnná nebo číslo
- operátor jest buď
+nebo-nebo*nebo/(/znamená celočíselné dělení, výsledkem je největší celé číslo menší nebo rovné podílu operandů) - proměnná jest jedno z písmen
AažZa označuje proměnnou, která může obsahovat celé číslo od -32767 do 32767. - číslo jest neprázdná posloupnost číslic od 0 do 9, která je desítkovým zápisem hodnoty od 0 do 32767.
Kdekoli uvnitř programu se mohou vyskytnout mezery a konce řádků. Jejich přítomnost nikterak neovlivňuje běh programu.
Následující programu v MLASKALu'89 načte ze vstupu dvě čísla a jsou-li kladná, vytiskne jejich největšího společného dělitele spočítaného Eukleidovým algoritmem:
}X }Y
[X>0 [Y>0
[X>0
[Y>X Z=X X=Y Y=Z]
X=X-Y
]
{Y
Y=0
] ]
Úlohy:
- Napište interpret jazyka MLASKAL'89, tj. program, který načte ze vstupu program v jazyku MLASKAL'89 a provede ho. Interpret by měl rozpoznat a ohlásit co nejvíce chyb – syntaktických, aritmetických apod.
- Navrhněte (nemusíte programovat) rozšíření MLASKALu'89 o procedury bez parametrů s lokálními proměnnými tak, aby zůstal zachován „mlaskalský“ duch jazyka.