2001 variant D

  1. Daná je časť programu:
    1. Zistite, čo vypíše tento program pre n=4.
    2. Zistite, čo vypíše tento program pre n=8.

    Poznámka: Pomôže Vám, keď budete všetky výpočty robiť v 3-ovej sústave.

  1. Máme rad N žiaroviek - každá z nich buď svieti (je v stave 1) alebo je zhasnutá (je v stave 0). Okrem týchto žiaroviek máme jedno tlačidlo, ktoré je naprogramované tak, že vždy, keď ho stlačíme, vykoná takúto činnosť: nájde pozíciu najľavejšej rozsvietenej žiarovky a zapamätá si ju ako i; potom nájde pozíciu najpravejšej zhasnutej žiarovky a zapamätá si ju ako j. Ak také pozície existujú a i<j, potom i-tu žiarovku zhasne a j-tu rozsvieti. Zrejme po každom stlačení tlačidla sa môže niektorá žiarovka rozsvietiť a niektorá iná zhasnúť, ale celkový počet svietiacich žiaroviek sa nezmení. V niektorých situáciách stlačenie tlačidla už nič nemení (hovoríme tomu stabilný stav).
    1. Zistite, koľko existuje rôznych stabilných stavov pre N=20.
    2. Pre počet žiaroviek N=10 zistite, koľko existuje rôznych počiatočných stavov, z ktorých po jednom stlačení tlačidla sa stane stabilný stav.
    3. Navrhnite taký počiatočný stav dvadsiatich žiaroviek (N=20), aby na dosiahnutie stabilného stavu bol potrebný maximálny možný počet stlačení. Koľko stlačení bude treba? (Ak takých riešení existuje viac, stačí, ak uvediete jedno.)
  1. Mravec Ferdo sa pohybuje na štvorčekovom papieri a my ho pozorujeme. Všetky jeho pohyby si zapisujeme takto: keď sa presunie na susedný štvorček v tom smere, v ktorom je práve otočený, zapíšeme písmeno D (dopredu), keď sa otočí vľavo o 90 stupňov, zapíšeme L a pri otočení vpravo o 90 stupňov zapíšeme písmeno P. Napr. zápis DDPDPDDPD znamená, že mravec navštívil 6 rôznych políčok, pričom sa vrátil na pôvodné miesto. Opakujúce sa časti v zápise môžeme skrátiť, napr. 4(100DL) znamená, že 4-krát sa opakuje 100 krokov dopredu a jedno otočenie vľavo (jeho trasa je štvorec so stranou 100 štvorčekov).
    1. Koľko rôznych políčok navštívil, ak prešiel DL1DPP1DL DL2DPP2DL DL3DPP3DL ... DL9DPP9DL? (tromi bodkami vyjadrujeme, že ďalej sa stále opakuje ten istý zápis DLxDPPxDL, ale stále s väčšími a väčšími čislami). Počítame aj štartové políčko.
    2. Predchádzajúci zápis by sme mohli skrátene zapísať 9(DLxDPPxDL), v ktorom písmeno x vyjadruje číslo - poradové číslo opakovania (prechodu) cyklom. Zistite, koľko rôznych políčok navštívi mravec, ak prešiel trasu 4(4(DLDPPxDPPxDP)L) - x sa vzťahuje len na najvnútornejší cyklus. Nakreslite výsledný útvar.
  1. Predpokladajme, že v programovacom jazyku máme definovanú procedúru bod s troma celočíselnými parametrami x, y a farba, ktorá nakreslí do grafickej plochy obrazovky na zadané súradnice farebnú bodku. Ľavý horný roh obrazovky má súradnice (0,0). V programovacom jazyku už nemáme ďalšie procedúry na kreslenie do grafickej plochy.
    Napíšte program, ktorý nakreslí takýto pravouhlý rovnoramenný trojuholník: prepona je rovnobežná s x-ovou osou a má dĺžku N bodov (ľavý vrchol prepony nech má súradnice (50,150)); zrejme obe odvesny zvierajú s preponou 45 stupňový uhol. Trojuholník je vyplnený červenou farbou (farba=1) a jeho obvod je modrý (farba=2).
    Hodnota N je konštanta programu - môžete predpokladať, že nepárna, napr. N=191. Úlohu riešte všeobecne pre ľubovoľné nepárne N.
    Môžete použiť ľubovoľný programovací jazyk, ktorý ste používali na strednej škole.

© AB