Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na ajo@ksp.sk

Timke sa pokazil počítač. Je to pre ňu ako programátorku beztak ťažké, a akoby nestačilo, je nedeľa ráno a ona musí na pondelok do školy vypracovať úlohu z programovania. To by ale bola hanba keby ju ona, ktorá rieši všemožné súťaže nemala. Rozhodla sa preto zísť do pivnice a pokúsiť sa nájsť svoj starý počítač. Namiesto neho však našla iba pár zbytočností a jeden naozaj starý počítač. Oprášila ho a uvidela na ňom názov : “PRAStarý Kalkulátor”. Potešila sa. Keď ho však zapojila, ostala nemilo prekvapená. Počítač nebol úplne klasický, nemal ikonky ani žiadne pokročilé príkazy a hlavne nemal klasickú pamäť. Našla však k nemu naozaj starý manuál, ktorý popisuje jeho fungovanie a tajomnú rúru, ktorá sa pri programovaní v ňom používa.

Úloha

Pomôžte Timke a naprogramujte jej úlohu na tomto starom počítači.

  1. (1 bod) V rúre sa nachádza číslo \(x\) \((0 \leq x \leq 100)\). Vypíšte na výstup číslo \(3 \cdot x+5\).

Input:

10

Output:

35
  1. (2 body) Vypíšte na výstup čísla od 1 po \(x\), kde \(x\) \((1 \leq x \leq 100)\) je jediné číslo, nachádzajúce sa na začiatku v rúre.

Input:

4

Output:

1
2
3
4
  1. (2 body) Poznáte fibonnacciho postupnosť? Je to postupnosť tvaru \(0, 1, 1, 2, 3 \dots\) Prvé dve čísla postupnosti sú 0 a 1, pre ďalšie čísla platí, že každé je súčtom dvoch predchádzajúcich. V rúre máte na začiatku číslo \(n\) \((1 \leq n \leq 100)\). Vypíšte na výstup jediné číslo a to \(n\)-té fibbonacciho číslo.

Input:

5

Output:

3
  1. (3 body) V rúre sa nachádza jediné číslo \(x\) \((1 \leq x \leq 1000)\). Zistite počet jeho deliteľov a vypíšte tento počet na výstup.

Input:

8

Output:

4
  1. (3 body) Na vstupe sa nachádza \(n\) \((0 \leq n \leq 300)\) kladných čísel. Vypíšte na výstup jediné čislo, ich počet.

Input:

10 15 7 8 12 3

Output:

6
  1. (4 bodov) V rúre sa nachádza \(n\) \((1 \leq n \leq 2000)\) kladných čísel. Vypíšte na výstup tie z nich, ktoré sú deliteľné 3. Navyše musí platiť, že ich vypíšete v rovnakom poradí v akom sa nachádzali na začiatku v rúre.

Input:

10 20 30 4 9 7

Output:

30
9

Odovzdávanie

Odvzdávanie tejto úlohy je trochu špecifické. Vaše riešenia si môžete akokoľvek dlho testovať pomocou online simulátora, ku ktorému sme pre vás taktiež pripravili krátky manuál. Na testovanie môžete odoslať zozipovaný archív, ktorý má obsahovať pre každú podúlohu práve jeden textový súbor s názvom x.txt kde x je názov podúlohy. Tento textový súbor má obsahovať kód vášho programu. Pokiaľ v podúlohe uvádzame, že sa v rúre niečo nachádza, váš program má predpokladať, že to tam naozaj je. Neodosielajte teda na testovanie verziu, v ktorej si nejaký testovací vstup vyrobíte tak, ako to zrejme treba robiť v simulátore. Dajte si tiež pozor aby zip neobsahoval priečinok ale priamo textové súbory. Testovač by mal váš kód otestovať, pričom v detailoch jednotlivých stupov sa viete dozvedieť, čo bolo zle. Pokiaľ sa testovač tvári, že váš kód testuje a trvá to nejak dlho, je veľmi pravdepodobné, že je niečo zle, napr. neodoslali ste súbory v požadovanom formáte a podobne. Ak ste si napriek tomu istý, že robíte všetko správne a testovač štrajkuje, neváhajte nás kontaktovať na mail vyššie. Odovzdávať môžete aj iba časť programov, teda napr. môžete odoslať zip s obsahom a.txt, c.txt a e.txt. Toto výrazne odporúčame, nakoľko si viete otestovať, či všetko funguje na menej ťažkých podúlohách.

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.

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