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

  • 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. 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. čí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.

  • 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. takto:

šesťprvkový spájaný zoznam

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

tri izolované vrcholy

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.

pripojený vrchol v2 k v1

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.

tri pospájané vrcholy

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:

obsah pamäti po vyhodení premenných v2 a v3

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

vizualizácia v pythontutor.com

Spájané vytváranie vrcholov

Pozrite tento zápis:

>>> a = Vrchol('a')
>>> b = Vrchol('b')
dva izolované vrcholy
>>> a.next = b
spiojené dva vrcholy
>>> del b
zrušená premenná 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.:

>>> 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':

šesťprvkový zoznam s písmenami Python

Výpis pomocou cyklu

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

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

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

štvorprvkový zoznam

Teraz treba vypísať všetky jeho hodnoty postupne od prvej po poslednú, môžeme to urobiť napr. 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, najskôr 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:

posunutie referencie na nasledovníka

postupne dostávame:

posunutie referencie na nasledovníka

posunutie referencie na nasledovníka

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

posunutie referencie na nasledovníka

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 bude potrebné si uchovať referenciu na začiatok zoznamu, resp. v takomto cykle nebude pracovať priamo s premennou v1, ale s jej kópiou, napr. 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:

posunutie na nasledovníka s pomocnou premennou

posunutie na nasledovníka s pomocnou premennou

posunutie na nasledovníka s pomocnou premennou

posunutie na nasledovníka s pomocnou premennou

posunutie na nasledovníka s pomocnou premennou

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(zoznam.data, end=' -> ')
        zoznam = zoznam.next
    print(None)

Pri volaní funkcie sa do formálneho parametra zoznam priradí hodnota skutočného parametra (napr. 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. 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. zoznam, zoz, zac, z (ako začiatok zoznamu) alebo niekedy aj po anglicky head (hlavička zoznamu).

Postupné prechádzanie vrcholov zoznamu

Spôsob, akým sa prechádzajú všetky vrcholy zoznamu pomocou while-cyklu, bude užitočný aj na riešenie iných úloh. Často sa preto použije práve takáto schéma algoritmu:

pom = zoznam
while pom is not None:
    # spracuj vrchol s referenciou pom
    pom = pom.next

Vytvorenie zoznamu pomocou cyklu

Zoznamy sa 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 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
prázdny zoznam

Vytvoríme prvý vrchol s hodnotou 0:

>>> pom = Vrchol(0)
jednoprvkový zoznam

a dáme ho na začiatok:

>>> zoz = pom
jednoprvkový zoznam

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

Vytvoríme druhý vrchol:

>>> pom = Vrchol(1)
nový vrchol

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

>>> pom.next = zoz
pripojí pred doterajší začiatok

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

>>> zoz = pom
nový vrchol sa stáva novým začiatkom

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
vyrobí nový vrchol

pripojí pred doterajší začiatok

stáva sa novým začiatkom
>>> pom = Vrchol(3)
>>> pom.next = zoz
>>> zoz = pom
na začiatok pridá nový vrchol

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                    # zatial este prazdny 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

kompletný zoznam čísel od 9 po 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:

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

Pridanie nového vrcholu na začiatok zoznamu

Zapamätajte si, že zápis zoz = Vrchol(hodnota, zoz) pre zoz, ktorý referencuje na začiatok zoznamu, znamená pridanie nového vrcholu na začiatok zoznamu.

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.

>>> 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. ak sú vstupnou postupnosťou riadky otvoreného textového súboru, tak takúto postupnosť 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.

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

>>> 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 jednoduchá funkcia, 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á vloží na koniec zoznamu 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 bude treba nájsť posledný vrchol zoznamu a tomuto vrcholu zmeníme jeho atribút next, t.j. 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:

Hľadanie posledného vrcholu zoznamu

Aj práca s posledným vrcholom zoznamu sa môže vyskytnúť v našich programoch. Preto najčastejšie použijeme takýto zápis:

if zoz is None:
    '''spracuj prípad, keď zoznam je prázdny'''
else:
    posledny = zoz
    while posledny.next is not None:
        posledny = posledny.next
    '''spracuj posledný vrchol'''

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                          # 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                          # 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 pom 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 zadané pred_hodnotu.



Cvičenia

L.I.S.T.

  1. Bez spúšťania na počítači zisti, čo urobia nasledovné programy.

    • predpokladaj tieto deklarácie a funkcie z prednášky:

      class Vrchol:
          def __init__(self, data, next=None):
              self.data, self.next = data, next
      
      def vypis(zoznam):
          while zoznam is not None:
              print(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('A')
      v2 = Vrchol('B')
      v3 = Vrchol('C')
      v4 = Vrchol('D')
      v3.next = v1
      v1.next = v2
      v2.next = v3
      v1.next = v4
      zoz = v2
      vypis(zoz)
      
    • druhý spájaný zoznam:

      v1 = None
      v2 = Vrchol('X', v1)
      v2 = Vrchol('Y', v2)
      v3 = Vrchol('Z', v1)
      v3 = Vrchol('T', v3)
      v2 = Vrchol('U', v2)
      v3.next.next = v2
      vypis(v3)
      

  1. Skonštruuj zoznam tak, aby si dostal požadovaný výstup.

    • >>> z = ...
      >>> vypis(z)
      2 -> 3 -> 5 -> sedem -> 11 -> None -> 13 -> None
      

  1. Máme daný zoznam, ktorý má aspoň 3 prvky. Oprav ho tak, aby jeho druhý prvok obsahoval číslo -99.

    • napr.

      >>> zoz = ...
      >>> vypis(zoz)
      0 -> 1 -> 2 -> 3 -> None
      >>> ... oprav 2. prvok
      >>> vypis(zoz)
      0 -> -99 -> 2 -> 3 -> None
      

  1. Máme daný neprázdny zoznam. Vlož za prvý prvok nový vrchol s hodnotou 'abc'.

    • napr.

      >>> zoz = ...
      >>> vypis(zoz)
      prvy -> druhy -> treti -> None
      >>> ... vlož nový vrchol za prvý prvok
      >>> vypis(zoz)
      prvy -> abc -> druhy -> treti -> None
      

  1. Napíš funkciu vynuluj(zoznam), ktorá v danom zozname zmení hodnoty v každom vrchole na číslo 0. Funkcia nič nevracia.

    • napr.

      >>> zoz = ...
      >>> vypis(zoz)
      prvy -> abc -> druhy -> treti -> None
      >>> vynuluj(zoz)
      >>> vypis(zoz)
      0 -> 0 -> 0 -> 0 -> None
      

  1. Napíš funkciu pocty(zoznam), ktorá vráti dve čísla: počet vrcholov, ktoré majú číselné hodnoty (int alebo float) a počet vrcholov, ktoré nemajú.

    • napr.

      >>> zoz = ...
      >>> vypis(zoz)
      prvy -> 2 -> druhy -> 3.14 -> [3]-> None
      >>> pocty(zoz)
      (2, 3)
      

  1. Napíš funkciu pripocitaj1(zoznam), ktorá ku každému prvku zoznamu pripočíta 1, ale len vtedy, ak sa dá (nevznikne pritom chyba), inak tento prvok nezmení a pokračuje na ďalších. Funkcia nič nevracia.

    • napr.

      >>> zoz = ...
      >>> vypis(zoz)
      11 -> 12 -> 13.5 -> a -> (2, 3) -> 14 -> None
      >>> pripocitaj1(zoz)
      >>> vypis(zoz)
      12 -> 13 -> 14.5 -> a -> (2, 3) -> 15 -> None
      

  1. Prerob funkciu vypis() na novy_vypis(zoznam) tak, aby najprv z jednotlivých prvkov spájaného zoznamu vytvorila zoznam (list) reťazcov a až na záver z toho pomocou ' -> '.join(...) vyrobí reťazec, ktorý potom vypíše.

    • otestuj tento nový výpis aj pre dlhý zoznam (najprv s pôvodnou verziou a potom s prerobenou):

      >>> vypis(vyrob(range(1000)))
      ...
      >>> novy_vypis(vyrob(range(1000)))
      ...
      

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

    • pre spájaný zoznam:

      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)
      

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

    • napr.

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

  1. Napíš funkciu vloz_za(zoznam, hodnota1, hodnota2), ktorá v danom zozname vyhľadá vrchol s danou hodnotou hodnota1 a za neho vloží nový vrchol s hodnotou hodnota2. Ak taký vrchol neexistuje, funkcia nerobí nič. Funkcia nič nevracia.

    • napr.

      >>> y = ...
      >>> vypis(y)
      3 -> 7 -> a -> a -> 11 -> None
      >>> vloz_za(y, 'a', 9)
      >>> vypis(y)
      3 -> 7 -> a -> 9 -> a -> 11 -> None
      >>> vloz_za(y, 11, 13)
      >>> vypis(y)
      3 -> 7 -> a -> 9 -> a -> 11 -> 13 -> None
      

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

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

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

    • napr.

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

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

    • napr.

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

  1. Napíš rekurzívnu verziu funkcie pocet(zoznam), t.j. funkcia prejde všetky prvky zoznamu bez použitia cyklu len pomocou rekurzie. Do definície funkcie nepridávaj ďalšie parametre.

    • napr.

      >>> zoz = vyrob(range(10, 20))
      >>> pocet(zoz)
      10
      >>> pocet(zoz.next)
      9
      >>> pocet(None)
      0
      

  1. 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. typu list).

    • napr.

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

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

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

  1. Napíš funkciu oprav(zoznam, funkcia), 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.

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

  1. Napíšte funkciu vyhod(zoznam, podmienka), ktorá zo zoznamu vyhodí všetky vrcholy, pre ktoré zavolanie parametra podmienka s hodnotou data vráti True.

    • napr.

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


3. Domáce zadanie

L.I.S.T.

Poznáme Turingov stroj, pomocou ktorého vieme „naprogramovať“ jeho správanie v závislosti s informáciami na nekonečnej páske. V tomto prípade takýmto programom je množina pravidiel a Turingov stroj z nich v každom kroku vyberie jedno vhodné pravidlo a vykoná požadovanú akciu (zmení symbol na páske, posunie sa na susednú pozíciu, zmení stav).

Existujú aj iné takéto modely, ktoré sa viac alebo menej približujú reálnym počítačom. 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 predstavíme 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ť adresy - obsah registrov sa bude môcť meniť

  • bude pracovať s postupnosťou inštrukcií - aj táto postupnosť je očíslovaná od O, pričom každá inštrukcia môže mať aj nejaké svoje parametre - tejto postupnosti hovoríme program

  • do takéhoto stroja 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 túto pásku môže postupne čítať, ale nevie sa už ku skôr prečítaným hodnotám vrátiť

  • zo stroja 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äť, 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 čislo inštrukcie alebo dosiahne špeciálnu inštrukciu halt

Inštrukcie počítača

Naša verzia RAM pozná tieto inštrukcie (identifikátorom mem tu bude 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 mem[adresa] = 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(mem[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šimnite 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:

  • init adresa číslo - do registra s danou adresou sa priradí zadané číslo - v Pythone by sme si túto inštrukciu mohli predstaviť ako mem[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 mem[adresa1] += mem[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 mem[adresa1] -= mem[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 mem[adresa1] *= mem[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 mem[adresa1] //= mem[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
init 1 10  # k10 ... pripravíme si konštantu 10
init 2 0   # cs = 0 ... do registra 2 priradí 0 (fungovalo by aj sub 2 2)
init 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šimnite 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 pre každý register) a pamäť bude odteraz „osekávať“ každú vkladanú hodnotu na tento zadaný počet bajtov (napr. 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). Pozrite tento program, ktorý spustíme v jednobajtovej pamäti:

init 0 50
init 1 200
sub 0 1
print 0

Chceme vypočítať -150, lenže pri vkladaní tejto hodnoty do registra 0 (inštrukciou sub 0 1) sa urobí zvyšok po delení číslom 256 a 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čitovať, 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. jump 0 označuje skok na úplný začiatok programu

  • jz adresa padresa - toto je podmienený skok: najprv sa skontroluje obsah registra na adresa a až keď je tento nulový, program pokračuje na inštrukcii podľa zadanej padresa, napr. jz 1 2 označuje, že ak je 1. register nulový, pokračuje sa na inštrukcii 2 - v Pythone by sme si túto inštrukciu mohli predstaviť ako if mem[adresa] == 0: jump padresa

  • jnz adresa padresa - toto je opäť podmienený skok: najprv sa skontroluje obsah registra na adresa a až keď je tento nenulový, program pokračuje na inštrukcii podľa zadanej padresa, napr. 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 mem[adresa] != 0: jump padresa

  • jlt adresa1 adresa2 padresa - toto je ďalší podmienený skok: najprv sa porovná obsah dvoch registrov na adresa1 a adresa2 a až keď prvý z nich menší ako druhý, program pokračuje na inštrukcii podľa zadanej padresa, napr. jlt 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 mem[adresa1] < mem[adresa2]: jump padresa

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

read 0     # n = input()
init 1 1   # konštanta 1
init 2 0   # sucet = 0
# adresa 3:
add 2 0    # sucet += n
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). Zamyslite 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 add 2 0    # cs += n skokovou inštrukciou jnz 0 3, bude tento program 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 mem[adresa1] = mem[mem[adresa2]]

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

Pomocou nepriamej adresácie môžeme pracovať aj s poľami (nejakými postupnosťami celých čísel). Napr.

init 0 5   # adresa, kde začína výsledné pole
read 1     # n = input()
init 2 1   # konštanta 1
init 3 1   # i = 1
add 4 0    # pom = adresa pola
# adresa 5:
save 4 3   # mem[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

Tento program pripraví n-prvkové pole s hodnotami 1, 2, …, n. Adresa 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):

mem: 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 poľa - tu boli postupne hodnoty 5 (začiatok poľa), 6 (ďalší prvok poľa), … 13 (prvok za posledným v poli).

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

class RAMError(Exception): pass

class Memory:
    def __init__(self, pocet_bajtov=2, maximum=1000):
        self._pamat = []
        ...

    def get(self, adresa):
        return 0

    def set(self, adresa, hodnota):
        ...

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

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

    def start(self, input='', pocet_bajtov, maximum):
        self.mem = Memory(pocet_bajtov, maximum)
        ...

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

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

Trieda Memory zabezpečuje prácu všetkých registrov. Metódy fungujú takto:

  • __init__(pocet_bajtov, maximum) - inicializuje zatiaľ prázdnu pamäť, v ktorej budú mať registre zadaný rozsah bajtov a ktorá bude mať zadané maximum

  • get(adresa) - vráti momentálny obsah registra adresa; ak tento register ešte neexistoval, vráti hodnotu 0

  • set(adresa, hodnota) - do daného registra adresa priradí zadanú hodnotu; ak je hodnota mimo rozsahu bajtov, oreže ju (napr. 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. pre zatiaľ prázdnu pamäť inštrukcia init 3 42 vytvorí 4 registre mem: 0 0 0 42); ak je adresa mimo maximálny rozsah maximum, žiaden register sa nevytvorí

  • __repr__() - vráti obsah pamäte v tvare 'mem: číslo číslo ...'

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

  • __init__(prog) - 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, pocet_bajtov, maximum) - nastaví prázdnu pamäť registrov (atribút mem) s daným rozsahom bajtov (parameter pocet_bajtov) a s daným maximálnym počtom registrov (parameter maximum); parameter input obsahuje vstupnú pásku; potom spustí vykonávanie programu od adresy 0 (pc``tzv. program counter); vykonávanie programu skončí vtedy, keď ``pc bude mimo rozsahu 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

  • command(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

  • vaše riešenie odovzdajte v súbore riesenie3.py, pričom sa v ňom budú nachádzať len tri definície tried RAMError, Memory, RAM, prípadne aj dve globálne premenné prog1 a prog2

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

    # 3. zadanie: ram
    # autor: Janko Hrasko
    # datum: 10.3.2019
    
  • zrejme ako autora uvediete svoje meno

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

Testovanie

Napr. po otestovaní:

ram = RAM('''
 init 0 5   # adresa, kde začína výsledné pole
 read 1     # n = input()
 init 2 1   # konštanta 1
 init 3 1   # i = 1
 add 4 0    # pom = adresa pola
 # adresa 5:
 save 4 3   # mem[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.mem)

dostaneme výstup:

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

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

  1. prečíta dve čísla n a k a vypíše hodnotu n ** k

  2. 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 vaše dva programy. Za ich správne riešenie získavate 20% z hodnotenia.

Projekt riesenie3.py odovzdávajte na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 21. marca. Za tento projekt môžete získať 10 bodov.