Zadanie

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

Táto úloha naväzuje na úlohu Prvé prototypy z predošlej série. Predtým, než sa vrhnete na tento príklad vám preto odporúčame prečítať si zadanie z minulého kola.

Vedci v Bajtlandii spravili v poslednom kvartáli veľké pokroky. Aj vďaka vašej pomoci sa ich ponuka strojov výrazne rozrástla. Stroje stále pracujú so 16-cifernými páskami, ktoré obsahujú postupnosti jednotiek a núl. Každý stroj akceptuje jednu alebo dve pásky, ktoré spracuje a výsledok zapíše na novú pásku.

Počas Vianoc výskumníci nezaháľali a rozhodli sa svoje stroje naučiť počítať. Museli sa preto dohodnúť, ako pomocou pások zapisovať čísla. Rozhodli sa, že číslo \(b\) budú reprezentovať páskou, na ktorej sú najskôr samé 0 a potom presne \(b\) jednotiek, za ktorými už žiadne ďalšie znaky nenasledujú.

Inak povedané, v Bajtlandii počítajú v unárnej sústave. A hoci takýmto spôsobom vedia zapísať iba čísla od 0 po 16, zatiaľ im to bude stačiť.

Príklad:

Páska:  0000000000000111    (=3)
Páska:  0000000000000000    (=0)
Páska:  0000001111000000    toto nie je platné číslo
Páska:  1111111111111111    (=16)
Páska:  0101010101011111    toto nie je platné číslo

Nasledujúci stroj uvádza počítanie do praxe:

P – stroj:

Do tohto stroja vložíme jednu pásku a on vytlačí novú, ktorá vráti počet jednotiek na vstupnej páske. Stroj teda zarovná všetky jednotky doprava.

Príklad:

Do stroja vložíme pásku:    0100011010100101
Stroj vytlačí pásku:        0000000001111111 (=7)

Príklad: Použitie stroja P v programe:

B= P(A)                     // použi stroj P na pásku A a výsledok ulož do pásky B
C= (0000000011111111) << 8
D= B & C                    // skombinuj pásku B a C pomocou stroja AND
Vytlač D

Úloha

K dispozícii máte stroje z minulej úlohy (!, &, <<, >>, OR, XOR, SEL, RAO, RM) a navyše k nim pribudol nový stroj P. Môžete tiež používať pásky s konštantou (napr. ako v príklade vyššie pri priradení do C). Vašou úlohou je vytvoriť nové, komplikovanejšie stroje.

“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 postupovali.

a) (1 bod) NP – stroj

Do stroja vložíme jednu pásku A. Výstupná páska má obsahovať počet núl, ktoré A obsahuje.

Príklad:

Do stroja vložíme:      1111000111010000
Stroj vytlačí pásku:    0000000011111111 (=8)
b) (2 body) NULP – stroj

Stroj príjme jednu pásku A. Vašou úlohou je zistiť, koľko núl na páske A má napravo od seba ďalšiu nulu. Výstupná páska bude obsahovať tento počet.

Príklad:

Do stroja vložíme:      0011100100100010
Stroj vytlačí pásku:    0000000000011111 (=5)
c) (3 body) POL – stroj

Do stroja vložíme pásku A. Výstupom stroja POL je počet jednotiek na páske A vydelený dvomi. Ak sa na páske nachádza nepárny počet jednotiek, stroj zaokrúhli výsledok nadol.

Príklady:

Do stroja vložíme:      0011100100100010
Stroj vytlačí pásku:    0000000000000111 (=3)

Do stroja vložíme:      1001100110011110
Stroj vytlačí pásku:    0000000000001111 (=4)
d) (4 body) TRI – stroj

Súvislú časť jednotiek ohraničenú nulami alebo koncami pásky nazveme úsek. Vytvorte stroj, ktorý príjme pásku A a zistí, koľko úsekov dĺžky presne 3 obsahuje.

Príklad:

Do stroja vložíme:      1110011011101111
Stroj vytlačí pásku:    0000000000000011 (=2)
e) (5 bodov) NAJDL – stroj

Do stroja vložíme jednu pásku A. Výstupná páska bude obsahovať dĺžku najdlhšieho úseku jednotiek.

Príklad:

Vstup:   1100111011111011
Výstup:  0000000000011111 (=5)

Podúloha a) NP – stroj

Stroj sa veľmi podobá na stroj P zo zadania. Tento stroj ale vracia počet jednotiek, ktoré sú na vstupnej páske. Aby sme ho mohli použiť na vytvorenie stroja NP, potrebujeme na vstupnej páske vymeniť nuly za jednotky a naopak, jednotky za nuly. Na to slúži stroj NOT, ktorý poznáme z minulého kola.

Preto na vstupnú pásku použijeme stroj NOT a jeho výsledok vložíme do P.

Páska A:            0001110001101100
B = !A              1110001110010011
C = P(B)            0000000111111111 (=9)
Vytlač C:           0000000111111111 (=9)

Alebo v skratke C = P(!A).

Podúloha b) NULP – stroj

Najskôr vytvorme o niečo jednoduchší stroj, ktorý zistí, koľko \(1\) má napravo od seba ďalšiu \(1\). Pretože nás zaujíma, či je pravý sused ľubovoľnej \(1\) opäť \(1\), skúsme celú pásku posunúť o \(1\) doľava pomocou stroja LSHIFT, resp. <<.

Páska A:            1100100111101011
B = A << 1          1001001111010110

Všimnime si, že páska B je teraz páskou pravých susedov A – na \(i\)-tej pozícií obsahuje pravého suseda \(i\)-tej cifry z A. Pozície, na ktorých je 1 na oboch páskach, sú preto hľadaným riešením. Sú to totiž pozície, na ktorých je 1 (páska A), a zároveň má napravo od seba 1 (páska B). Na pásky A a B preto použijeme stroj AND, ktorý ponechá 1 iba na miestach, kde ich obsahovali obe pásky. Výsledok následne spočítame pomocou stroja P.

Páska A:            1100100111100011
B = A << 1          1001001111000110
C = A & B           1000000111000010
D = P(C)            0000000000011111 (=5)

Teraz sa vráťme k pôvodnej úlohe. Tou bolo zistiť počet \(0\), ktoré majú napravo od seba \(0\). Zjavne stačí prehodiť \(1\) a \(0\) a môžeme použiť riešenie uvedené vyššie. Na to použijeme opäť stroj NOT.

Páska A:            1100100111100011
B = !A              0011011000011100
C = B << 1          0110110000111000
D = B & C           0010010000011000
E = P(D)            0000000000001111 (=4)
Vytlač E

Alebo v skratke E = P(!A & (!A << 1))

Poznámka: Namiesto posunu doľava << sme mohli použiť aj posun doprava >>. Rozmyslite si, že na ľubovoľnej páske je rovnako veľa 0, ktoré majú napravo od seba 0, ako 0, ktoré majú naľavo od seba 0.

Podúloha c) POL – stroj

Najskôr zistíme počet \(1\) strojom P. Získané číslo potrebujeme vydeliť dvomi. Použijeme na to nasledovný trik: do stroja AND vložíme výstup P(A) a pásku \(1010101010101010\).

Páska A:                1001101011100100
B = P(A)                0000000011111111 (=8)
C = 1010101010101010    1010101010101010
D = B & C               0000000010101010
E = P(D)                0000000000001111 (=4)

Čo takýto stroj robí? Zo súvislého úseku jednotiek na páske B=P(A) vyberie iba tie na párnych pozíciách, teda polovicu z pôvodného počtu. Nakoniec ešte použijeme stroj P, aby sme tieto jednotky zarovnali doprava a vytvorili tak korektné číslo.

Iná predstava je, že pôvodné číslo rozdelíme na kôpky veľkosti \(2\), pretože ak páska D obsahuje na \(i\)-tej pozícií \(1\) znamená to, že páska B=P(A) obsahovala na \(i\)-tej a \(i + 1\) pozícií \(1\), ktoré spolu tvoria kôpku. Počet takýchto kôpok je potom pôvodné číslo vydelené dvomi.

Uvedomme si, že takéto riešenie navyše zaokrúhľuje nadol pri delení nepárnych čísel:

Páska A:                1000000011100100
B = P(A)                0000000000011111 (=5)
C = 1010101010101010    1010101010101010
D = B & C               0000000000001010
E = P(D)                0000000000000011 (=2)

Pri nepárnom čísle totiž najľavejšia jednotka na páske B vôbec neovplyvní výsledok. Je na nepárnej pozícií, pričom páska \(1010101010101010\)1 má na nepárnych pozíciách vždy \(0\). Ak by sme pri delení chceli zaokrúhľovať nahor, samozrejme by sme použili pásku 0101010101010101.

V skratke: E = P(P(A) & (1010101010101010))

Podúloha d) TRI – stroj

Najskôr musíme vymyslieť spôsob, ako rozpoznať úseky dĺžky \(3\). Všimnime si, že najľavejšia \(1\) ľubovoľného úseku dĺžky aspoň \(3\) musí mať cifru 1 o jednu aj dve pozícii napravo od seba. Niečo podobné sme už riešili v prvej podúlohe. Aby sme sa dostali k cifre o jedna napravo, posunuli sme celú pásku o jednu pozícii doľava (<< 1). Ak teda chceme cifry o dve pozície napravo, posunieme pásku o dve cifry doľava (<< 2).

Páska A:            1110011110011100
B = A << 1          1100111100111000 (susedia napravo)
C = A << 2          1001111001110000 (susedia o 2 pozície napravo)
D = A & B           1100011100011000 (pozície s 1, ktoré majú 1 aj napravo od seba)
E = D & C           1000011000010000 (pozície s 1, ktoré majú dve 1 napravo od seba)

Ak má páska E na \(i\)-tej pozícii \(1\), znamená to, že na pôvodnej páske A sú na pozíciách \(i\), \(i + 1\) a \(i + 2\) všade \(1\). V opačnom prípade by aspoň jedna z vymenovaných pozícií obsahovala \(0\).

Jednotky, ktoré ostali na páske E však nie sú hľadaným výsledkom. Nás totiž zaujímajú iba úseky jednotiek, ktoré majú dĺžku presne tri. Každý takýto úsek je síce na páske E reprezentovaný 1, ale aj úsek jednotiek dĺžky 4 nám na pásku E pridá nejaké jednotky, presnejšie rovno 2. Uvedomme si však, že úseky jednotiek dĺhších ako 3, nám na páske E vytvoria nejaký úsek jednotiek dlhší ako 1. To znamená, že na páske E chceme nájsť počet osamotených 1 – takých, ktoré majú napravo aj naľavo od seba 0.

Pri tom si pomôžeme strojom RAO z minulého kola. Ten vedel takéto osamotené z pásky odstraňovať. Máme teda pásku E na ktorej sú dobré aj zlé 1 a pásku RAO(E), v ktorej sme dobré 1 odstránili. Koľko je teda dobrých jednotiek? No predsa P(E) - P(RAO(E)) – ak spočítame počet jednotiek na páske E a odčítame od neho počet jednotiek z pásky RAO(E) tak výsledok je práve počet dobrých jednotiek. Jediný problém je, ako spraviť odčítanie. Na to nám ale veľmi šikovne poslúži stroj XOR. Pozrite sa na príklad nižšie a rozmyslite si, ako takéto odčítavanie bude fungovať.

Páska A:            1110011111011100
B = A << 1          1100111110111000 (susedia napravo)
C = A << 2          1001111101110000 (susedia o 2 pozície napravo)
D = A & B           1100011100011000 (pozície s 1, ktoré majú 1 aj napravo od seba)
E = D & C           1000011100010000 (pozície s 1, ktoré majú dve 1 napravo od seba)
F = RAO(E)          0000011100000000
G = P(E)            0000000000011111 (=5, počet 1 vrátane osamotených)
H = P(F)            0000000000000111 (=3, počet 1 bez osamotených)
I = G ^ H           0000000000011000
J = P(I)            0000000000000011 (=2, počet osamotených 1)

Skrátene: E = A & (A << 1) & (A << 2) a potom J = P( P(E) ^ P(RAO(E)) )

Podúloha e) NAJDL – stroj

Vytvoríme si najskôr pomocný stroj SEK, ktorý z každého úseku jednotiek vymaže najľavejšiu jednotku. Stroj SEK:

Páska A:            0100111011010110
B = A >> 1          0010011101101011
C = A & B           0000011001000010
Vytlač C

Pomocou stroja SEK budeme postupne skracovať úseky jednotiek na vstupnej páske. Po prvom použítí tohto stroja zmiznú všetky úseky dĺžky 1. Po dvoch použitiach už na páske neostane nič z úsekov dĺžky 2, atď.. To znamená, že ak sa po \(x\) použitiach stroja SEK na páske nachádza nejaká 1, tak na pôvodnej vstupne páske musel byť úsek jednotiek dĺžky aspoň \(x+1\).

Budeme teda opakovať nasledovný postup. Najskôr zistíme, či sa na páske nachádza nejaká 1. Toto vieme ľahko spraviť pomocou stroja P. Na páske B si potom budeme pamätať, koľkokrát sa tam naozaj nejaká jednotka nachádzala. No a následne použijeme na pásku stroj SEK.

Na pásku B zapíšeme toľko jednotiek, aká bolo dĺžka najdlhšieho úseku jednotiek na vstupnej páske a vďaka tomu ľahko zistíme odpoveď.

Páska A:            0111101101111110
B = 0               0000000000000000
C = 1               0000000000000001

D = P(A)            0000111111111111 (=12)
E = D & C           0000000000000001 (A obsahuje aspoň 1 jednotku)
B = B OR E          0000000000000001 (pripíšem výsledok na pásku B)
A = SEK(A)          0011100100111110

D = P(A)            0000000111111111 (=9)
E = D & C           0000000000000001 (A obsahuje aspoň 1 jednotku)
B = B << 1          0000000000000010 (spravím si miesto pre novú informáciu)
B = B OR E          0000000000000011 (pripíšem výsledok na pásku B)
A = SEK(A)          0001100000011110

....
14x
....

B = P(B)
Vytlač B

Všimnite si, že sme použili výrazy typu A = SEK(A). To znamená, že stroj SEK príjme pôvodnú hodnotu pásky A a svoj výsledok zapíše opäť na pásku A, čím zmení jej obsah.

Naše riešenie však používa tie isté operácie stále dookola. Pre jednoduchší zápis, môžeme použiť cyklus tvaru opakuj k, do ktorého vložíme nejaké operácie. Tieto operácie sa potom zopakujú \(k\) krát.

Páska A
B = 0
C = 1

Opakuj 16:
    D = P(A)
    E = D & C
    B = B << 1
    B = B OR E
    A = SEK(A)

B = P(B)
Vytlač B

Alebo ešte stručnejšie:

B = 0
Opakuj 16:
    B = B << 1
    B = B OR ( P(A) & 1 )
    A = SEK(A)

Vytlač P(B)

  1. Takýmto páskam, v skutočnom počítači číslam, hovoríme bitová maska (angl. bitmask).↩

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ť.