# --- # jupyter: # jupytext: # formats: ipynb,py:percent # text_representation: # extension: .py # format_name: percent # format_version: '1.3' # jupytext_version: 1.14.0 # kernelspec: # display_name: Python 3 (ipykernel) # language: python # name: python3 # --- # %% [markdown] toc=true slideshow={"slide_type": "notes"} #

Table of Contents

#
# %% [markdown] slideshow={"slide_type": "slide"} # # Fondamenti di Programmazione # # # **Andrea Sterbini** # # lezione 17 - 2 dicembre 2022 # %% RECAP [markdown] slideshow={"slide_type": "slide"} # # RECAP: # - Analisi OOP # - Ereditarietà # - Esempio di gerarchia di figure disegnate con Turtle # - Ricorsione e sue proprietà # - Esempi: fattoriale, fibonacci, GCD di Eulero # # # OGGI: altri esempi di ricorsione # %% Ricorsione init_cell=true slideshow={"slide_type": "notes"} # decoratore che stampa le chiamate ed uscite di una funzione ricorsiva from rtrace import trace # %%% Una chiamata ricorsiva può simulare un ciclo, anzi due slideshow={"slide_type": "slide"} # mi costruisco una lista di valori casuali import random lista = random.choices(range(-10000,10001), k=10) # %% [markdown] slideshow={"slide_type": "slide"} # # Somma ricorsiva di una lista (svolta in uscita) # - **caso base**: se la lista è vuota la somma è 0 # - **se la lista non è vuota**: sommiamo il primo elemento alla somma del resto della lista # %% slideshow={"slide_type": "slide"} @trace() def somma_ricorsiva(L): if L: # se caso ricorsivo primo, *resto = L return primo + somma_ricorsiva(resto) else: return 0 # altrimenti caso base somma = somma_ricorsiva.trace(lista) somma2 = sum(lista) somma, somma2 # %% slideshow={"slide_type": "slide"} @trace() def somma_ricorsiva_distruttiva(L): if L: # se caso ricorsivo ultimo = L.pop() return ultimo + somma_ricorsiva_distruttiva(L) else: return 0 # altrimenti caso base somma3 = somma_ricorsiva_distruttiva.trace(lista.copy()) # controlliamo che venga il risultato giusto somma2, somma3 # %% [markdown] slideshow={"slide_type": "slide"} # ## Somma iterativa di una lista # - accumuliamo la somma con un ciclo # %% slideshow={"slide_type": "fragment"} def somma_iter(L : list[int]) -> int: somma = 0 N = len(L) for i in range(N): somma += L[i] return somma somma_iter(lista), sum(lista) # %% [markdown] slideshow={"slide_type": "slide"} # ## Somma ricorsiva in avanti (simulando il ciclo) # - le variabili di stato, **somma**, **i** ed **N** # - diventano argomenti della funzione # - ad ogni step le aggiorniamo nella chiamata ricorsiva # %% slideshow={"slide_type": "fragment"} @trace() def _somma_ric_avanti(L : list[int], i : int, N : int, somma : int) -> int : if i==N: return somma else: return _somma_ric_avanti(L, i+1, N, somma + L[i]) # AGGIORNAMENTO def somma_ric_avanti(L): return _somma_ric_avanti(L, 0, len(L), 0) somma_ric_avanti(lista) # %% [markdown] slideshow={"slide_type": "slide"} # ## Stampa di una lista # - **in avanti** (prima del passo ricorsivo) # - **indietro** (dopo il passo ricorsivo) # - **avanti poi indietro** (prima e dopo) # # Analisi: # - la lista vuota non stampa nulla (caso base) # - una volta stampato il primo elemento va stampato il resto (passo ricorsivo) # %% slideshow={"slide_type": "slide"} # per scandire e stampare una lista in avanti def stampa_in_avanti(L): if L: primo, *resto = L print(primo, end=' ') stampa_in_avanti(resto) stampa_in_avanti(lista) print() print(lista) # %% slideshow={"slide_type": "slide"} # per scandire e stampare una lista a rovescio def stampa_dalla_fine(L): if L: primo, *resto = L stampa_dalla_fine(resto) print(primo, end=' ') stampa_dalla_fine(lista) print() print(lista) # TODO per scandire una lista sia in avanti che a rovescio # basta stampare sia prima della ricorsione che dopo # %%% esempio: mergesort (ordinamento per fusione) [markdown] slideshow={"slide_type": "slide"} # # MergeSort (ordinamento per fusione) # # ## osservazione: se due liste sono ordinate è facile e veloce fonderle in una nuova lista ordinata # # - per fondere due liste ordinate (**merge**) # - il primo elemento della soluzione è uno dei due primi delle due liste # - il resto della soluzione è la fusione del resto delle due liste # # - **convergenza**: almeno un elemento va a posto per ogni chiamata ricorsiva # - **caso base**: una delle due liste è vuota # %% slideshow={"slide_type": "slide"} @trace(True) def merge(L1 : list, L2 : list ) -> list: if not L1: # caso base: L1 vuota return L2 if not L2: # caso base: L2 vuota return L1 if L1[0] <= L2[0]: # caso ricorsivo con L1[0] minore return [L1[0]] + merge( L1[1:], L2 ) else: # caso ricorsivo con L2[0] minore return [L2[0]] + merge( L1, L2[1:] ) L1 = [1, 3, 5, 7, 9] L2 = [2, 4, 6, 8] merge.trace(L1, L2) # NOTA: per essere più efficienti possiamo preallocare la lista risultato e lavorare solo su indici # NOTA: oppure/inoltre lavorare in modo iterativo # %%% esempio: mergesort (ordinamento per fusione) [markdown] slideshow={"slide_type": "slide"} # ## E se ho una lista disordinata e la voglio ordinare? (MergeSort) # - la posso spezzare in due liste disordinate (**riduzione**) # - le posso ordinare separatamente (chiamata ricorsiva sui **sottoproblemi**) # - le posso fondere rapidamente (**costruzione della soluzione**) con **merge** # # # - **convergenza**: a forza di spezzare le liste in 2 si arriverà a liste di 0,1 elementi # - **caso base**: liste di 1 o 0 elementi, sono già ordinate # %% slideshow={"slide_type": "slide"} ## per spezzare in 2 posso usare una slice L = [1, 5, 2, 9, 4, 6, 1, 90 ] mid = len(L)//2 L1 = L[:mid] L2 = L[mid:] L1, L2 # %%% esempio: alberi binari e stampa in/pre/post ordine slideshow={"slide_type": "slide"} ## oppure una funzione ricorsiva che torna due liste di elementi alternati @trace() def splitta(L): if not L: return [], [] else: primo, *resto = L # prendo il primo elemento ed il resto L1, L2 = splitta(resto) L2.append(primo) return L2, L1 # aggiungo il valore su una lista e le scambio splitta.trace(L) # %%% esempio: alberi n-inari e directory slideshow={"slide_type": "slide"} ## Finalmente realizziamo mergeSort @trace() def merge_sort(L : list) -> list: if len(L) < 2: # [x] e [] sono già ordinate return L else: L1, L2 = splitta(L) # 2 sottoliste disordinate sorted1 = merge_sort(L1) # ordino la prima sorted2 = merge_sort(L2) # ordino la seconda return merge(sorted1, sorted2) # le fondo # TODO: per essere un po' più efficienti si può lavorare con indici in liste che non vengono modificate merge_sort.trace(L) # %% [markdown] slideshow={"slide_type": "slide"} # ![](mergesort.png) # %% [markdown] slideshow={"slide_type": "slide"} # # Alberi binari # # - si parte da un nodo "radice" che non ha "padri" # - ogni nodo piò avere fino a 2 "figli" # - i nodi senza figli sono le "foglie" # - ogni nodo ha un solo "padre" # %% slideshow={"slide_type": "notes"} import graphviz T = graphviz.Digraph() T.body.append(''' radice -> "nodo\n0" -> "nodo\n00" -> "foglia\n000" radice -> "nodo\n1" -> "nodo\n10" -> "foglia\n100" "nodo\n0" -> "nodo\n01" -> "foglia\n010" "nodo\n1" -> "nodo\n11" -> "foglia\n110" "nodo\n00" -> "foglia\n001" "nodo\n10" -> "foglia\n101" "nodo\n01" -> "foglia\n011" "nodo\n11" -> "foglia\n111" ''') # %% slideshow={"slide_type": "slide"} T # %% slideshow={"slide_type": "slide"} # usiamo gli oggetti per rappresentare i nodi dell'albero class NodoBinario: def __init__(self, V : int, left : 'NodoBinario' = None, right : 'NodoBinario' = None): self._value = V self._sx = left self._dx = right def __repr__(self): return f'NodoBinario({self._value})' n11 = NodoBinario(11) n10 = NodoBinario(10) n1 = NodoBinario(1, right=n11) n0 = NodoBinario(0, left= n10) r = NodoBinario(100, n0, n1) r # %% [markdown] slideshow={"slide_type": "slide"} # ## Stampa di un albero # ### con visita in PREordine (la radice prima dei sottoalberi) # %% slideshow={"slide_type": "fragment"} # radice è un nodo oppure None # per stampare indentato passo un argomento 'livello' # e lo incremento ogni volta che scendo in un sottoalbero def stampa_PRE(radice : NodoBinario, livello : int =0) -> None : print('|--'*livello, radice) if radice: stampa_PRE(radice._sx, livello+1) stampa_PRE(radice._dx, livello+1) stampa_PRE(r) # %% [markdown] slideshow={"slide_type": "slide"} # ### con visita in POSTordine (la radice DOPO i sottoalberi) # %% slideshow={"slide_type": "fragment"} def stampa_POST(radice, livello=0): if radice: stampa_POST(radice._sx, livello+1) stampa_POST(radice._dx, livello+1) print('|--'*livello, radice) stampa_POST(r) # %% [markdown] slideshow={"slide_type": "slide"} # ### con visita INordine (la radice TRA i sottoalberi) # %% slideshow={"slide_type": "fragment"} def stampa_IN(radice, livello=0): if radice: stampa_IN(radice._sx, livello+1) print('|--'*livello, radice) if radice: stampa_IN(radice._dx, livello+1) stampa_IN(r) # %% [markdown] slideshow={"slide_type": "slide"} # ## Calcolo della profondità/altezza di un albero (in uscita) # - Una foglia ha altezza 1 (caso base) # - un nodo ha altezza 1 + la massima altezza dei sottoalberi (passo ricorsivo + composizione) # # Oppure: # - **None** ha altezza 0 # %% [markdown] # ![](altezza.png) # %% slideshow={"slide_type": "slide"} @trace() def altezza(radice): if radice is None: return 0 H_sx = altezza(radice._sx) H_dx = altezza(radice._dx) return 1 + max(H_sx, H_dx) altezza.trace(r) stampa_PRE(r) # %% [markdown] slideshow={"slide_type": "slide"} # ## Calcolo della profondità in "andata" # # - si fornisce come argomento la profondità massima incontrata finora # - la si aggiorna visitando tutto l'albero # - (ogni volta che si scende in un sottoalbero si somma 1 alla profondità) # - se il nodo è **None** si torna la profondità corrente # - altrimenti il nodo esiste e la profondità è il massimo delle profondità dei due sottoalberi # %% slideshow={"slide_type": "slide"} @trace() def altezza2(radice, profondità=0): if radice is None: return profondità P_sx = altezza2(radice._sx, profondità+1) P_dx = altezza2(radice._dx, profondità+1) return max(P_sx, P_dx) altezza2.trace(r) # %% [markdown] slideshow={"slide_type": "slide"} # # Alberi N-ari (con numero indefinito di figli) # - **value**: valore del nodo # - **sons**: elenco di figli # %% slideshow={"slide_type": "notes"} G3 = graphviz.Digraph() G3.body.append(''' 2 [color=green] 19 [color=red] 14 -> 11 14 -> 12 14 -> 2 11 -> 19 11 -> 13 11 -> 3 11 -> 4 ''') # %% slideshow={"slide_type": "slide"} G3 # %% slideshow={"slide_type": "fragment"} # utility che mi permette di aggiungere con %%add_to dei metodi definiti in celle separate alla classe import jdc class NodoNario : def __init__(self, V : int, sons : list['NodoNario'] = None): # ATTENTI AL DEFAULT!!! self._value = V if sons is None: self._sons = [] else: self._sons = sons def __repr__(self): return f"NodoNario({self._value}, {len(self._sons)} sons)" # %% [markdown] slideshow={"slide_type": "slide"} # ### stavolta scriviamo le funzioni come metodi della classe NodoNario # %% [markdown] slideshow={"slide_type": "fragment"} # ### altezza del nodo nell'albero (quanti livelli ha sotto) # - esploro l'albero ricorsivamente # - l'altezza di un nodo è 1 + max altezza dei sottoalberi figli # - l'altezza di una foglia è 0 # %% slideshow={"slide_type": "fragment"} # %%add_to NodoNario ## metodo per calcolare l'altezza del nodo def altezza(self): # se non ci sono figli si torna 0 return max( [son.altezza()+1 for son in self._sons], default=1 ) # %% slideshow={"slide_type": "fragment"} n19 = NodoNario(19) n2 = NodoNario(2) n3 = NodoNario(3) n4 = NodoNario(4) n13 = NodoNario(13) n12 = NodoNario(12) n11 = NodoNario(11, [n3, n4, n13, n19]) n14 = NodoNario(14, [n2, n11, n12]) # %% slideshow={"slide_type": "fragment"} n14.altezza() # %% [markdown] slideshow={"slide_type": "slide"} # ### stampa (in preordine) di un nodo e dei figli # - aggiungo un argomento livello che incremento ogni volta che scendo # - prima stampo il nodo indentato del livello corrente # - poi stampo ricorsivamente i sottoalberi con livello+1 # %% slideshow={"slide_type": "fragment"} # %%add_to NodoNario # metodo per stampare l'albero def stampa(self, livello=0): indent = '|--'*livello print(indent, self) for son in self._sons: son.stampa(livello+1) # %% slideshow={"slide_type": "fragment"} n14.stampa() # %% [markdown] slideshow={"slide_type": "slide"} # ## cerchiamo il massimo valore nell'albero # # - esploriamo ricorsivamente # - il valore massimo di un sottoalbero è il massimo tra il valore della radice ed i valori dei sottoalberi # %% slideshow={"slide_type": "fragment"} # %%add_to NodoNario # versione in stile non-funzionale def massimo(self): M = self._value for s in self._sons: m = s.massimo() if M < m: M = m return M # versione in stile funzionale def massimo2(self): return max([s.massimo2() for s in self._sons] + [self._value]) # %% slideshow={"slide_type": "fragment"} n14.massimo2() # %% slideshow={"slide_type": "slide"} # %%add_to NodoNario # versione che porta il massimo come argomento # da aggiornare mano a mano che si esplora l'albero def massimo3(self, max_corrente=None): if max_corrente is None: max_corrente = self._value else: max_corrente = max(max_corrente, self._value) for son in self._sons: max_corrente = son.massimo3(max_corrente) return max_corrente # ATTENZIONE: DOVETE TORNARE IL NUOVO VALORE!!! # perchè max_corrente è una VARIABILE LOCALE!!! # e tornandola comunicate all'esterno il risultato # %% n14.massimo3() # %% slideshow={"slide_type": "fragment"} n14.massimo(), n14.massimo2(), n14.massimo3() # %% [markdown] slideshow={"slide_type": "slide"} # ## cerchiamo il nodo col massimo valore # - esploriamo ricorsivamente # - il nodo massimo di un sottoalbero è nodo che contiene il massimo tra il valore della radice ed i valori dei sottoalberi # %% slideshow={"slide_type": "fragment"} # %%add_to NodoNario def max_node(self): M = [self] + [s.max_node() for s in self._sons] #print(M) return max(M, key=lambda x: x._value) def min_node(self): M = [self] + [s.min_node() for s in self._sons] #print(M) return min(M, key=lambda x: x._value) # %% slideshow={"slide_type": "fragment"} n14.max_node(), n14.min_node() # %% [markdown] slideshow={"slide_type": "slide"} # ## cerchiamo la differenza in altezza tra nodo con valore massimo e nodo con valore minimo # %% slideshow={"slide_type": "fragment"} # %%add_to NodoNario def depth_of_max(self,livello=0): M = [(self._value, livello)] + [ son.depth_of_max(livello+1) for son in self._sons] return max(M, key=lambda x: x[0]) def depth_of_max2(self,livello=0): M = self._value P = livello for son in self._sons: m,p = son.depth_of_max2(livello+1) if m > M: M = m P = p return M, P def depth_of_min(self,livello=0): M = [(self._value, livello)] + [ son.depth_of_min(livello+1) for son in self._sons] return min(M, key=lambda x: x[0]) # %% slideshow={"slide_type": "fragment"} n14.depth_of_max(), n14.depth_of_min()