Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Peťovi na peto159@gmail.com

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

Podúloha a) (2 body) OR – stroj

Keď sa snažíme pracovať s logickými hradlami alebo funkciami, často sa nám oplatí napísať si celú tabuľku hodnôt pre hľadané hradlo a nájsť podobnosti s hradlami, ktoré poznáme. Vieme, že hradlo OR má vrátiť nulu iba v tom prípade, ak sú obe vstupné hodnoty rovné 0. Inak vráti hodnotu 1. To sa trochu podobá na hradlo AND, ktoré vráti 1 iba v jedinom prípade – keď sa obe vstupné hodnoty rovnajú 1.

Ak znegujeme výsledok AND, podobnosť s hradlom OR je ešte výraznejšia, pretože negovaný AND (nazývaný tiež NAND) vracia 0 iba v jedinom prípade, presne tak, ako hradlo OR. Akurát tie prípady sú odlišné. OR na to potrebuje dve nuly, ale NAND dve jednotky. Ako teda zaručíme, aby ak naše hradlo dostane dve 0, náš znegovaný AND dostal dve 1? Jednoducho obe vstupné hodnoty znegujeme.

Celé hradlo preto vyzerá nasledovne: znegované vstupné hodnoty vložíme do hradla AND, ktorého výsledok nakoniec tiež znegujeme.

Páska A:            0011100100100010
Páska B:            1010010110101101
C=!A                1100011011011101 
D=!B                0101101001010010
E=C&D               0100001001010000
F=!E                1011110110101111
Vytlač F:           1011110110101111

Alebo v skratke F=!((!A) & (!B)).

Podúloha b) (2 body) XOR – stroj

Jednotka bude na tých pozíciách, kde sa čísla na páskach líšili. A to bude tam, kde bude buď na páske A \(1\) a zároveň na páske B nebude \(1\), alebo keď bude na páske B \(1\) a zároveň na páske A \(1\) nebude.

Všimnime si zvýraznené slová v tomto popise. Tie predsa priamo zodpovedajú strojom ktoré máme – “a zároveň” je stroj AND a “alebo” je stroj OR. A ak chceme zistiť, na ktorých pozíciách nie je \(1\), zistíme to pomocou stroja NOT.

Správne sformulované zadanie nám teda presne popisuje, ako sa dostaneme k výsledku a túto formuláciu stačí prepísať do kódu:

Páska A:            0011100100100010
Páska B:            1010010110101101
C=!A                1100011011011101 (kde v A nie je 1) 
D=!B                0101101001010010 (kde v B nie je 1)
E=A&D               0001100000000010 (v A je 1 a v B nie je 1)
F=B&C               1000010010001101 (v B je 1 a v A nie je 1)
G=E|F               1001110010001111
Vytlač G:           1001110010001111

Alebo v skratke G=(A&!B) OR (!A&B)

Podúloha c) (3 body) SEL – stroj

Ak chceme vynulovať niektoré políčka na páske, najlepšie je spraviť AND s páskou, ktorá má nuly, práve na tých miestach, ktoré chceme vynulovať. Tento stroj chce vynulovať všetky pozície, okrem jednej konkrétnej (\(k+1\) z pravej strany). Na tejto pozícii teda chceme mať 1, ktorá zaručí, že po operácii AND ostane na tejto pozícii pôvodná hodnota. No a pásku, ktorá obsahuje 1 iba na \(k+1\) pozícii vyrobíme najľahšie pomocou stroja LSHIFT.

Výsledný program je teda C = (1<<k)&A.

Pre \(k=3\) to teda môže vyzerať takto:

k=3
Páska A:            1110010111100101
B=1<<k              0000000000001000
C=B&A               0000000000000000 
Vytlač C:           0000000000000000

Prípadne pre \(k=5\):

k=5
Páska A:            1110010111100101
B=1<<k              0000000000100000
C=B&A               0000000000100000
Vytlač C:           0000000000100000

Podúloha d) (3 body) RAO – stroj

Pri riešení tejto úlohy si musíme uvedomiť, akú podmienku vlastne kontrolujeme. Jednotka bude na tých pozíciach, kde už bola predtým, a zároveň bola 1 buď napravo alebo naľavo od danej pozície. Uvedomme si, že ak posunieme celú pásku o 1 doprava a túto pásku spojíme strojom AND s pôvodnou páskou A tak 1 ostanú na tých pozíciách, kde boli 1 pôvodne a zároveň mali 1 napravo od seba.

Rovnakú myšlienku vieme samozrejme použiť aj na smer vľavo. Výsledné riešenie dostaneme spojením týchto dvoch možností strojom OR.

Páska A:            1110010111100101
B=A<<1              1100101111001010 (posunutie doľava)
C=A>>1              0111001011110010 (posunutie doprava)
D=A&B               1100000111000000 (pozície s 1, ktoré majú 1 aj napravo od seba)
E=A&C               0110000011100000 (pozície s 1, ktoré majú 1 aj naľavo od seba)
F=D|E               1110000111100000
Vytlač E:           1110000111100000

Alebo v skratke: E=((A<<1)&A) | ((A>>1)&A)

Podúloha e) (3 body) RM – stroj

Budeme postupovať podobne ako v predchádzajúcej úlohe. Najprv si uvedomíme, že jednotka je na okraji práve vtedy, keď nemá jednotky na oboch stranách. Rovnako ako v predchádzajúcej úlohe to, či je jednotka napravo alebo naľavo, zistíme posunutím pásky o jednu cifru doprava alebo doľava.

Ak tieto dva posuny dáme dokopy pomocou AND, dostaneme všetky pozície 1, ktoré majú 1 na oboch stranách. My sa však práve týchto jednotiek chceme zbaviť a preto túto pásku znegujeme. Následne ju spojíme s pôvodnou páskou A, čím dostaneme výsledok.

Páska A:            0110010111101110
B=A<<1              1100101111011100
C=A>>1              0011001011110111
D=B&C               0000001011010100 (1 je na pozíciách ktoré mali z oboch strán 1)
E=!D                1111110100101011 
F=A&E               0110010100101010 
Vytlač F:           0110010100101010

Alebo skrátene F=(!((A<<1) & (A>>1))) & A

A ako toto súvisí s počítačmi?

V počítači sa čísla ukladajú v binárnej sústave ako postupnosť núl a jednotiek. Tento fakt už, ako programátori takmer nevnímame, pretože počítač nám ich vypisuje v desiatkovej sústave. Napriek tomu však s číslami vieme pracovať aj v ich binárnej reprezentácii, a to pomocou funkcií podobných tým v tejto úlohe.

Pomerne bežne sa stáva, že znalosť týchto funkcií a toho, ako fungujú vám pomôže pri riešení nejakého problému. Jednou z veľa výhod napríklad je, že tieto binárne operácie sú naozaj rýchle1.

Najčastejšie používané sú nasledovné funkcie udané aj s bežným označeným:

& - AND
| - OR
^ - XOR
~ - NOT
<< - posuvanie dolava
>> - posuvanie doprava

Keby sme si chceli posledný príklad prepísať do Pythonu vyzeralo by to nasledovne:

A= int ('0110010111101110', 2) #nacitaj cislo v dvojkovej sustave
B=A<<1
C=A>>1
D=B & C
E=~D
F=A&E
print (bin(F)) #vypis v dvojkovej sustave

Program vypíše: 0b110010100101010

0b označuje, že číslo vypisujeme v binárnej sústave. Oproti našej páske tam chýba 0 na začiatku. Tá sa však nevypisuje z rovnakých dôvodov, z akých v desiatkovej nepíšeme 0572.

Keby sme si chceli posledný príklad prepísať do C++, vyzeralo by to nasledovne:

#include <iostream>
#include <string>
#include <cstdlib>
#include <bitset>
using namespace std;
int main()
{
    string s = "0110010111101110"; 
    int A = (int) strtol(s.c_str(), NULL, 2);  //zmena retazca v dvojkovej sustave na cislo
    int B = A<<1;
    int C = A>>1;
    int D = B&C;
    int E = ~D;
    int F = A&E;
    cout<<bitset<16>(F)<<endl; //vypis ako cislo v dvojkovej sustave, tak aby malo 16 cifier
}

  1. Čo vedie k situáciám, kde namiesto násobenia 2 používame <<1. Výsledok je ten istý, akurát druhý spôsob je oveľa rýchlejší. Našťastie takéto optimalizácie za vás často krát spraví aj kompilátor.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

  • Eliška Macáková

    8. december 2016 19:50

    Dakujem za zaujimavu ulohu, pacil sa mi aj vzorak :)