Třetí série první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

1-3-1 Pokrytí matice

Nechť A je celočíselná matice velikosti m ×n obsahující nuly a jedničky. Nechť linie je společný název pro řádky a sloupce. Množinu linií P nazveme pokrytím matice A, jestliže každý nenulový prvek matice A leží alespoň v jedné linii množiny P. Napište program, který vytiskne velikost nejmenšího pokrytí zadané matice.

Příklad: Pro matici

( 1 0 0 )
1 1 1
1 0 0

program vytiskne 2.

1-3-2 Král a dáma

Zadavatel hry postaví na některé pole šachovnice 8×8 černého krále. Řešitel, který na šachovnici nevidí, v každém kroku zvolí jedno pole. Zadavatel na toto pole na okamžik postaví bílou dámu a ohlásí:

  1. král je v šachu
  2. král není v šachu
  3. dáma stojí na témže poli jako král.
Úkolem řešitele je dosáhnout odpovědi c) (tzn. konce hry) co nejmenším počtem kroků.

Napište program umožňující hrát tuto hru v obsazení: zadavatel=člověk, řešitel=počítač.

1-3-3 Yaghobiánská osmička

Nechť A je matice velikosti 3×3 obsahující právě jednou každé z čísel 1, 2, … , 9. Tahem rozumíme takovou záměnu obsahu prvků Ai,j, Ak,l, pro kterou platí:

  1. Ai,j=9     a zároveň
  2. i=k ∧ |j-l |= 1 nebo j=l ∧ |i-k |= 1.
Seřazenou maticí rozumíme matici, pro kterou platí Ai,j=3(i-1)+j pro i,j=1,2,3. (Podobnost s Lloydovou patnáctkou není čistě náhodná.)

Napište program, jenž k zadané matici najde posloupnost tahů, které tuto matici převedou na seřazenou, a vytiskne indexy k, l všech tahů posloupnosti.

1-3-4 Interpret jazyka ZÁLIBY

Programovací jazyk ZÁLIBY pracuje s celými čísly z rozsahu 0 až 32767. Programy v něm napsané používají zásobník celých čísel. Zásobník je datová struktura se dvěma operacemi: přidání prvku a odebrání nejnovějšího prvku. Nejnovější prvek v zásobníku budeme označovat TOS, druhý nejnovější NOS. Program (posloupnost znaků) se skládá z následujících příkazů:

  1. Posloupnost číslic – uloží na zásobník hodnotu celého čísla daného touto posloupností číslic (dvě čísla vedle sebe se oddělují mezerou)
  2. Některý ze znaků +, -, *, / odebere ze zásobníku TOS a NOS a jejich součet (rozdíl, součin, podíl) uloží na zásobník, tzn. NOS+TOS →TOS, NOS-TOS →TOS, NOS·TOS →TOS, NOS/TOS →TOS, kde / znamená celočíselné dělení.
  3. = odebere TOS a NOS, porovná je a rovnají-li se, uloží na zásobník číslo 1, jinak 0.
  4. < odebere TOS a NOS, porovná je a je-li NOS<TOS, uloží na zásobník číslo 1, jinak 0.
  5. ; odebere TOS a dvakrát ho uloží na zásobník.
  6. ?:! (obdoba příkazu IF) se smí vyskytnout jen v kontextu:
    ? posloupnost příkazů : posloupnost příkazů !
    Odebere TOS a je-li nenulový, provede posloupnost příkazů mezi ? a :, je-li TOS nulový, provede posloupnost příkazů mezi : a !. Poté provádění programu pokračuje za !. Jsou-li příkazy ?:! vnořeny, vztahují se : a ! k nejbližšímu předcházejícímu ?.
  7. [@] (obdoba cyklu while) se smí vyskytnout pouze v kontextu:
    [ posloupnost příkazů @ posloupnost příkazů ]
    Provede posloupnost příkazů mezi [ a @ a pak odebere ze zásobníku TOS. Je-li nenulový, provede posloupnost příkazů mezi @ a ] a provádění programu pokračuje opět od [. Je-li TOS nulový, výpočet pokračuje za ]. Jsou-li příkazy [@] vnořeny, vztahují se @ a ] k nejbližšímu předcházejícímu znaku [.
  8. . odebere TOS a jeho hodnotu vytiskne.

Příkazy mohou (ale nemusí) být odděleny mezerami.

Příklad: Program 10[;@;;*.1-] vytiskne druhé mocniny celých čísel 10, 9, … , 1.

Úlohy:

  1. Napište program (tzv. interpret), který načte ze vstupu program v jazyce ZÁLIBY a provede ho. Zásobník je na začátku výpočtu prázdný. Interpret by měl rozpoznat nejrůznější druhy chyb, jako neznámý příkaz, výsledek aritmetické operace mimo stanovený rozsah apod.
  2. Zkuste jazyk ZÁLIBY rozšířit tak, aby se v něm už dalo něco naprogramovat.