Písomná skúška na prijímacích pohovoroch z Informatiky
- Variant D - 1999
-
Nasledujúci program načíta nejaké celé číslo n a vypočíta hodnotu
i. Všimnite si, že používa príkazy dec a inc, ktoré
znížia, resp. zvýšia hodnotu premennej o 1. Tieto príkazy v počítači
trvajú jednu stotinu sekundy. Priraďovacie príkazy trvajú dve stotiny sekundy.
Predpokladáme, že zvyšné príkazy v programovacom jazyku trvajú nulový čas.
var n,i,j,k:longint;
begin
readln(n);
i:=0; k:=-1;
while n>=0 do
begin
inc(i); inc(k); inc(k); j:=k;
while j>0 do begin dec(n); dec(j)
end
end;
dec(i);
writeln(i)
end.
-
Spočítajte, ako dlho program bežal pre n=123.
-
Zistite, pre aké najmenšie n bude program bežať viac ako sekundu.
-
Jeden tanzánijský kmeň ešte stále používa päťkovú číselnú sústavu. Vyriešte
príklad, ktorý sme vybrali z ich učebnice matematiky pre základnú školu
(POZOR! všetky konštanty sú v päťkovej sústave):
Nájdite najmenšie číslo x (x>0), pre ktoré číslo 123405
* x + 245 obsahuje v päťkovej sústave len párne cifry!
Označte, či výsledok uvádzate v desiatkovej alebo v päťkovej sústave.
-
Postupnosť písmen môžeme transformovať pomocou prepisovacích pravidiel.
Napr. pravidlo AB -> BA označuje, že ak sa v postupnosti za sebou vyskytuje
dvojica písmen AB, tak sa môže nahradiť dvojicou BA. Ak je daných viac
pravidiel, nezáleží na poradí, v akom sa budú aplikovať. Danú postupnosť
písmen budeme transformovať dovtedy, kým sa dá použiť niektoré z daných
pravidiel. Jeden krok transformácie zapisujeme slovo1 => slovo2, kde slovo2
vzniklo aplikovaním niektorého pravidla na slovo1. Symbolom =>* označíme,
že sme pravidlá aplikovali dovtedy, kým sa dalo a z počiatočného slova
sme získali výsledné.
Stratila sa nám postupnosť prepisovacích pravidiel, zachovalo sa len
niekoľko "pretransformovaných" slov a ľavé strany týchto pravidiel. Doplňte
chýbajúce časti prepisovacích pravidiel. Prepisovacie pravidlá navrhnite
tak, aby žiadna pravá strana prepisovacieho pravidla neobsahovala rovnaké
písmená (napr. pravidlo ab -> bb nie je prípustné).
-
aabbab =>* x; ab->?, ax->??, bx->??, xx->?
-
Navrhnite také 10 a 14 písmenové vstupné slová obsahujúce len písmená 'a'
a 'b', ktoré sa pretransformujú na písmeno 'x' (podľa prepisovacích pravidiel
z príkladu a). V rámci každého vstupného slova sa žiaden podreťazec
dĺžky 4 nevyskytuje viackrát.
-
Predpokladajme, že v programovacom jazyku je zadefinovaná procedúra vektor
s dvoma reálnymi parametrami: uhol a dĺžka. Táto procedúra na obrazovke
nakreslí úsečku zadanej dĺžky z momentálnej pozície pera, ktorá zviera
s y-ovou osou zadaný uhol. Po nakreslení úsečky pero zostane v koncovom
bode úsečky a kreslenie pokračuje ďalej od tohto bodu. Veľkosť uhla zadávame
v stupňoch a meriame v smere otáčania hodinových ručičiek (sever je uhol
0). Predpokladáme, že v programovacom jazyku už nie sú žiadne ďalšie grafické
príkazy. Pero je na začiatku v strede obrazovky.
Napíšte program (v ľubovoľnom programovacom jazyku, ktorý ste používali
na strednej škole), ktorý nakreslí N štvorcov ležiacich tesne vedľa seba
so stranami 10, 20, 30, ... 10*N. Štvorce ležia na spoločnej podstave a
dotýkajú sa. N je načítaná vstupná hodnota, ktorá je väčšia ako 1.