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)
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.