Písomná skúška na prijímacích pohovoroch z Informatiky
- Variant C - 1999
-
Nasledujúca časť programu triedi n-prvkové a pole čísel pomocou
algoritmu bublinkového triedenia. Predpokladajme, že manipulácia s prvkami
poľa je časovo veľmi náročná operácia – každá odvolávka na prvok poľa trvá
jednu stotinu sekundy, napr. testovanie a[j]>a[j+1] trvá 2 stotiny
sekundy. Zvyšné príkazy v programovacom jazyku trvajú nulový čas.
{načítanie n a n-prvkového poľa a}
for i:=1 to n do
for j:=1 to n-i do
if a[j]>a[j+1] then
begin
k:=a[j];
a[j]:=a[j+1];
a[j+1]:=k;
end;
-
Spočítajte, ako dlho program bežal pre n=100 a n-prvkové
vzostupne utriedené pole a (všetky prvky v poli sú navzájom rôzne).
-
Spočítajte, ako dlho program bežal pre n=100 a n-prvkové zostupne
utriedené pole a (všetky prvky v poli sú navzájom rôzne).
-
Zistite, ako dlho bude program bežať pre n=5 a hodnoty prvkov poľa
(3,1,2,5,4).
-
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 všetky čísla, v ktorých sú všetky cifry v päťkovej sústave
rôzne a sú deliteľné číslom 11105.
Výsledok uveďte v päťkovej sústave. Výsledné číslo nemusí obsahovať všetky
cifry.
-
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.
Teraz si pozrime postupnosť slov, ktorá vznikla tak, že každé ďalšie
slovo vzniklo transformovaním podľa nejakého pravidla z predchádzajúceho
slova v postupnosti:
xAABB => xaABB => xAaBB => xABaB => xABBa => xaBBa => xBaBa =>
xBBaa =>
=> xbBaa => xBbaa => xbbaa
-
Navrhnite čo najmenšiu množinu prepisovacích pravidiel, ktorá zodpovedá
daným transformáciám. Pritom ľavé strany pravidiel sú vždy aspoň 2 znakové
reťazce písmen.
-
Zistite, ako sa pretransformuje slovo xABBAABAB podľa týchto prepisovacích
pravidiel.
-
Zistite, aká je dĺžka transformačnej postupnosti slov, ktorá začína písmenom
'x', za ktorým nasleduje 130 písmen 'A'.
-
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 rovnostranných trojuholníkov so stranami
30. Tieto trojuholníky sú nakreslené pod sebou, pričom vrchol nižšieho
sa dotýka stredu strany vyššieho trojuholníka. Obrázok nakreslite jedným
ťahom tak, aby pero neprešlo viackrát po tej istej čiare. N je načítaná
vstupná hodnota, ktorá je väčšia ako 1.