Písomná skúška na prijímacích pohovoroch z Informatiky - Variant C - 1999
  1. 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;
    1. 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).
    2. 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).
    3. Zistite, ako dlho bude program bežať pre n=5 a hodnoty prvkov poľa (3,1,2,5,4).
  1. 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.
  1. 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
    1. 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.
    2. Zistite, ako sa pretransformuje slovo xABBAABAB podľa týchto prepisovacích pravidiel.
    3. Zistite, aká je dĺžka transformačnej postupnosti slov, ktorá začína písmenom 'x', za ktorým nasleduje 130 písmen 'A'.
  1. 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.