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:
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`
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`
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`
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`
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 `
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.
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`
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`
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`
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`
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`