2. Spájané štruktúry¶

Doteraz sme pracovali s „predpripravenými“ dátovými štruktúrami jazyka Python (zjednodušene hovoríme, že štruktúra je typ, ktorý môže obsahovať viac prvkov), napríklad

list - zoznam (postupnosť) hodnôt, ktoré sú očíslované indexmi od 0 do počet prvkov-1
dict - slovník (asociatívne pole), kde každému prvku zodpovedá kľúč
set - množina rôznych hodnôt

Okrem toho už viete konštruovať vlastné dátové typy pomocou definovania tried. Inštancie tried obsahujú atribúty, ktoré sú buď stavovými premennými alebo metódami (napríklad Stack alebo Queue). Takto vieme vytvárať vlastné typy, pričom využívame štruktúry Pythonu.

Referencie

Už vieme, že premenné v Pythone (aj atribúty objektov) sú vlastne pomenované referencie na nejaké hodnoty, napríklad čísla, reťazce, zoznamy, funkcie, atď. Referencie (kreslili sme ich šípkou) sú niečo ako adresou do pamäte, kde sa príslušná hodnota nachádza. Takýmito referenciami sú aj prvky iných štruktúrovaných typov, napríklad

zoznam čísel [1, 2, 5, 2] je v skutočnosti štvorprvkový zoznam referencií na hodnoty 1, 2, 5 (posledný prvok obsahuje rovnakú referenciu ako druhý prvok zoznamu);
slovník (asociatívne pole) uchováva dvojice (kľúč, hodnota) a každá z nich je opäť referenciou na príslušné hodnoty;
množina hodnôt sa tiež uchováva ako množina referencií na hodnoty
atribúty tried, ktoré sú stavové premenné obsahujú tiež „iba“ referencie na hodnoty.

Naučíte sa využívať referencie (adresy rôznych hodnôt, teda adresy objektov) na vytváranie spájaných štruktúr.

Spájaný zoznam¶

Jednosmerný spájaný zoznam (singly linked list) je najjednoduchšia spájaná štruktúra, v ktorej každý prvok obsahuje referenciu (adresu, niekedy hovoríme aj link, smerník, pointer) na nasledovný prvok štruktúry. Prvkom štruktúry hovoríme Vrchol (alebo niekedy po anglicky Node). Spájané štruktúry budú vždy prístupné pomocou premennej, ktorá odkazuje (obsahuje referenciu) na prvý prvok (vrchol) zoznamu. Spájaný zoznam reprezentuje postupnosť nejakých hodnôt a v tejto postupnosti je jeden vrchol posledný, za ktorým už nie je nasledovný prvok. Tento jeden vrchol si teda namiesto nasledovníka bude pamätať informáciu, že nasledovník už nie je - najčastejšie na to využijeme hodnotu None.

Takúto štruktúru budeme kresliť takto:

jedna premenná odkazuje (obsahuje referenciu) na prvý prvok (vrchol) zoznamu
každý vrchol nakreslíme ako obdĺžnik s dvomi priečinkami: časť s údajom (pomenujeme to ako data) a časť s referenciou na nasledovníka (pomenujeme ako next)
referencie budeme kresliť šípkami, pričom neexistujúcu referenciu (pre nasledovníka posledného vrcholu), t.j. hodnotu None môžeme značiť prečiarknutím políčka next, napríklad takto:

Reprezentácia vrcholu¶

Vrchol budeme definovať ako objekt s dvoma premennými data a next:

class Vrchol:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

Pozrite, čo sa definuje týmto zápisom:

>>> v1 = Vrchol(11)

Vytvorili sme jeden vrchol, resp. jednovrcholový spájaný zoznam. Jeho nasledovníkom je None. Na tento vrchol odkazuje premenná v1. Jedine, čo zatiaľ môžeme s takýmto vrcholom robiť je to, že si vypíšeme jeho atribúty:

>>> print(v1.data)
    11
>>> print(v1.next)
    None

Podobne zapíšeme:

>>> v2 = Vrchol(22)
>>> v3 = Vrchol(33)

Teraz máme vytvorené 3 izolované vrcholy, ktoré sú prístupné pomocou troch premenných v1, v2 a v3. Tieto tri vrcholy sa nachádzajú v rôznych častiach pamäti a nie sú nijako prepojené.

Vytvorme prvé prepojenie: ako nasledovníka v1 nastavíme vrchol v2:

>>> v1.next = v2
>>> print(v1.next)
    <__main__.Vrchol object at 0x01FAF0D0>

Vidíme, že nasledovníkom v1 už nie je None, ale nejaký objekt typu Vrchol - zrejme je to vrchol v2.

Môžeme sa pozrieť na údaj nasledovníka v1:

>>> print(v1.next.data)
    22
>>> print(v1.next.next)
    None

Keďže jeho nasledovníkom je None, znamená to, že nasledovníka nemá. Premenná v1 obsahuje referenciu na vrchol, ktorý má jedného nasledovníka, t.j. v1 odkazuje na dvojprvkový spájaný zoznam. Pripojme teraz do tejto postupnosti aj vrchol v3:

>>> v2.next = v3

Takže prvým vrcholom v spájanom zozname je v1 s hodnotou 11, jeho nasledovníkom je v2 s hodnotou 22 a nasledovníkom v2 je v3 s hodnotou 33. Nasledovníkom tretieho vrcholu je stále None, teda tento vrchol nemá nasledovníka.

Vytvorili sme trojprvkový spájaný zoznam, ktorého vrcholy majú postupne tieto hodnoty:

>>> print(v1.data)
    11
>>> print(v1.next.data)
    22
>>> print(v1.next.next.data)
    33

Vidíte, že pomocou referencie na prvý vrchol sa vieme dostať ku každému vrcholu, len treba dostatočný počet krát zapísať next. Premenné v2 a v3 teraz už nepotrebujeme a mohli by sme ich hoci aj zrušiť - na vytvorený zoznam to už nemá žiaden vplyv:

>>> del v2, v3

Teraz to v pamäti vyzerá takto:

Webová stránka pythontutor.com¶

Zo zimného semestra poznáme http://pythontutor.com/visualize.html - veľmi užitočný nástroj na vizualizáciu pythonovských programov. Vieme, že sem môžeme preniesť skoro ľubovoľný algoritmus, ktorý sme robili doteraz (okrem grafiky) a odkrokovať ho. Môžeme sem preniesť, napríklad tento program:

class Vrchol:
    def __init__(self, data, next=None):
        self.data, self.next = data, next

v1 = Vrchol(11)
v2 = Vrchol(22)
v3 = Vrchol(33)
v1.next = v2
v2.next = v3
del v2,v3

Po spustení vizualizácie môžeme vidieť, že globálna premenná v1 obsahuje referenciu na inštanciu triedy Vrchol, v ktorej atribút data má hodnotu 11 a atribút next je opäť referenciou na ďalšiu inštanciu triedy Vrchol, atď.

Tiež tu môžeme vidieť, že globálna premenná Vrchol obsahuje referenciu na definíciu triedy Vrchol:

Spájané vytváranie vrcholov¶

Pozrite tento zápis:

>>> a = Vrchol('a')
>>> b = Vrchol('b')

>>> a.next = b

>>> del b

Vytvorí dvojprvkový zoznam, pričom premenná b je len pomocná a hneď po priradení do a.next sa aj zruší. To isté môžeme zapísať aj bez nej:

>>> a = Vrchol('a')
>>> a.next = Vrchol('b')

Tu si všimnite, že inicializačná metóda (Vrchol.__init__()) má druhý parameter, ktorým môžeme definovať hodnotu next už pri vytváraní vrcholu. Preto môžeme tieto dve priradenia zlúčiť do jedného:

>>> a = Vrchol('a', Vrchol('b'))

Hoci teraz je tu malý rozdiel a to v tom, že vrchol Vrchol('b') sa vytvorí skôr ako Vrchol('a'), čo ale vo väčšine prípadov nevadí. Podobne by sme vedeli jedným priradením vytvoriť nielen dvojprvkový, ale aj viacprvkový zoznam, napríklad:

>>> zoznam = Vrchol('P', Vrchol('y', Vrchol('t', Vrchol('h', Vrchol('o', Vrchol('n'))))))

Vytvorí šesťprvkový zoznam, pričom každý prvok obsahuje jedno písmeno z reťazca 'Python':

Výpis pomocou cyklu¶

Predpokladajte, že máme vytvorený nejaký, napríklad štvorprvkový zoznam:

>>> v1 = Vrchol(11, Vrchol(22, Vrchol(33, Vrchol(44))))

V pamäti by sme ho mohli vidieť nejako takto:

Teraz treba vypísať všetky jeho hodnoty postupne od prvej po poslednú, môžeme to urobiť, napríklad takto:

>>> print(v1.data)
    11
>>> print(v1.next.data)
    22
>>> print(v1.next.next.data)
    33
>>> print(v1.next.next.next.data)
    44

alebo v jednom riadku:

>>> print(v1.data, v1.next.data, v1.next.next.data, v1.next.next.next.data)
    11 22 33 44

Zrejme pre zoznam ľubovoľnej dĺžky budeme musieť použiť nejaký cyklus, asi najvhodnejší bude while-cyklus. Keď vypíšeme prvú hodnotu, posunieme premennú v1 na nasledovníka prvého vrcholu:

>>> print(v1.data)
>>> v1 = v1.next

a môže sa to celé opakovať. Zápis v1 = v1.next je veľmi dôležitý a budeme ho v súvislosti so spájanými zoznamami používať veľmi často. Označuje, že do premennej v1 sa namiesto referencie na nejaký vrchol dostáva referencia na jeho nasledovníka:

postupne dostávame:

Ak už tento vrchol nasledovníka nemá, do v1 sa dostane hodnota None:

Preto kompletný výpis hodnôt zoznamu môžeme zapísať takto:

while v1 is not None:
    print(v1.data, end=' -> ')
    v1 = v1.next
print(None)

Pre názornosť sme tam medzi každé dve vypisované hodnoty pridali reťazec ' -> ':

11 -> 22 -> 33 -> 44 -> None

Hoci to vyzerá dobre a dostatočne jednoducho, má to jeden problém: po skončení vypisovania pomocou tohto while-cyklu je v premennej v1 hodnota None:

>>> print(v1)
    None

Teda výpisom sme si zničili jedinú referenciu na prvý vrchol zoznamu a teda Python pochopil, že so zoznamom už pracovať ďalej nechceme a celú štruktúru z pamäti vyhodil (hovorí sa tomu garbage collection). Môžeme to skontrolovať aj vo vizualizácii http://pythontutor.com/visualize.html. Tento príklad ukazuje to, že niekedy si bude potrebné uchovať referenciu na začiatok zoznamu, alebo sa v takomto cykle nebude pracovať priamo s premennou v1, ale s jej kópiou, napríklad takto:

pom = v1
while pom is not None:
    print(pom.data, end=' -> ')
    pom = pom.next
print(None)

Po skončení tohto výpisu sa premenná pom vynuluje na None, ale začiatok zoznamu v1 ostáva neporušený. Teraz je to už správne a v pamäti to postupne vyzerá takto:

Takýto výpis sa dá zapísať aj do funkcie, pričom tu pomocnú referenciu na začiatok zoznamu zastúpi parameter:

def vypis(zoznam):
    while zoznam is not None:
        print(repr(zoznam.data), end=' -> ')
        zoznam = zoznam.next
    print(None)

Pri volaní funkcie sa do formálneho parametra zoznam priradí hodnota skutočného parametra (napríklad obsah premennej v1) a teda referencia na začiatok zoznamu sa týmto volaním nepokazí.

Teraz môžeme volať funkciu na výpis nielen so začiatkom zoznamu ale hoci, napríklad aj od druhého vrcholu:

>>> vypis(v1)
    11 -> 22 -> 33 -> 44 -> None
>>> vypis(v1.next)
    22 -> 33 -> 44 -> None

Vidíte, že referencia na prvý vrchol v spájanom zozname má špeciálny význam a preto sa zvykne označovať nejakým dohodnutým menom, napríklad zoznam, zoz, zac, z (ako začiatok zoznamu) alebo niekedy aj po anglicky head (hlavička zoznamu).

Vytvorenie zoznamu pomocou cyklu¶

Zoznamy sme doteraz vytvárali sériou priradení a to bez cyklov. Častejšie sa ale budú vytvárať (možno aj dosť dlhé) zoznamy pomocou opakujúcich sa programových konštrukcií. Začneme vytváraním zoznamu pridávaním nového vrcholu na začiatok doterajšieho zoznamu, keďže toto je výrazne jednoduchšie.

Vytvoríme desaťprvkový zoznam s hodnotami 0, 1, 2, … 9. Začneme s prázdnym zoznamom:

>>> zoz = None

Vytvoríme prvý vrchol s hodnotou 0:

>>> pom = Vrchol(0)

a dáme ho na začiatok:

>>> zoz = pom

Keby sme to teraz vypísali pomocou funkcie vypis(zoz), dostali by sme: 0 -> None

Vytvoríme druhý vrchol:

>>> pom = Vrchol(1)

a dáme ho pred doterajší začiatok:

>>> pom.next = zoz

tento nový vrchol je teraz novým začiatkom zoznamu:

>>> zoz = pom

Po výpise by sme dostali: 1 -> 0 -> None

Toto môžeme opakovať viackrát pre rôzne hodnoty - zakaždým sa na začiatok doterajšieho zoznamu pridá nový vrchol:

>>> pom = Vrchol(2)
>>> pom.next = zoz
>>> zoz = pom

>>> pom = Vrchol(3)
>>> pom.next = zoz
>>> zoz = pom

Takto by sme mohli pokračovať až do 9. Teraz už vidíte, čo sa tu opakuje a čo treba dať do cyklu:

zoz = None                    # zatiaľ je to ešte prázdny zoznam
for hodnota in range(10):
    pom = Vrchol(hodnota)
    pom.next = zoz
    zoz = pom

Týmto postupom sme dostali 10 prvkový zoznam hodnôt v poradí od 9 do 0

>>> vypis(zoz)
    9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None

Opäť si všimnime zápis tela cyklu:

pom = Vrchol(hodnota)
pom.next = zoz
zoz = pom

Vytvorí sa tu nový vrchol najprv s danou hodnotou a nasledovníkom None. Potom sa tento nasledovník zmení na pom.next = zoz a na záver sa tento nový vrchol pom stáva novým začiatkom zoznamu, t.j. zoz = pom. Toto isté sa dá zapísať kompaktnejšie:

zoz = None
for hodnota in range(10):
    zoz = Vrchol(hodnota, zoz)

Takto by sme vedeli vytvoriť ľubovoľné zoznamy. Zapíšme tento algoritmus do funkcie:

def vyrob(postupnost):
    zoz = None
    for hodnota in postupnost:
        zoz = Vrchol(hodnota, zoz)
    return zoz

Otestujme, napríklad:

>>> zoz1 = vyrob(range(1000))
>>> vypis(zoz1)
    999 -> 998 -> ... -> 1 -> 0 -> None
>>> zoz2 = vyrob('Python')
>>> vypis(zoz2)
    'n' -> 'o' -> 'h' -> 't' -> 'y' -> 'P' -> None

Vytvorili sa dva zoznamy: prvý s 1000 vrcholmi a druhý so šiestimi vrcholmi s písmenami reťazca 'Python'. Treba si pri tomto uvedomiť, že takto sa vytvárajú zoznamy s hodnotami v opačnom poradí, ako so do neho vkladali.

Častejšie budeme potrebovať vyrábať zoznamy, v ktorých budú prvky v tom poradí, v akom sme ich vkladali. Jednoduchým riešením môže byť prevrátenie vstupnej postupnosti pomocou reversed():

def vyrob1(postupnost):
    zoz = None
    for hodnota in reversed(postupnost):
        zoz = Vrchol(hodnota, zoz)
    return zoz

Otestujeme:

>>> zoz2 = vyrob1('Python')
>>> vypis(zoz2)
    'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None

Uvedomte si, že nie vždy môžeme takto jednoducho otočiť vstupnú postupnosť, z ktorej sa má vytvoriť spájaný zoznam. Napríklad, ak sú vstupnou postupnosťou riadky otvoreného textového súboru, tak takúto postupnosť takto jednoducho neotočíme.

Zistenie počtu prvkov¶

Zapíšeme funkciu, ktorá spočíta počet prvkov zoznamu. Bude pracovať na rovnakom princípe ako funkcia vypis() len namiesto samotného vypisovania hodnoty funkcia zvýši počítadlo o 1:

def pocet(zoznam):
    vysl = 0
    while zoznam is not None:
        vysl += 1
        zoznam = zoznam.next
    return vysl

Otestujeme, napríklad:

>>> zoz = vyrob('Python')
>>> pocet(zoz)
    6

Malou úpravou túto funkciu vylepšíme:

def pocet(zoznam, hodnota=None):
    vysl = 0
    while zoznam is not None:
        if hodnota is None or zoznam.data == hodnota:
            vysl += 1
        zoznam = zoznam.next
    return vysl

Táto funkcia dokáže nielen zistiť počet prvkov zoznamu, ale aj počet výskytov nejakej konkrétnej hodnoty. Napríklad:

>>> zoz1 = vyrob('programujem v pythone')
>>> pocet(zoz1)
    21
>>> pocet(zoz1, 'p')
    2

Hľadanie vrcholu¶

Podobný cyklus, ako sme použili pri výpise a pri zisťovaní počtu prvkov, môžeme použiť pri zisťovaní, či sa daná hodnota nachádza v zozname. Napíšme funkciu, ktorá vráti True, ak nájde konkrétnu hodnotu, inak vráti False:

def zisti(zoznam, hodnota):
    while zoznam is not None:
        if zoznam.data == hodnota:
            return True
        zoznam = zoznam.next
    return False

Otestujeme:

>>> zoznam = vyrob('Python')
>>> zisti(zoznam, 'h')
    True
>>> zisti(zoznam, 'g')
    False

Táto funkcia skončila prechádzanie prvkov zoznamu už pri prvom výskyte hľadanej hodnoty.

Zmena hodnoty vo vrchole¶

Najprv vytvorme jednoduchú funkciu, ktorá zmení všetky hodnoty v zozname:

def zmen(zoznam, hodnota):
    while zoznam is not None:
        zoznam.data = hodnota
        zoznam = zoznam.next

>>> zoznam = vyrob('Python')
>>> zmen(zoznam, 0)
>>> vypis(zoznam)
    0 -> 0 -> 0 -> 0 -> 0 -> 0 -> None

Ak chceme zmeniť len vrcholy, ktoré obsahujú nejakú konkrétnu hodnotu, môžeme to zapísať takto:

def zmen(zoznam, hodnota, na_hodnotu):
    while zoznam is not None:
        if zoznam.data == hodnota:
            zoznam.data = na_hodnotu
            # return
        zoznam = zoznam.next

Príkaz return v tele cyklu spôsobí ukončenie funkcie už po prvom výskyte hľadanej hodnoty. Inak sa zmenia obsahy všetkých vrcholov s danou hodnotou.

Otestujeme so zakomentovaným return:

>>> zoz = vyrob((1, 2, 3) * 3)
>>> zmen(zoz, 2, 'xy')
>>> vypis(zoz)
    1 -> 'xy' -> 3 -> 1 -> 'xy' -> 3 -> 1 -> 'xy' -> 3 -> None

Vloženie vrcholu na koniec zoznamu¶

Chceme vyrobiť novú operáciu, ktorá na koniec zoznamu vloží nový vrchol s danou hodnotou. Už vieme, že pridávanie vrcholu na začiatok je takto jednoduché:

zoz = ...       # zoz je referencia na začiatok zoznamu
zoz = Vrchol(hodnota, zoz)

S pridávaním na koniec to bude zložitejšie: najprv nájdeme posledný vrchol zoznamu a až tomuto vrcholu zmeníme jeho atribút next, t.j. až na záver urobíme:

posledny.next = Vrchol(hodnota)

Hľadanie posledného vrcholu sa bude podobať na postupné prechádzanie všetkých vrcholov:

posledny = zoz                # posledny je pomocná referencia
while posledny is not None:
    posledny = posledny.next

Lenže toto nebude fungovať - po skončení while-cyklu nebude v premennej posledny referencia na posledný vrchol ale bude tam None. Treba to zapísať trochu zložitejšie - while neskončí až vtedy, keď v posledny bude None, ale keď jeho next bude None:

posledny = zoz
while posledny.next is not None:
    posledny = posledny.next

Teraz je to už naozaj dobre, ale toto bude fungovať len pre neprázdny zoznam. Pre prázdny zoznam hodnota premennej posledny bude None a preto posledny.next spadne na chybe. Tento špeciálny prípad musíme vyriešiť ešte pred cyklom. Teraz môžeme zapísať kompletnú funkciu, ktorá pridá na koniec zoznamu nový vrchol. Táto funkcia bude vracať ako svoj výsledok začiatok takto vytvoreného zoznamu:

def pridaj_koniec(zoz, hodnota):
    if zoz is None:
        return Vrchol(hodnota)
    posledny = zoz
    while posledny.next is not None:
        posledny = posledny.next
    posledny.next = Vrchol(hodnota)
    return zoz

Môžeme otestovať:

zoznam = None
for i in 'Python':
    zoznam = pridaj_koniec(zoznam, i)
vypis(zoznam)

Mali by sme dostať zoznam so 6 písmenami v správnom poradí. Zapamätajte si:

Vloženie nového vrcholu do zoznamu¶

Nový vrchol môžeme vložiť buď pred nejaký existujúci alebo za. Jednoduchšie to bude s vkladaním za nejaký existujúci. Zapíšme:

def pridaj_za(zoznam, za_hodnotu, hodnota):
    while zoznam is not None and zoznam.data != za_hodnotu:
        zoznam = zoznam.next
    if zoznam is not None:
        zoznam.next = Vrchol(hodnota, zoznam.next)

To isté môžeme zapísať aj takto:

def pridaj_za(zoznam, za_hodnotu, hodnota):
    while zoznam is not None:
        if zoznam.data == za_hodnotu:
            zoznam.next = Vrchol(hodnota, zoznam.next)
            return
        zoznam = zoznam.next

Vkladanie pred vrchol bude trochu náročnejšie a bude sa trochu podobať hľadaniu posledného vrcholu v zozname:

def pridaj_pred(zoznam, pred_hodnotu, hodnota):
    if zoznam is None:
        return None                      # nie je čo robiť
    if zoznam.data == pred_hodnotu:
        return Vrchol(hodnota, zoznam)   # pred prvý
    pom = zoznam
    while pom.next is not None:
        if pom.next.data == pred_hodnotu:
            pom.next = Vrchol(hodnota, pom.next)
            break
        pom = pom.next
    return zoznam

Keďže v tomto prípade sa môže zmeniť začiatok zoznamu, táto funkcia vždy vráti začiatok takéhoto zoznamu.

Na tomto príklade sa dá ukázať ešte jedno programátorské vylepšenie prechádzania spájaného zoznamu. Okrem pomocnej referencie pom budeme mať ešte jednu referenciu pred na predchodcu pom:

def pridaj_pred(zoznam, pred_hodnotu, hodnota):
    if zoznam is None:
        return None                       # nie je čo robiť
    pred, pom = None, zoznam
    while pom is not None and pom.data != pred_hodnotu:
        pred, pom = pom, pom.next
    if pred is None:
        zoznam = Vrchol(hodnota, zoznam)  # pred prvý
    elif pom is not None:
        pred.next = Vrchol(hodnota, pred.next)
    return zoznam

Všimnite si, že vo while-cykle sa paralelne menia obe referencie: pom na svojho nasledovníka a pred na predchodcu pom. Keď while-cyklus skončí a v pred je None, znamená to, že budeme pracovať s vrcholom, ktorý nemá predchodcu, čo je prvý vrchol v zozname (máme vložiť pred prvý). Ak po skončení while-cyklu je v pom hodnota None, znamená to, že sme prešli celý spájaný zoznam a nenašli sme vrchol, ktorého hodnota je v parametri pred_hodnotu.

Cvičenia¶

Bez spúšťania na počítači zisti, čo urobia nasledovné programy. Predpokladaj tieto deklarácie a funkcie:

class Vrchol:
    def __init__(self, data, next=None):
        self.data, self.next = data, next

def vypis(zoznam):
    while zoznam is not None:
        print(repr(zoznam.data), end=' -> ')
        zoznam = zoznam.next
    print(None)

def vyrob(postupnost):
    zoz = None
    for hodnota in reversed(postupnost):
        zoz = Vrchol(hodnota, zoz)
    return zoz

Prvý spájaný zoznam:

v1 = Vrchol('v')
v2 = Vrchol('s')
v3 = Vrchol('o')
v4 = Vrchol('a')
v3.next = v1
v1.next = v2
v2.next = v3
v1.next = v4
zoz = v2
vypis(zoz)

Druhý spájaný zoznam:

v1 = None
v2 = Vrchol('S', v1)
v2 = Vrchol('U', v2)
v3 = Vrchol('I', v1)
v3 = Vrchol('V', v3)
v2 = Vrchol('R', v2)
v3.next.next = v2
vypis(v3)

Potom to skontroluj v Pythone.

Skonštruuj zoznam tak, aby si dostal požadovaný výstup. Najprv bez funkcie vyrob a potom pomocou nej:
```
>>> z = ...
>>> vypis(z)
    3.14 -> '6.28' -> 9.42 -> None -> 15.7 -> None
```

Máme daný štvorprvkový zoznam (pri jeho vytváraní využi range). Oprav v ňom druhý prvok:

>>> zoz = vyrob(...)
>>> vypis(zoz)
    4 -> 11 -> 18 -> 25 -> None
>>> ... oprav len 2. prvok
>>> vypis(zoz)
    4 -> (10, 12) -> 18 -> 25 -> None

Máme daný zoznam, ktorý vznikol z vety 'strc prst skrz krk' a pomocou metódy split. Vlož za druhý prvok nový vrchol:
```
>>> zoz = ...
>>> vypis(zoz)
    'strc' -> 'prst' -> 'skrz' -> 'krk' -> None
>>> ... vlož nový vrchol za druhý prvok
>>> vypis(zoz)
    'strc' -> 'prst' -> {1: 2} -> 'skrz' -> 'krk' -> None
```
Zapíš to tak, aby vkladanie za druhý prvok fungovalo aj pre ľubovoľný iný aspoň dvojprvkový zoznam.

Napíš funkciu zmen_parne(zoznam, hodnota=0), ktorá v danom zozname zmení hodnoty len vo vrcholoch s párnou celočíselnou hodnotou na zadanú hodnotu. Funkcia nič nevracia. Napríklad:

>>> zoz = ...
>>> vypis(zoz)
    5 -> 0 -> 2.12 -> '2' -> 18 -> 4.0 -> 4 -> None
>>> zmen_parne(zoz, 42)
>>> vypis(zoz)
    5 -> 42 -> 2.12 -> '2' -> 42 -> 4.0 -> 42 -> None
>>> zmen_parne(zoz.next.next)
>>> vypis(zoz)
    5 -> 42 -> 2.12 -> '2' -> 0 -> 4.0 -> 0 -> None

Napíš funkciu pocty(zoznam, hodnota=0), ktorá vráti dvojicu čísel: počet vrcholov, ktoré sú väčšie ako zadaná hodnota a počet vrcholov, ktoré sú menšie ako hodnota. Napríklad:
```
>>> zoz = ...
>>> vypis(zoz)
    'prvy' -> -7 -> 0.0 -> 2 -> 'druhy' -> -3.14 -> [3] -> None
>>> pocty(zoz)
    (1, 2)
>>> pocty(zoz, 'python')
    (0, 2)
```

Napíš funkciu zdvoj(zoznam), ktorá každý prvok zoznamu zdvojnásobí. Toto urobí len vtedy, ak sa to dá (nevznikne chyba), inak tento prvok nezmení a pokračuje na ďalších. Funkcia nič nevracia. Napríklad:

>>> zoz = ...
>>> vypis(zoz)
    3.14 -> '6.28' -> {1, 2} -> (9, 42) -> None -> [15.7] -> None
>>> zdvoj(zoz)
>>> vypis(zoz)
    6.28 -> '6.286.28' -> {1, 2} -> (9, 42, 9, 42) -> None -> [15.7, 15.7] -> None

Napíš funkciu to_str(zoznam), ktorá z daného spájaného zoznamu vráti reťazec. Tento reťazec bude rovnaký, ako by vypísala funkcia výpis. Funkcia najprv z jednotlivých prvkov spájaného zoznamu vytvorí pythonovský zoznam (list) reťazcov a až na záver z neho pomocou ' -> '.join(...) vyrobí výsledný reťazec. Otestuj tento nový výpis aj pre dlhý zoznam:
```
>>> vypis(vyrob(range(1000)))
    ...
>>> print(to_str(vyrob(range(1000))))
    ...
```
Malo by fungovať aj:
```
>>> print(to_str(vyrob('Python')))
    'P' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
```

Bez spúšťania na počítači zisti, čo urobí:

zoz = vyrob((1, 3, 5, 7, 9, 11, 13))
v = zoz.next.next
v1 = v.next.next
v.next.next = v1.next
v1.next = v.next
v.next = v1
vypis(zoz)

Napíš funkciu vyhod_prvy(zoznam). Funkcia vráti pôvodný zoznam bez prvého prvku. Napríklad:

>>> x = vyrob('py')
>>> vypis(x)
    'p' -> 'y' -> None
>>> x = vyhod_prvy(x)
>>> vypis(x)
    'y' -> None
>>> x = vyhod_prvy(x)
>>> vypis(x)
    None
>>> x = vyhod_prvy(x)
>>> vypis(x)
    None

Napíš funkciu vyhod_druhy(zoznam), ktorá vyhodí druhý prvok spájaného zoznamu. Funkcia nič nevracia. Napríklad:

>>> x = vyrob('pyt')
>>> vypis(x)
    'p' -> 'y' -> 't' -> None
>>> vyhod_druhy(x)
>>> vypis(x)
    'p' -> 't' -> None
>>> vyhod_druhy(x)
>>> vypis(x)
    'p' -> None
>>> vyhod_druhy(x)
>>> vypis(x)
    'p' -> None

Napíš funkciu vyhod_za(zoznam, hodnota), ktorá v danom zozname vyhľadá vrchol s danou hodnotou hodnota a vyhodí za ním nasledujúci vrchol. Ak taký vrchol neexistuje, funkcia nerobí nič. Funkcia nič nevracia. Napríklad:
```
>>> y = ...
>>> vypis(y)
    3 -> 7 -> 'a' -> 'a' -> 11 -> None
>>> vyhod_za(y, 'a')
>>> vypis(y)
    3 -> 7 -> 'a' -> 11 -> None
>>> vyhod_za(y, 11)
>>> vypis(y)
    3 -> 7 -> 'a' -> 11 -> None
```

Napíš funkciu vyhod_posledny(zoznam). Funkcia vráti pôvodný zoznam bez posledného prvku. Napríklad:

>>> x = Vrchol(5, Vrchol(7))
>>> vypis(x)
    5 -> 7 -> None
>>> x = vyhod_posledny(x)
>>> vypis(x)
    5 -> None
>>> x = vyhod_posledny(x)
>>> vypis(x)
    None
>>> x = vyhod_posledny(x)
>>> vypis(x)
    None

Napíš funkciu vyhod_kazdy_druhy(zoznam), ktorá zo zoznamu vyhodí každý druhý prvok. Funkcia nič nevracia. Napríklad:

>>> zoz = vyrob('abcdef')
>>> vypis(zoz)
    'a' -> 'b' -> 'c' -> 'd' -> 'e' -> 'f' -> None
>>> vyhod_kazdy_druhy(zoz)
>>> vypis(zoz)
    'a' -> 'c' -> 'e' -> None
>>> vyhod_kazdy_druhy(zoz)
>>> vypis(zoz)
    'a' -> 'e' -> None

Napíš rekurzívnu verziu funkcie pocet(zoznam), ktorá vráti počet prvkov zoznamu. Funkcia prejde všetky prvky zoznamu bez použitia cyklu len pomocou rekurzie (uvedom si, čo je triviálny prípad rekurzie). Do definície funkcie nepridávaj ďalšie parametre. Napríklad:
```
>>> zoz = vyrob(range(10, 20))
>>> pocet(zoz)
    10
>>> pocet(zoz.next)
    9
>>> pocet(None)
    0
```

Napíš rekurzívnu funkciu sucet(zoznam), ktorá vypočíta súčet prvkov zoznamu (sčituje len číselné hodnoty). Funkcia prejde všetky prvky zoznamu bez použitia cyklu len pomocou rekurzie. Do definície funkcie nepridávaj ďalšie parametre. Napríklad:
```
>>> zoz = ...
>>> vypis(zoz)
    3.14 -> '6.28' -> -1 -> (9, 42) -> None -> [15.7] -> None
>>> sucet(zoz)
    2.14
>>> sucet(zoz.next)
    -1
>>> sucet(None)
    0
```

Napíš funkciu spoj(zoz1, zoz2), ktorá na koniec zoznamu zoz1 pripojí zoznam zoz2. Funkcia ako výsledok vráti začiatok takéhoto nového zoznamu. Nepoužívaj žiadne pomocné zoznamy (napríklad typu list). Napríklad:
```
>>> z1 = vyrob('ABC')
>>> z2 = vyrob('prst')
>>> z = spoj(z1, z2)
>>> vypis(z)
    'A' -> 'B' -> 'C' -> 'p' -> 'r' -> 's' -> 't' -> None
>>> vypis(spoj(None, Vrchol(1234)))
    1234 -> None
```

Napíš funkciu prevratena_kopia(zoznam), ktorá vytvorí a vráti z daného zoznamu nový zoznam. Tento bude mať všetky prvky z pôvodného v opačnom poradí. Pôvodný zoznam musí ostať bez zmeny. Nepoužívaj žiadne pomocné zoznamy (typ list). Napríklad:

>>> z1 = vyrob('python')
>>> vypis(z1)
    'p' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None
>>> z2 = prevratena_kopia(z1)
>>> vypis(z2)
    'n' -> 'o' -> 'h' -> 't' -> 'y' -> 'p' -> None
>>> vypis(z1)
    'p' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' -> None

Napíš funkciu mapuj(funkcia, zoznam), ktorá pre každý vrchol v danom zozname spustí zadanú funkciu s parametrom hodnota vo vrchole a ak to nespadne na chybe, zmení hodnotu vrcholu. Funkcia nič nevracia. Napríklad:

>>> zoz = vyrob((1, -2, 3, -4, 5, -6))
>>> mapuj(abs, zoz)
>>> vypis(zoz)
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
>>> mapuj(lambda x: x**2, zoz)
>>> vypis(zoz)
    1 -> 4 -> 9 -> 16 -> 25 -> 36 -> None

Napíš funkciu filtruj(podmienka, zoznam), ktorá zo zoznamu vyhodí všetky vrcholy, pre ktoré zavolanie parametra podmienka s hodnotou data nevráti True (alebo spadne na chybe). Napríklad:

>>> zoz = vyrob(range(5, 12))
>>> vypis(zoz)
    5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> None
>>> zoz = filtruj(lambda x: x%3==0, zoz)          # číslo je deliteľné 3
>>> vypis(zoz)
    6 -> 9 -> None

2. Týždenný projekt¶

Teoretická informatika sa zaoberá rôznymi modelmi strojov, ktoré sa viac alebo menej približujú reálnym počítačom (napríklad Turingov stroj). Veľmi známym modelom je aj RAM (Random-access machine), ktorý sa už trochu viac podobá na strojový kód súčasných procesorov. Najlepšie si ho môžeme predstaviť takto:

obsahuje nejakú množinu celočíselných registrov, ktoré sú očíslované od 0 po nejaké maximum - budeme tomuto hovoriť pamäť počítača, ich očíslovaniu budeme hovoriť adresa - obsah registrov sa bude môcť meniť; je to vlastne zoznam celočíselných premenných, ktoré majú mená od 0 po nejaké zadané maximum
bude pracovať s postupnosťou inštrukcií - aj táto postupnosť je očíslovaná od 0, pričom každá inštrukcia môže mať aj nejaké svoje parametre - tejto postupnosti hovoríme program
do takéhoto počítača vieme poslať aj nejaký vstup (postupnosť celých čísel), ktorý si môžeme predstaviť ako pásku, na ktorej sú na začiatku pripravené nejaké hodnoty - samotný program môže túto pásku postupne čítať, ale nevie sa už ku skôr prečítaným hodnotám vrátiť
z počítača môže vychádzať aj nejaký výstup (postupnosť celých čísel), ktorý si môžeme predstaviť tiež ako pásku - na túto pásku môže program postupne zapisovať nejaké číselné údaje
samotný počítač dostáva na začiatku program, (zatiaľ prázdnu) pamäť registrov, pripravenú vstupnú pásku a pripravenú (zatiaľ prázdnu) výstupnú pásku
keď sa počítač naštartuje (tlačidlom START), začne vykonávať inštrukciu za inštrukciou (začne s inštrukciou číslo 0) a pokračuje, kým neprejde na neexistujúce číslo inštrukcie alebo dosiahne špeciálnu inštrukciu halt

Inštrukcie počítača¶

Naša verzia RAM pozná tieto inštrukcie (identifikátorom reg tu budeme označovať našu pamäť registrov):

halt - počítač zastane
nop - inštrukcia sa ignoruje (označuje no operation a zodpovedá pythonovskému pass)
read adresa - prečíta ďalšiu hodnotu zo vstupnej pásky a vloží ju do registra s daným číslom (adresou) - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa] = int(input())
print adresa - vyberie z pamäti (z registra s danou adresou) nejakú hodnotu a zapíše ju na výstupnú pásku - v Pythone by sme si túto inštrukciu mohli predstaviť ako print(reg[adresa])

Teraz by sme už vedeli zapísať náš prvý program:

read 0       # do 0. registra prečíta prvú hodnotu zo vstupu
read 1       # do 1. registra prečíta ďalšiu hodnotu zo vstupu
print 1      # na výstup dá hodnotu 1. registra
print 0      # na výstup dá hodnotu 0. registra

Tento program prečíta zo vstupu dve čísla a vypíše ich na výstup v opačnom poradí: najprv druhé a potom prvé. Všimni si komentáre, ktoré sa podobajú komentárom v Pythone. Na koniec programu nemusíme písať inštrukciu halt, lebo počítač automaticky zastane, keď už nemá ďalšie inštrukcie.

Ďalej vymenujeme inštrukcie, ktoré pracujú s číslami v registroch:

const adresa číslo - do registra s danou adresou sa priradí zadané číslo - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa] = číslo
add adresa1 adresa2 - do registra s danou adresou adresa1 sa pripočíta obsah registra s adresou adresa2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa1] += reg[adresa2]
sub adresa1 adresa2 - od registra s danou adresou adresa1 sa odpočíta obsah registra s adresou adresa2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa1] -= reg[adresa2]
mul adresa1 adresa2 - register s danou adresou adresa1 sa vynásobí obsahom registra s adresou adresa2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa1] *= reg[adresa2]
div adresa1 adresa2 - register s danou adresou adresa1 sa vydelí obsahom registra s adresou adresa2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa1] //= reg[adresa2] (ak by sme chceli deliť nulou, vyvolá sa výnimka RAMError)

Ďalej nasleduje malá ukážka týchto inštrukcií (pre lepšiu čitateľnosť budeme registrom dávať v komentároch nejaké identifikátory):

read 0      # n ... prečíta číslo zo vstupu do registra 0
const 1 10  # konštanta 10 ... do registra 1 si pripraví konštantu 10
const 2 0   # cs = 0 ... do registra 2 priradí 0 (fungovalo by aj sub 2 2)
const 3 0   # pom = 0
add 3 0     # pom = n
div 3 1     # pom = n // 10
mul 3 1     # pom = n // 10 * 10
add 2 0     # cs += n            ...
sub 2 3     # cs -= pom ... teda cs -= n // 10 * 10 ... teda cs = n % 10
div 0 1     # n = n // 10
add 2 0     # cs += n
print 2     # print(cs)

Všimni si, že tento program počíta ciferný súčet dvojciferného čísla zo vstupu. Ak by sme tento program spustili so vstupom (na vstupnej páske) 85, na výstupnej páske by sme dostali jedinú hodnotu 13.

Počítač RAM nemá záporné čísla. Okrem toho, pri štarte programu treba počítaču oznámiť, aký bude rozsah registrov (počet bajtov, ktorý bude zaberať každý register) a pamäť bude odteraz „osekávať“ každú vkladanú hodnotu na tento zadaný počet bajtov (napríklad, pre jednobajtovú pamäť bude robiť zvyšok po delení 256). Vďaka tomuto sa v registroch ukladajú len nezáporné čísla a aj to len v danom rozsahu (pre jednobajtovú pamäť od 0 do 255). Teraz si pozrime program, ktorý sa spustí v jednobajtovej pamäti:

const 0 50   # a = 50
const 1 200  # b = 200
sub 0 1      # a -= b
print 0      # a

Asi by sme tu očakávali výsledok -150, lenže pri vkladaní tejto hodnoty do registra 0 (inštrukciou sub 0 1) sa urobí zvyšok po delení číslom 256 a tým dostávame výsledok 106. Ak by sme tento program spustili v dvojbajtovej pamäti, výsledkom by bolo číslo 65386 (robí sa zvyšok po delení číslom 256**2, t.j. 65536). Zrejme podobný efekt dostaneme, keď budeme sčítavať, resp. násobiť dostatočne veľké čísla.

Ďalšími inštrukciami sú skokové inštrukcie. Pomocou nich sa riadenie neprenesie na nasledovnú inštrukciu, ale na inštrukciu zadanú ako parameter príkazu:

jump padresa - program pokračuje na inštrukcii podľa zadanej padresa, napríklad jump 0 označuje skok na úplný začiatok programu
jz adresa padresa - toto je podmienený skok (z anglického jump if zero): najprv sa skontroluje obsah registra na adresa a až keď je tento nulový, program pokračuje na inštrukcii podľa zadanej padresa, napríklad jz 1 2 označuje, že ak má 1. register nulový obsah, pokračuje sa na inštrukcii 2 (inak pokračuje na ďalšej inštrukcii) - v Pythone by sme si túto inštrukciu mohli predstaviť ako if reg[adresa] == 0: jump padresa
jnz adresa padresa - toto je opäť podmienený skok (z anglického jump if not zero): najprv sa skontroluje obsah registra na adresa a až keď je tento nenulový, program pokračuje na inštrukcii podľa zadanej padresa, napríklad jnz 1 2 označuje, že ak je 1. register nenulový, pokračuje sa na inštrukcii 2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako if reg[adresa] != 0: jump padresa
jl adresa1 adresa2 padresa - toto je ďalší podmienený skok (z anglického jump if less): najprv sa porovná obsah dvoch registrov na adresa1 a adresa2 a až keď je prvý z nich menší ako druhý, program pokračuje na inštrukcii podľa zadanej padresa, napríklad jl 1 2 3 označuje, že ak je 1. register menší ako 2. register, pokračuje sa na inštrukcii 3 - v Pythone by sme si túto inštrukciu mohli predstaviť ako if reg[adresa1] < reg[adresa2]: jump padresa

Nasledovný program ilustruje použitie inštrukcie jnz:

read 0     # n = input()
const 1 1  # konštanta 1
const 2 0  # sucet = 0
add 2 0    # sucet += n     # riadok programu na adrese 3
sub 0 1    # n -= 1
jnz 0 3    # if n != 0: jump 3
print 2    # print(sucet)

Program počíta súčet čísel od 1 do n (číslo na vstupe). Zamysli sa nad tým, čo sa stane, keď na vstupe bude hodnota 0.

Ak v programe, ktorý počítal ciferný súčet dvojciferného čísla nahradíme inštrukciu na adrese 10: add 2 0 # cs += n skokovou inštrukciou jnz 0 3, tento program bude počítať ciferný súčet ľubovoľne veľkého čísla (nielen dvojciferného).

Poslednú skupinu tvoria dve inštrukcie na prácu s nepriamou adresáciou:

load adresa1 adresa2 - adresa2 označuje adresu registra, v ktorom sa ale nachádza adresa iného registra, inštrukcia load hodnotu tohoto nepriameho registra prekopíruje do registra na adresa1 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[adresa1] = reg[reg[adresa2]]
store adresa1 adresa2 - adresa1 označuje adresu registra, v ktorom sa ale nachádza adresa iného registra, inštrukcia store do tohoto nepriameho registra prekopíruje hodnotu registra na adresa2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako reg[reg[adresa1]] = reg[adresa2]

Pomocou nepriamej adresácie môžeme pracovať aj s poľom (nejakou postupnosťou celých čísel). Napríklad:

const 0 5   # adresa registra, kde začína výsledné pole
read 1      # n = input()
const 2 1   # konštanta 1
const 3 1   # i = 1
add 4 0     # pom = adresa pola
store 4 3   # reg[pom] = i     # riadok programu na adrese 5
add 3 2     # i += 1
add 4 2     # pom += 1
sub 1 2     # n -= 1
jnz 1 5     # if n != 0: jump 5

Tento program pripraví n-prvkové pole s hodnotami 1, 2, …, n. Adresa začiatku tohto poľa je v registri 0. Ak by sme vypísali obsah pamäte, dostali by sme takéto niečo (na vstupe bola hodnota 8):

reg: 5 0 1 9 13 1 2 3 4 5 6 7 8

V registri 0. je adresa začiatku poľa, teda na adrese 5 začína osem prvkov poľa. V registri 1. je momentálna hodnota n, keďže sme ju v cykle znižovali o 1, po skončení cyklu tu musí byť 0. V registri 2 je konštanta 1, v registri 3 je premenná i - tá postupne nadobúdala hodnoty od 1 do 9 a v registri 4 je momentálna adresa v poli - tu boli postupne hodnoty 5 (začiatok poľa), 6 (ďalší prvok poľa), … 13 (prvok za posledným v poli).

Napíš program, ktorý definuje simulátor počítača RAM:

class RAMError(Exception): pass

class Registers:
    def __init__(self, num_bytes, maximum):
        self._mem = []
        ...

    def get(self, address):
        return 0

    def set(self, address, value):
        ...

    def __repr__(self):
        return 'reg: ...'

class RAM:
    def __init__(self, program):
        ...

    def start(self, input='', num_bytes=2, maximum=1000):
        self.reg = Registers(num_bytes, maximum)
        ...

    def __repr__(self):
        return repr(self.reg)

    def instruction(self, pc, instr, *param):
        ...
        return pc + 1

Trieda RAMError slúži na vyvolanie chybových stavov (napríklad pre chybný počet parametrov inštrukcie, chybnú inštrukciu, delenie nulou).

Trieda Registers zabezpečuje prácu pamäti registrov. Metódy fungujú takto:

__init__(num_bytes, maximum) - inicializuje zatiaľ prázdnu pamäť registrov (atribút _mem), v ktorej budú mať registre zadaný rozsah bajtov (parameter num_bytes) a ktorá bude mať zadané maximum (maximálny počet registrov v pamäti)
get(address) - vráti momentálny obsah registra address; ak tento register ešte neexistoval, vráti hodnotu 0
set(address, value) - do daného registra address priradí zadanú hodnotu; ak je value mimo rozsahu bajtov, oreže ju (napríklad pre hodnotu -150 s rozsahom 1 bajt, do registra vloží 106); ak tento register zatiaľ ešte neexistoval (ešte sa do neho nepriradzovalo), vytvorí ho s 0 hodnotou a prípadne vytvorí aj všetky ešte neexistujúce registre s menšou adresou (napríklad, pre zatiaľ prázdnu pamäť inštrukcia const 3 42 vytvorí 4 registre reg: 0 0 0 42); ak je adresa mimo maximálny rozsah maximum, žiaden register sa nevytvorí
__repr__() - vráti obsah pamäte registrov v tvare 'reg: číslo číslo ...'

Trieda RAM simuluje činnosť RAM počítača a pomáha si pritom objektom Registers. Metódy:

__init__(program) - dostáva program ako znakový reťazec, v ktorom sú v riadkoch inštrukcie aj s parametrami oddelené aspoň jednou medzerou; komentáre a prázdne riadky by sa pritom mali ignorovať
start(input, num_bytes, maximum) - nastaví prázdnu pamäť registrov (atribút reg) s daným rozsahom bajtov (parameter num_bytes) a s daným maximálnym počtom registrov (parameter maximum); parameter input obsahuje vstupnú pásku; metóda spustí vykonávanie programu od adresy 0 (pc tzv. program counter); vykonávanie programu skončí vtedy, keď pc bude mimo rozsah adries inštrukcií; táto metóda sa môže spustiť viackrát - zakaždým s prázdnou pamäťou a možno s rôznymi vstupmi; metóda vráti výstupnú pásku ako zoznam (pythonovský list) celých čísel
instruction(pc, instr, *param) - vykoná jednu inštrukciu s danými parametrami; funkcia vráti adresu inštrukcie, na ktorej sa bude pokračovať (najčastejšie to bude hodnota pc + 1), kde pc je momentálna adresa; funkcia vráti -1 pre inštrukciu halt

Obmedzenia¶

svoje riešenie odovzdaj v súbore riesenie.py, pričom sa v ňom budú nachádzať len tri definície tried RAMError, Registers, RAM, prípadne aj dve globálne premenné prog1 a prog2

prvé tri riadky tohto súboru budú obsahovať:

# 2. zadanie: ram
# autor: Janko Hrasko
# datum: 25.2.2023

zrejme ako autora uvedieš svoje meno
program by nemal počas testovania testovačom nič vypisovať (žiadne tvoje testovacie print())

Testovanie¶

Napríklad, po otestovaní:

if __name__ == '__main__':
    ram = RAM('''
     const 0 5  # adresa, kde začína výsledné pole
     read 1     # n = input()
     const 2 1  # konštanta 1
     const 3 1  # i = 1
     add 4 0    # pom = adresa začiatku poľa
     # adresa 5:
     store 4 3  # reg[pom] = i
     add 3 2    # i += 1
     add 4 2    # pom += 1
     sub 1 2    # n -= 1
     jnz 1 5    # if n != 0: jump 5
    ''')
    ram.start('8', 1)       # vstupná páska '8', počet bajtov pre registre je 1
    print(ram)

dostaneš výstup:

reg: 5 0 1 9 13 1 2 3 4 5 6 7 8

Všimni si, že riadok s komentárom # adresa 5: neobsahuje žiaden príkaz, preto až nasledovný riadok je na adrese 5.

Okrem dvoch tried Registers a RAM vo výslednom projekte zadefinuj aj dve premenné prog1 a prog2, ktoré budú obsahovať riešenie týchto dvoch úloh v jazyku RAM:

prečíta dve čísla n a k a vypíše hodnotu n ** k
zo vstupu číta čísla až po prvú 0, tieto čísla ukladá do poľa (adresa poľa je v registri 0) a potom vypíše tieto číselné informácie: počet čísel (veľkosť poľa), ich súčet, ich priemer (celá časť priemeru) a počet nadpriemerných hodnôt (počet prvkov poľa, ktorých hodnota je väčšia ako priemer); program by nemal spadnúť ani pri prázdnom vstupnom poli (na vstupe je len 0); testovač bude kontrolovať aj obsah pamäti od adresy, kde je začiatok poľa (podľa registra 0)

Testovač bude testovať aj tieto tvoje dva programy. Za ich správne riešenie získaš 20% z celkového hodnotenia.

Projekt riesenie.py odovzdávaj na úlohový server https://list.fmph.uniba.sk/. Za tento projekt môžeš získať 5 bodov.