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