Priebežný test z Programovania (2) 2023/2024 - Variant A

  1. Máme tento turingov stroj:

    (x, x) -> (a, >, y)
    (x, y) -> (c, >, z)
    (y, x) -> (b, >, z)
    (y, y) -> (a, >, x)
    (z, x) -> (b, >, x)
    (z, y) -> (c, >, y)
    (z, _) -> (a, <, end)
    

    Napíš funkciu turing(retazec), ktorá odsimuluje tento turingov stroj so vstupným reťazcom pásky. Funkcia vráti výsledný obsah pásky (bez prázdnych znakov) alebo None v prípade, že turingov stroj zadaný vstup neakceptoval. Napríklad:

    >>> print(turing('a'))
        None
    >>> print(turing('y'))
        ca
    

    Môže ti pomôcť zhustená definícia turingovho stroja:

    x x a > y
    x y c > z
    y x b > z
    y y a > x
    z x b > x
    z y c > y
    z _ a < end
    

  1. Napíš funkciu zlucuj(zoznam), ktorá prerobí prvky spájaného zoznamu takto: z troch za sebou idúcich prvkov vyrobí jeden, ktorý bude obsahovať trojicu (tuple) z hodnôt týchto troch prvkov. Takýchto trojíc vytvorí čo najviac, pričom, ak dĺžka zoznamu nie je deliteľná tromi, tak zoznam začne prvkami bez trojíc. Napríklad, zoznam 1->2->3->4->5->6->7->8 prerobí na 1->2->(3,4,5)->(6,7,8). Funkcia nič nevracia, lebo začiatok zoznamu sa ňou nezmení:

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

  1. Máme daný prefixový celočíselný výraz s operátormi +, -, *, /, kde operandmi sú celé čísla a premenná x. Napíš funkciu vysledky(prefix, hodnoty), ktorá postupne zistí hodnoty zadaného prefixového výrazu pre všetky hodnoty premennej x z postupnosti hodnoty. Operácia / reprezentuje celočíselné delenie. Môžeš predpokladať, že prefixový výraz je zadaný korektne, hoci pre niektoré x môže spôsobiť výnimku (vtedy sa nezaradí do výsledkov). Funkcia vráti množinu celých čísel. Napríklad:

    >>> vysledky('* + x 1 x', range(1, 6))
        {2, 6, 12, 20, 30}
    

  1. Napíš funkciu preorder(postupnost), ktorá vygeneruje (pomocou yield) preorder postupnosť vrcholov z binárneho vyhľadávacieho stromu, ktorý by sa vytvoril zo zadanej postupnosti (postupným pridávaním do stromu). Napríklad:

    >>> x = preorder((3, 5, 1))
    >>> x
        <generator object preorder>
    >>> print(*x)
        3 1 5
    

  1. Napíš funkciu pocet(mnozina), ktorá dostáva ako parameter množinu slov (reťazcov) a zistí počet vrcholov prefixového stromu (trie), ktorý by sa vytvoril z týchto slov. Napríklad:

    >>> pocet({'abc', 'aba'})
        5
    

  1. Napíš funkciu vsetky(slovo), ktorá vygeneruje (pomocou yield) všetky rôzne slová zložené z rovnakých písmen, ako má zadané slovo. Môžeš počítať s tým, že všetky písmená v zadanom slove sú rôzne. Napríklad:

    >>> mn = vsetky('abc')
    >>> mn
        <generator object vsetky>
    >>> print(*mn)
        bac acb cab bca abc cba
    

  1. Neorientovaný graf je zadaný vymenovaním hrán (zoznam dvojíc čísel). Napíš funkciu zisti(hrany), ktorá zistí všetky také trojice vrcholov, ktoré sú navzájom spojené hranami každý s každým. Funkcia vráti množinu všetkých takýchto trojíc (tuple) vrcholov. Do tejto množiny zaraďuj trojice vrcholov v rastucej postupnosti ich čísel:

    >>> zisti(((2, 1), (2, 3), (1, 3)))
        {(1, 2, 3)}
    >>> zisti(((2, 1), (2, 3), (1, 4), (4, 3)))
        set()
    


Riešenie odovzdaj v súbore test.py (môžeš si ho stiahnuť z L.I.S.T.u), pričom prvé tri riadky súboru budú obsahovať:

# test z programovania variant A 2023/2024
# student: Janko Hrasko
# datum: 21.5.2024

zrejme ako študenta uvedieš svoje meno.