# Programování II pro matematiky ## Teoretické cvičení 07 **14. 4. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Poznámky k domácímu úkolu - Příklady - Řešení příkladů - Domácí úkol --- ## Opakování - Rekurze
Zdroj: https://thomaspark.co/2017/01/relevant-xkcd/ --- - Fibonačiho číslo ```python def fib(n): # vrať n-té číslo if n == 0: return 0 elif n == 1: return 1 else return fib(n-1) + fib(n-2) ```
--- - Binární strom ```python class Vrchol: """vrchol binárního stromu""" def __init__(self, x = None): self.info = x # uložená hodnota self.levy = None # levý syn self.pravy = None # pravý syn ```
--- ## Poznámky k Tabulka čokolády - Jeden algoritmus není dúkaz složitosti problému - Je potřeba provést $K \cdot L - 1$ zlomení - Libovolné zlomení čokolády zvýší počet kusů o jeden --- ## Příklady Najděte algoritmus a určete jeho časovou a prostorovou složitost v nejhorším případě. 1. Napište funkci pro výpočet faktorialu (pomocí rekurze a pomocí cyklu) 2. Na vstupu máme jednosměrný lineární spojový seznam. Chceme setřídit prvky spojového seznamu podle velikosti s použitím konstatní paměti (např. bez použití nového seznamu). 3. Na vstupu máme jednosměrný spojový seznam. Chceme obrátit pořadí prvků s použitím konstatní paměti (např. bez použití nového seznamu). **Na vstupu máme odkaz na kořen binárního stromu:** 1. Hledáme počet prvků v danném binárním stromě. 2. Hledáme maximální hloubku binárního stromu. 3. Hledáme prvek o hodnotě `x`. Chceme vrátit cestu z kořene k prvku `x`. 4. Chceme zjistit, zda je zadaný binární strom symetrický podle svislé osy procházející kořenem (jde nám pouze o tvar stromu, nikoliv o hodnoty uložené v jeho uzlech). --- ### Řešení (1) Napište funkci pro výpočet faktorialu (pomocí rekurze a pomocí cyklu). -- **Algoritmus:** (Vstup: Číslo `n`): ```python def factorial(n: int) -> int: if factorial > 1 return n * factorial(n-1) else return 1 def factroial(n: int) -> int: vysledek = 1 for i in range(1, n + 1): vysledek *= i return vysledek ``` -- Časová složitost $\mathcal{O}(n)$, paměťová složitost $\mathcal{O}(1)$ pro počítání přes cykly, ale při použití rekurze to může být i $\mathcal{O}(n)$ --- ### Řešení (2) Na vstupu máme lineární spojový seznam. Chceme setřídit prvky spojového seznamu podle velikosti s použitím konstatní paměti (např. bez použití nového seznamu). --- **Algoritmus:** (Vstup: První prvek jednosměrného spojového seznamu`prvni_prvek`): ```python def sort(prvni_prvek: Prvek) -> Prvek: zarazka = prvni_prvek todo = zaraska.dalsi while todo is not None: pozice = prvni_prvek while pozice is not zarazka: if pozice.hodnota <= todo.hodnota <= pozice.dalsi.hodnota: break pozice = pozice.dalsi # Přepojíme mensi = pozice vetsi = pozice.dalsi zarazka.dalsi = zarazka.dalsi.dalsi # vypojime prvek todo mensi.dalis = todo todo.dalsi = vetsi # Dalši prvek if mensi is zarazka zarazka = todo todo = zarazka.dalsi return prev ``` -- Časová složitost $\mathcal{O}(N^2)$ --- ### Řešení (3) Na vstupu máme jednosměrný lineární spojový seznam. Chceme obrátit pořadí prvků s použitím konstatní paměti (např. bez použití nového seznamu). -- **Algoritmus:** (Vstup: První prvek jednosměrného spojového seznamu `prvni_prvek`): ```python def reverse(prvni_prvek: Prvek) -> Prvek: prev = None current = prvni while(current is not None): next = current.dalsi current.dalsi = prev prev = current current = next return prev ```
--- ### Řešení (1) Hledáme počet prvků v danném binárním stromě. -- **Algoritmus:** (Vstup: Kořen binárního stromu `koren`): ```python pocet = 0 todo = collections.deque() # Procházíme do šířky todo.append(koren) while len(todo) > 0: prvek = todo.popleft() if prvek: pocet += 1 todo.append(prvek.levy) todo.append(prvek.pravy) return pocet ``` -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ (ve fronět bude celý strom) --- ### Řešení (2) Hledáme maximální hloubku binárního stromu. --- **Algoritmus:** (Vstup: Kořen binárního stromu `koren`): ```python def max_hloubka(vrchol) -> int: if vrchol is None: return 0 else return max(max_hloubka(vrchol.levy)+1, max_hloubka(vrchol.pravy)+1) return max_hloubka(koren) ``` -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(\text{hloubka stromu})$ --- ### Řešení (3) Hledáme prvek o hodnotě `x`. Chceme vrátit cestu z kořene k prvku `x`. -- Řešíme obdobně jako v příkladu jedna (máme zásobník) a dvě (jdeme do hloubky). Při nalezení hodnoty vrátíme aktuální zásobník. -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(\text{hloubka stromu})$ --- ### Řešení (4) Chceme zjistit, zda je zadaný binární strom symetrický podle svislé osy procházející kořenem (jde nám pouze o tvar stromu, nikoliv o hodnoty uložené v jeho uzlech). -- **Algoritmus:** (Vstup: Kořen binárního stromu `koren`): ```python je_stejny(levy, pravy): if levy is None and pravy is None: return True else: if je_stejny(levy.levy, pravy.pravy) and je_stejny(levy.pravy, pravy.levy): return True else: return False return je_stejny(koren.levy, koren.pravy) ``` -- Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(\text{hloubka stromu})$ --- ## Domácí úkol Mějme prázdnou minimalizační haldu H (minimum je v kořeni), postupně do ní vkládejme prvky $5, 4, 3, 2, 1$ a následně dokud není halda prázdná, tak odebírejme minimum. Názorně pomocí sekvence obrázků, názorných šipek a případných popisků ukažte jednotlivé kroky, které se vykonají. Například pokud se během odebírání minima nebo přidávání prvku provede více než jeden krok, nakreslete je všechny. Zapište, jak bude vypadat reprezetance haldy poocí pole po vložení posledního prvku (tj. při velikosti $5$). **Bonus**: Pokud neradi kreslíte, tak můžete kroky "vykreslovat" pomocí nějakého vlastního programu (pak ale není dovoleno používat pro samotnou haldu nějaké knihovny).