Priebežný test z Programovania (2) 2021/2022 - Variant B


  1. Z troch celočíselných operandov a dvoch operácií vieme vytvoriť niekoľko prefixových zápisov. Ak predpokladáme, že operandy sú v presnom poradí a nemôžu sa na rozdiel od operácií prehadzovať, potom z operandov [3, 5, 7] a operácií ['*', '+'] vieme vytvoriť, napríklad takéto výrazy '* 3 + 5 7' alebo '+ * 3 5 7', pričom každý môže mať inú hodnotu (prvý 36 a druhý 22). Napíš funkciu vsetky_prefixy(operandy, operacie), ktorá vráti množinu dvojíc všetkých výrazov aj s ich hodnotami, napríklad pre predchádzajúci príklad {('* 3 + 5 7', 36), ('+ * 3 5 7', 22), ...} - takýchto výrazov môže byť viac.

    def vsetky_prefixy(operandy, operacie):
        ...
    

  1. Funkcia pocitaj pomocou zásobníka nejako spracuje zadaný vstupný zoznam. Využije pritom rekurzívnu funkciu urob, ktorá ale môže niekedy spadnúť na pretečení rekurzie. Tvojou úlohou je opraviť funkciu urob tak, aby fungovala rovnako, ale bez rizika spadnutia kvôli rekurzii. Samozrejme, že funkciu pocitaj ani triedu Stack nemá zmysel meniť.

    class Stack:
        def __init__(self):
            self._zoz = []
        def push(self, hodn):
            self._zoz.append(hodn)
        def pop(self):
            return self._zoz.pop()
        def is_empty(self):
            return self._zoz == []
    
    def pocitaj(zoznam):
        stack = Stack()
        stack.push(7)
        for i in zoznam:
            urob(stack, i)
        vysl = stack.pop()
        while not stack.is_empty():
            vysl += stack.pop()
        return vysl
    
    def urob(stack, x):
        z = stack.pop()
        if stack.is_empty():
            stack.push(x)
        else:
            urob(stack, x)
        stack.push(1-z)
    

  1. V binárnom strome sa niektoré hodnoty môžu vyskytovať aj viackrát v rôznych vrholoch. Potrebujeme získať tie hodnoty, ktoré sa v strome vykytli nepárny počet krát, teda, ak sa nejaká hodnota vyskytla raz, alebo trikrát, alebo päťkrát, … tak nás bude zaujímať. Ale ak je nejaká hodnota v strome dvakrát, alebo štyrikrát, …, tak nás nezaujíma. Napíš metódu neparny_pocet(), ktorá vygeneruje (pomocou generátora) všetky hodnoty, ktoré sú v strome nepárny početkrát (každú len raz). Na binárny strom použi deklarácie:

    class BinarnyStrom:
        class Vrchol:
            def __init__(self, data):
                self.data, self.left, self.right = data, None, None
        def __init__(self):
            self.root = None
        def neparny_pocet(self):
            ...
    

  1. Niektoré triediace algoritmy „fungujú“ len pre nejaké konkrétne vstupy. Aj táto funkcia:

    def triedenie(zoznam):
        pom = list(range(len(zoznam)))
        s = 2 * len(zoznam) // 3
        pom = pom[s+1:] + pom[s:s+1] + pom[:s]
        zoznam[:] = [zoznam[i] for i in pom[::2]+pom[1::2]]
    

    Veľmi často neusporiada vstupný zoznam, ale ho ešte viac zamieša. Funkciu triedenie meniť nebudeš, ale navrhneš taký vstupný obsah pre zoznam, aby si po spracovaní dostal utriedený zoznam. Úlohu je teda tak preusporiadať pôvodný zoznam, aby si dostal:

    1. z1 = [2, 3, 4, 5, 6]

    2. z2 = [1.12, 2.13, 3.14, 4.15, 5.16, 6.17, 7.18, 8.19, 9.20, 10.21]

    3. z3 = ['ba', 'bb', 'dk', 'dt', 'kn', 'kz', 'lv', 'ma', 'ml', 'nz', 'po', 'pp', 'rs', 'rv', 'sc', 'to']


  1. Binárny vyhľadávací strom vieme veľmi jednoducho zostrojiť z nejakej danej postupnosti hodnôt postupným pridávaním hodnôt. Úlohou bude zostrojiť úplne rovnaký binárny vyhľadávací strom, vo vrcholoch ktorého budú hodnoty z nejakej úplne inej postupnosti. Riešiť to budeš tak, že v pôvodnom BVS (vytvorenej z počiatočnej postupnosti) prejdeš algoritmom inorder všetky vrcholy stromu a postupne nahradíš hodnoty vo vrcholoch prvkami druhej postupnosti. Musíš to ale urobiť tak, aby aj tento strom s novými hodnotami bol BVS. Napíš funkciu vyrob(postupnost1, postupnost2), ktorá vráti BVS s tvarom po vytvorení z postupnost1 ale s prvkami z postupnost2. Predpokladaj, že všetky prvky v každej z postupností sú rôzne a majú rovnaký počet. Funkcia vyrob:

    def vyrob(postupnost1, postupnost2):
        ...
    

    vráti inštanciu triedy:

    class BVS:
         class Vrchol:
             def __init__(self, data):
                 self.data, self.left, self.right = data, None, None
         def __init__(self):
             self.root = None
    

    Napríklad, volanie vyrob([5, 7, 3, 6, 2], ['a', 'o', 'r', 'g', 'd']) najprv vyrobí strom:

          5
        /   \
      3      7
     /      /
    2      6
    

    a potom ho zmení na:

          g
        /   \
      d      r
     /      /
    a      o
    

  1. So zoznamu hodnôt sme skonštruovali takýto binárny strom: prvý prvok išiel do koreňa, ďalšie 2 prvky zoznamu tvoria vrcholy v prvej úrovni stromu. Ďalšie 4 prvky tvoria vrcholy v druhej úrovni stromu. Zrejme v každej ďalšej úrovni je dvojnásobný počet vrcholov. V poslednej úrovni stromu môže byť aj menší počet prvkov a tie sú zrejme vo vrcholoch zľava. Napíš funkciu kontrola(zoznam), ktorá zistí, koľko vrcholov v takomto strome má svojho bezprostredného predka menšieho ako je on sám.

    def kontrola(zoznam):
        ...
    

  1. Napíš funkciu zoznam_urovni(permutacie), ktorá vráti zoznam (typ list) počtov vrcholov v jednotlivých úrovniach prefixového stromu, ktorý vznikol zo slov v množine permutacie. Táto množina obsahuje všetky permutácie nejakých rovnakých písmen (nemusíš to kontrolovať). Napríklad permutacie môže byť {'ab', 'ba'}, alebo {'vlk', 'vkl', 'lvk', 'lkv', 'kvl', 'klv'}. Potom volanie zoznam_urovni({'ab', 'ba'}) vráti zoznam [1, 2, 2] lebo prefixový strom má v 0. úrovni jeden vrchol, v 1. úrovni 2 vrcholy a v 2. úrovni tiež 2 vrcholy.

    def zoznam_urovni(permutacie):
        ...
    


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 2021/2022
# student: Janko Hrasko
# datum: 25.4.2024

zrejme ako študenta uvedieš svoje meno.