2. Prvé prototypy

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Peťovi na [email protected]

Vedci v Bajtlandí sa snažia skonštruovať prvý prototyp Bajtlandského počítača, ale zatiaľ sa im v tom príliš nedarí. Už však vynašli jednoduché stroje, ktoré dokážu pracovať s páskami so 16 ciframi. V Bajtlandii poznajú iba jednotky a nuly a preto si každú pásku môžete predstaviť ako postupnosť 16 jednotiek a núl. Stroje fungujú tak, že do nich vložíte jednu alebo dve pásky a oni vytlačia novú pásku.

Zatiaľ vedci vynašli štyri typy strojov:

& – AND – stroj:

Do tohto stroja vložíte dve pásky a stroj vytlačí pásku, kde bude 1 iba na tej pozícii, kde bola 1 v oboch páskach. Na ostatných miestach bude 0.

Príklad: Do stroja vložíme pásku A a pásku B:

Páska A:                0011100111101101
Páska B:                1010010101010110
Stroj vytlačí pásku:    0010000101000100

! – NOT – stroj:

Do tohto stroja vložíte jednu pásku a stroj vytlačí pásku, v ktorej je každá 1 vymenená za 0 a každá 0 vymenená za 1.

Príklad:

Do stroja vložíme pásku:    0100011010100101
Stroj vytlačí pásku:        1011100101011010

<< – LSHITF – stroj:

Do tohto stroja vložíte jednu pásku a ešte kladné číslo \(k\). Stroj potom posunie každú cifru na páske o \(k\) pozícií doľava, vynechá prvých \(k\) cifier a posledných \(k\) cifier zaplní nulami.

Príklad:

k=5:
Do stroja vložíme pásku:         1011010001011110
Posunutie:                  1011010001011110
Stroj vytlačí pásku:             1000101111000000

>> – RSHITF – stroj:

Podobný ako stroj LSHIFT. Opäť doňho vkladáme jednu pásku a kladné číslo \(k\). Stroj potom posunie každú cifru o \(k\) pozícií doprava, vynechá posledných \(k\) cifier a prvých \(k\) cifier zaplní nulami.

Príklad:

k=5:
Do stroja vložíme pásku:         1011010001011110
Posunutie:                            1011010001011110
Stroj vytlačí pásku:             0000010110100010

Spájanie

Bajtlandskí vedci dokážu spájať rôzne stroje dokopy, čím dokážu vyrábať komplikovanejšie prístroje. Takéto spájania potom zapisujú formou jednoduchého programu. Napríklad nasledujúci program zoberie dve pásky A a B, postupne vyrobí pásky C, D a E a pásku E vytlačí ako výsledok.

Príklad:

C= !B               //použi stroj NOT na pásku B. Výslednú pásku nazvi C
D= A & C            //skombinuj pásku C a A pomocou stroja AND. Výslednú pásku nazvi D
E= !D               //použi stroj NOT na pásku D. Výslednú pásku nazvi E
Vytlač E            //stroj vytlačí finálnu pásku E

Na novo vytlačenej páske bude 0 práve na tých pozíciach, kde bola na páske A 1 a na páske B 0, na ostatných bude 1.

Stroje môžu používať aj dopredu vyrobené pásky. Napríklad, keď by sme chceli spraviť stroj, ktorý načíta pásku A a vytlačí pásku, kde sa každá 1 v posledných 8 číslach zmení na 0, tak to vieme spraviť aj nasledovne:

B= (0000000011111111) << 8  //v premenej B bude páska posunutá o osem miest,
                            //teda 1111111100000000
C= A & B                    //v premennej A je vstupná páska
Vytlač C 

Úloha

K dispozícii máte štyri základné stroje !, &, <<, >> a ľubovoľné konštantné pásky (pozri posledný príklad). Vašou úlohou je s ich pomocou vyrobiť niekoľko komplikovanejších prístrojov. Pre každú podúlohu napíšte program, ktorý popisuje ako zostaviť požadovaný prístroj a tiež pridajte aspoň krátky slovný popis, prečo je vaše riešenie správne.

“Programovací jazyk”, v ktorom píšete stroje nie je presne daný. Skúste používať niečo podobné tomu, čo ste videli v predchádzajúcich príkladoch. Aj dostatočný slovný popis, ako poskladať žiadaný stroj však bude postačujúci. Hlavne nech je jasné, ako ste to robili.

a) (2 body) OR – stroj

Do stroja vložíte dve pásky A a B. Výstupná páska má mať 0 na tých pozíciách, na ktorých mali obe pásky A a B 0, a 1 na zvyšných.

Príklad:

Do stroja vložíme pásku A a pásku B:

Páska A:                0011100100100010
Páska B:                1010010110101101
Stroj vytlačí pásku:    1011110110101111

b) (2 body) XOR – stroj

Dnu vložíme dve pásky A a B. Výstupná páska bude mať 1 na tých pozícicáh, na ktorých sa pásky A a B líšili a 0 na tých, kde boli rovnaké.

Príklad:

Do stroja vložíme pásku A a pásku B:
Páska A:                0011100100100010
Páska B:                1010010110101101
Stroj vytlačí pásku:    1001110010001111

c) (3 body) SEL – stroj

Máte pásku A a číslo \(k\). Vytvorte stroj, ktorý zmení všetky 1, okrem tej na \(k+1\)-vej pozícii, na 0. Ak na pozícii \(k+1\) nie je 1, výstupom bude páska so samými 0.

Príklady:

k=5:
Do stroja vložíme:             1110010111100101
Stroj vytlačí pásku:           0000000000100000

k=3:
Do stroja vložíme:             1110010111100101
Stroj vytlačí pásku:           0000000000000000

d) (4 body) RAO – stroj

Vytvorte stroj, ktorý zoberie jednu pásku A a zmení všetky 1, ktoré nesusedia s inou 1, na 0.

Príklad:

Vstup:   1110010111101101
Výstup:  1110000111101100

e) (4 body) RM – stroj

Stroj dostane pásku A. Následne z každého súvislého úseku 1 nechá iba tie na okrajoch a zvyšné zmení na 0. Môžete predpokladať, že prvá aj posledná cifra pásky je 0.

Príklad:

Vstup:   0110010111101110
Výstup:  0110010100101010