3. Akútny upgrade vzorové riešenie

10

35

4

1
2
3
4

5

3

8

4

10 15 7 8 12 3

6

10 20 30 4 9 7

30
9

Táto úloha bola už tradične špeciálna. V tomto prípade sme vám ukázali nový model počítača a nejaký nový spôsob programovania. O tom, ako blízko realite tento model je si môžeme porozprávať v ďalšom vzoráku. Ako prvý krok k vyriešeniu úloh bolo dobré pozrieť si nejaké príklady programov a pochopiť čo asi robia.

Podúloha A

Toto bola úloha, ktorá mala preveriť, či chápete ako model funguje. Na jej vyriešenie stačilo iba do rúry pridať číslo 3 a 5. Po operácii mul sa potom na koniec rúry vložil násobok čísla, ktoré tam bolo a druhého čísla v rúre, teda 3. Následným príkazom add sa odtiaľ toto číslo vzalo, sčítalo s 5 a vložilo na koniec rúry. Print už len vypísal jediné číslo v rúre – výsledok.

put 3; put 5
mul; add;
print

Pokiaľ náhodou nerozumiete ako program funguje, kľudne si zapnite simulátor a odkrokujte si ho.

Podúloha B

Táto podúloha vyzerá, že k riešeniu potrebuje cyklus. Istú formu cyklu sme si ale ukazovali v manuáli k simulátoru, medzi príkladmi programov. Ten však funguje donekonečna a to sa nám až tak nepáči. Tiež nezvyšuje nejakú premennú, ktorú by sme asi potrebovali poznať. Budeme teda postupovať tak, že si načítame vstup do registra \(x\) a potom budeme zvyšovať v cykle číslo v registri \(i\) a to aj vypisovať.

get x
label cyklus
put i; put 1; add; get i
put i; print
jump cyklus

Toto už vyzerá celkom dobre až na to, že ide o nekonečný cyklus. Čo teda chceme urobiť? Pokiaľ sa v registri \(i\) nachádza to, čo registri \(x\) a už sme \(i\) vypísali, chceme skončiť. Ako skončiť? Skočíme jednoducho na nejaké návestie mimo cyklu a tam v pokoji skončíme.

Náš program bude vyzerať nejak takto:

get x

label cyklus
put i; put 1; add; get i
put i; print
jeq i x koniec
jump cyklus

label koniec

Podúloha C

Super, vytvorili sme si celkom pekný cyklus, ktorý by sa dal možno aj v budúcnosti použiť. Ak by sme boli požiadaní aby sme napísali riešenie pre túto úlohu v svojom obľúbenom programovacom jazyku, čo by sme urobili? Stačil by nám jeden for cyklus a dve premenné, v ktorých by sme si pamätali posledné a predposledné vypočítané fibonacciho číslo. V každom kroku cyklu by sme vypísali posledné číslo a obidve tieto premenné aktualizovali. Ak si tieto premenné označíme \(a\) a \(b\), chceli by sme urobiť \(a=b\) a \(b = a+b\). Inak povedané, predposledné číslo bude mať hodnotu posledného a posledné bude súčtom týchto dvoch čísel. Takýto presun samozrejme nejde urobiť naraz a budeme na to potrebovať pomocnú premennú, to nám ale nevadí.

get n
put 1; get b

label cyklus
put i; put 1; add; get i

jeq i n koniec
put b; put a; put b; get a; add; get b
jump cyklus

label koniec
put a; print a

Pokiaľ program príliš nechápete, krokujte si ho a všímajte si najmä hodnoty v registroch \(i\), \(a\), \(b\).

Podúloha D

Najjednoduchší spôsob ako zistiť počet deliteľov nejakého \(x\) je prejsť všetky čísla menšie rovné ako \(x\) a každé otestovať, teda zistiť či delí \(x\).

get n

label cyklus
put i; put 1; add; get i
put n; put i; mod

get z ; jz z pridaj
label sem

jeq i n koniec
jump cyklus

label pridaj
put a; put 1; add; get a
jump sem

label koniec
put a; print a

Na návestie/label pridaj skočíme, pokiaľ sme v cykle zistili, že aktuálne \(i\) delí \(n\). To sme zistili tak, že sme do rúry vhodili \(n\) a \(i\) a zistili, či sa zvyšok \(n\) po delení \(i\) rovná 0. Pokiaľ áno, skočime na návestie pridaj a odtiaľ skočíme potom naspäť do cyklu.

Podúloha E

Tu budeme musieť zvoliť iný prístup. Problémom je, že nevieme použiť rúru. Ak tam niečo vložíme, ako vieme, že sme narazili na nejaké naše číslo a nie na čísla, ktoré tam boli už predtým? Zachráni nás iba to, že čísla na vstupe sú kladné. Pokiaľ si teda vložíme za tieto čísla nulu, vieme odhaliť, že veci za ňou sme si tam vložili my a nie sú súčasťou vstupu.

Pre každé číslo na vstupe bude stačiť, ak si za našu zarážku vložíme hodnotu 1. Tým sa nám úloha zmení a v tomto momente chceme sčítať všetky čísla v rúre. V rúre je niekoľko 1 a my chceme zistiť koľko. Zjavne nám stačí sčítavať čísla pokým to ide. Zavolať funkciu add však nemôžeme pokiaľ nemáme v rúre aspoň dve čísla. Preto musíme vždy skontrolovať či máme v rúre aspoň dve čísla, ak áno, tak môžeme zavolať add. Pokiaľ nie, tak číslo, ktoré je v rúre jediné je náš želaný súčet.

put 0
label cyklus1
get a; jz a spocitaj
put 1
jump cyklus1

label spocitaj
get a;
jempty koniec
get b; put a; put b; add
jump spocitaj

label koniec
put a; print

Po prvom cykle, ktorý skončí keď narazí na 0 je iba nejaký počet jednotiek. Za každé číslo na vstupe je tam teraz jedna jednotka. V cykle spočítaj teda už iba “bezpečne” sčítavame, pokým nám neostane v rúre iba jedno číslo. Bezpečne v tom zmysle, že keby len voláme dookola add, môže sa nám stať, že v rúre budeme mať už iba jedno číslo a náš program spadne. Preto pred každým sčítaním otestujeme, či sú v rúre aspoň dve čísla. Na to použijeme jempty.

Podúloha F

Táto podúloha sa celkom podobá na podúlohu E a použijeme v nej tiež podobný trik s 0 ako zarážkou. Táto podúloha však vyžaduje trochu väčšiu kreativitu pri riešení. Čo si môžeme chcieť dať za zarážku? Najvhodnejšie by bolo asi zvyšky po delení jednotlivých čísel 3. Na to však nevieme vhodne použiť operáciu mod. Z dôvodu, že tej bude chýbať druhý parameter. Prvé prejdenie čísel bude teda musieť byť akási predpríprava na toto. Za každé číslo si vhodíme do rúry toto číslo a 3. To nám umožní v ďalšom prechode hádzať za zarážku rovno zvyšok po delení 3. Pokiaľ rúra vyzerala: 10 15 7 3 8, bude po takomto preiterovaní vyzerať takto: 10 3 15 3 7 3 3 3 8 3. Všetky tieto čísla sú kladné, teda v ďaľšom prechode môžeme znova 0 použiť ako zarážku.

Tu nás však PRAStarý Kalkulátor sklame. On totiž nevie zistiť, či je na začiatku rúry 0. Predtým musí túto 0 načítať. Je teda jasné, že pri prechode týchto čísel budeme musieť vždy najprv číslo načítať, zistiť či nie je 0 a potom až použiť mod. Tomu však bude chýbať prvý parameter, ktorý sme práve využili na test, či to nie je naša zarážka. Z tohto dôvodu sa nám oplatí si do rúry vkladať pri prvom prechode samotné číslo 2 krát. Rúra teda bude vyzerať po našom zamyslení takto: 10 10 3 15 15 3 7 7 3 3 3 3 8 8 3. Teraz už vieme opakovať postup načítaj číslo, ak to je 0, skonči. Ak to nie je 0, zavolaj funkciu mod. Po tomto prechode máme v rúre akékoľvek čísla, ktoré reprezentujú zvyšky jednotlivých čísel po delení 3. Je zjavné, že nám už stačí len odpočítať počet 0. To si zjednodušíme ešte tým, že si okrem zvyšku po delení budeme do rúry vkladať aj dané číslo. Aby sa nám znovu dala 0 použiť ako zarážka. V predposlednom prechode nám teda rúra bude vyzerať takto: 10 1 15 0 7 1 3 0 8 2. Po tomto už len stačí rúru prejsť a za 0, ktorú môžeme opäť použiť ako zarážku, si za každý zvyšok 0 hodiť 1. Vtedy sa nám problém zmení znova na spočítanie jednotiek v rúre, čo sme vyriešili už v predchádzajúcej úlohe.

put 0
label cyklus1
get a; jz a koniec1
put a; put a; put 3
jump cyklus1

label koniec1

put 0
label cyklus2
get a; jz a koniec2
put a; mod
jump cyklus2

label koniec2

put 0
label cyklus3
get a; jz a koniec3
get z; jz z pridaj
jump cyklus3

label pridaj
put 1
jump cyklus3

label koniec3

label spocitaj
get k;
jempty koniec
get l; put k; put l; add
jump spocitaj

label koniec
put k; print

Tým, že sa program skladá z viacerých častí, odporúčame si po jednotlivých častiach vložiť príkaz end. Tým ľahko zistíte, ako vyzerá rúra po jednotlivých väčších blokoch kódu.