2. Pokročilé prototypy

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)