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

  1. Máme tento turingov stroj:

    (x, x) -> (x, >, y)
    (x, y) -> (x, >, z)
    (y, x) -> (y, >, z)
    (y, y) -> (y, >, x)
    (y, _) -> (y, <, end)
    (z, x) -> (z, >, x)
    (z, y) -> (z, >, y)
    (z, _) -> (z, <, 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'))
        xz
    

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

    x x x > y
    x y x > z
    y x y > z
    y y y > x
    y _ y < end
    z x z > x
    z y z > y
    z _ z < end
    

  1. Napíš funkciu spajaj(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 ukončí 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 spajaj(zoznam):
        ...
    

  1. Máme daný postfixový výraz s operátormi +, -, *, /, kde operandmi sú desatinné čísla a premenná x. Napíš funkciu skus(postfix, hodnoty), ktorá postupne zistí hodnoty zadaného postfixového výrazu pre všetky hodnoty premennej x z postupnosti hodnoty. Môžeš predpokladať, že postfixový výraz je zadaný korektne, hoci pre niektoré x môže spôsobiť výnimku (vtedy sa nezaradí do výsledkov). Funkcia vráti zoznam desatinných čísel (v ľubovoľnom poradí). Napríklad:

    >>> skus('x 0.25 - x *', (0.5, 1, 1.5))
        [0.125, 0.75, 1.875]
    

  1. Napíš funkciu postorder(postupnost), ktorá vygeneruje (pomocou yield) postorder 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 = postorder((3, 5, 1))
    >>> x
        <generator object postorder>
    >>> print(*x)
        1 5 3
    

  1. Napíš funkciu pocet2(mnozina), ktorá dostáva ako parameter množinu slov (reťazcov) a zistí počet vrcholov prefixového stromu (trie), ktoré majú aspoň dvoch potomkov. Tento prefixový strom by sa vytvoril zo slov v danej množine. Napríklad:

    >>> pocet2({'abc', 'aba'})
        1
    

  1. Napíš funkciu permutacie(slovo), ktorá vráti množinu všetkých rôznych slov, ktoré sú 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:

    >>> permutacie('abc')
        {'bac', 'acb', 'cab', 'bca', 'abc', 'cba'}
    

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

    >>> print('vysledok =', *trojuholniky(((2, 1), (2, 3), (1, 3))))
        vysledok = (1, 2, 3)
    >>> print('vysledok =', *trojuholniky(((2, 1), (2, 3), (1, 4), (4, 3))))
        vysledok =
    


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 B 2023/2024
# student: Janko Hrasko
# datum: 21.5.2024

zrejme ako študenta uvedieš svoje meno.