2001 variant C

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

    Poznámka: Pomôže Vám, keď budete všetky výpočty robiť v 2-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é takto: vždy, keď ho stlačíme, nájde všetky trojice za sebou idúcich žiaroviek, ktoré buď všetky tri svietia alebo sú všetky tri zhasnuté a po pustení tlačidla niektoré z týchto žiaroviek buď zhasnú alebo sa rozsvietia. Pravidlo je takéto: keď tri za sebou idúce žiarovky svietili, tak stredná z nich po pustení zhasne; keď boli tri za sebou idúce žiarovky zhasnuté, tak najpravejšia z nich sa rozsvieti. Treba si uvedomiť, že toto sa robí naraz so všetkými trojicami (trojíc je N-2). Napr. pre N=5 a stavy 00000 sa po jednom stlačení zmení stav na 00111 a po ďalšom stlačení tlačidla 00101. V niektorých situáciách stlačenie tlačidla už nič nemení (hovoríme tomu stabilný stav).
    1. Pre N=20 zistite, koľko existuje rôznych stabilných stavov s maximálnym možným počtom rozsvietených žiaroviek. Vypíšte aspoň jedno takéto riešenie.
    2. Pre počet žiaroviek N=6 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. Je zaujímavé, že z každého počiatočného stavu sa po niekoľkých stlačeniach tlačidla stane stabilný stav. Pre N=10 zistite, do akého stabilného stavu sa dostanú všetky rozsvietené žiarovky a do akého stabilného stavu sa dostanú všetky zhasnuté žiarovky.
  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 20(6(2DP)2(DP))?
    2. Mravec prešiel zaujímavú trasu: štvorec so stranou 80, pričom v každom vrchole prešiel ešte aj malý štvorec so stranou 10 (dotýka sa zvonku jedným rohom veľkého štvorca). V zápise tejto trasy niekto nahradil niektoré písmená D, P a L znakom x a niektoré čísla (aj viacciferné) znakom y a dostali sme: y(Pyx2(xyx)). Správne zostavte túto trasu.
  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í N sústredných štvorcov, ktorých strany sú rovnobežné so súradnými osami. Najmenší štvorec má veľkosť strany 20 bodov a každý ďalší je o 20 bodov väčší. Najmenší štvorec je vyplnený farbou číslo 1, ďalší farbou číslo 2, ďalší farbou 3 atď. Keďže sa štvorce prekrývajú, z väčšieho štvorca vidíme len "pás" okolo menšieho.
    Hodnota N je konštanta programu, napr. N=8. Úlohu riešte všeobecne pre ľubovoľné N.
    Môžete použiť ľubovoľný programovací jazyk, ktorý ste používali na strednej škole.

© AB