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:

  1. Každá konečná posloupnost číslic je N-výraz, jehož hodnotou je nezáporné celé číslo zapsané touto posloupností.
  2. 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.
Napište program, který přečte ze vstupu posloupnost znaků, zjistí, zda se jedná o N-výraz, a v kladném případě vytiskne jeho hodnotu.

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 AZ, 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)
  • podmínka jest:
    • buď výraz = výraz
    • nebo výraz < výraz
    • nebo výraz > 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 AZ a 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:

  1. 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.
  2. 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.