mff/14.6.2000/i      

Variant C

Prijímacie pohovory z informatiky

 

 

1.       V n-prvkovom celočíselnom poli a sa nachádzajú rôzne čísla z množiny {1,2,...,n}. Je daná časť programu:

  p:=0; m:=1;

  for i:=2 to n do

    if a[i]>a[m] then

      begin

        p:=m+p-i;

        m:=i

       end

    else if a[i]<a[m+p] then p:=i-m;

  writeln(p);

a)       Zistite, čo vypíše tento program, ak sa v poli pre n=15 nachádzajú čísla:

13, 4, 2, 5, 15, 7, 12, 8, 14, 9, 10, 1, 3, 6, 11

b)       Navrhnite také hodnoty do poľa a (pre čo najmenšie n), aby program vypísal číslo -13.

 

2.       V múzeu výpočtovej techniky sme objavili historickú celočíselnú kalkulačku, ktorá až na dve tlačidlá vôbec nefun­gu­je. Jedno tlačidlo má označenie [*3] a po jeho zatlačení sa číslo na dipleji vynásobí 3. Druhé tlačidlo [÷2] vydelí číslo na displeji dvoma - delenie je celočíselné, t.j. zvyšok po delení sa zanedbá. Na začiatku je na displeji číslo 5. Postupným stláčaním tlačidiel môžeme na displeji dosiahnuť rôzne výsledky.

a)       Ako dosiahneme na čo najmenší počet stlačení číslo 8?

b)       Na displeji je na začiatku číslo 5. Koľko rôznych výsledkov sa dá dosiahnuť na displeji, ak štyrikrát postupne stlačíme nejaké z tlačidiel [*3] a [÷2] (do úvahy berieme len čísla, ktoré sa dosiahli po štvrtom stlačení tlačidla)?

 

3.       V poznámkach jedného programátora sa našiel úryvok programu v zabudnutom programovacom jazyku A--. Podarilo sa nám rozlúštiť tieto pravidlá jazyka - všetky inštrukcie sa skladajú z troch častí:

·         kódu operácie (= priradenie,+,-,*,/ celočíselné delenie,% zvyšok po celočíselnom delení,<> test na nulu);

·         premennej, s ktorou sa vykoná operácia;

·         parametra (číslo alebo premenná), resp. pre reláciu <> je posledným parametrom návestie skoku.

Niektoré inštrukcie navyše začínajú návestím na skok - číslo, za ktorým je dvojbodka (označuje miesto v programe, na ktoré bude možné skočiť inštrukciou testu na nulu).

Napr. + x 7 znamená, že k x sa pričíta 7, <> x 1 znamená, že ak x sa nerovná 0, tak program pokračuje na návestí 1.

Máte daný nasledujúci program v jazyku A--:

= y 0 1: = z x + z 3 % z 10 * y 10 + y z / x 10 <> x 1

a)       Zistite, čo bude v premennej y po skončení programu, ak v premennej x bolo 4215.

b)       Zistite, pre akú vstupnú hodnotu x bude mať program po skončení v premennej y číslo 97531. Nájdite aspoň dve riešenia.

 

4.       Predpokladajme, že v programovacom jazyku máme definovanú procedúru daj s troma parametrami r, s a h, ktorá do špeciálnej dvojrozmernej tabuľky celých čísel zapíše do r-tého riadku a s-tého stĺpca jedno číslo h. Riadky aj stĺpce číslujeme od 1. V programovacom jazyku už nemáme ďalšiu procedúru na prečítanie hodnoty zo žiadneho políčka.

Napíšte program, ktorý túto tabuľku zaplní rôznymi číslami len s použitím procedúry daj podľa nasledujúceho návodu (číslovanie políčok po špirále):

·         v ľavom hornom rohu bude 1;

·         postupne budeme číslovať políčka najprv po obvode tabuľky v smere pohybu hodinových ručičiek;

·         stále sa budú zmenšovať rovné úseky čísel podľa toho ako zapĺňame tabuľku;

·         takto postupne očíslujeme celú tabuľku veľkosti NxN.

Zaplňte prvých N riadkov a N stĺpcov tabuľky číslami od 1 do N*N, pričom nesmiete použiť žiadne pomocné polia.

Môžete použiť ľubovoľný programovací jazyk, ktorý ste používali na strednej škole.

ÓAB