#
# Ad ogni mese il numero di coppie si ottiene sommando:
# - i nuovi coniglietti che nascono dalle coppie adulte (quelle di 2 mesi prima)
# - e le coppie correnti (1 mese prima)
# %% [markdown] slideshow={"slide_type": "slide"}
# ### Soluzione iterativa (simulando le coppie)
# - F(0)=0
# - F(1)=1
# - ...
# - F(N)=F(N-1)+F(N-2)
# %% [markdown] slideshow={"slide_type": "slide"}
# ### Soluzione ricorsiva
# Se osserviamo il problema dal punto di vista dell'anno N:
# - **caso base**: 0 coppia se N==0
# - **caso base**: 1 coppia se N==1 (erano troppo giovani)
# - **riduzione del problema**: Per calcolare F(N) ci servono F(N-1) ed F(N-2)
# - **composizione della soluzione**: F(N) = F(N-1) + F(N-2)
# %%% Le 4 proprietà di un algoritmo ricorsivo slideshow={"slide_type": "slide"}
@trace
def fibonacci(N : int) -> int :
if N < 2:
return 1
else:
return fibonacci(N-1) + fibonacci(N-2)
fibonacci.trace(4)
# %%% Strategia di analisi [markdown] slideshow={"slide_type": "slide"}
# # METODO: le 4 proprietà vi guidano per affrontare un problema ricorsivo sconosciuto:
# - trovate il **caso base**
# - confrontate **problemi** di dimensioni diverse per capire come fare la "riduzione"
# - confrontate **soluzioni** di dimensioni diverse per capire come calcolare la "soluzione"
# - **verificate che** applicando più volte il passo di riduzione **si arrivi sempre ad un caso base** (convergenza)
# - altrimenti aumentate i casi base
# %% [markdown] slideshow={"slide_type": "slide"}
# ## E' sempre possibile simulare un ciclo con una ricorsione
# ## E' sempre possibile simulare una ricorsione con uno o più cicli (e se necessario una pila/stack)
# - Iacopini Bohm
#
# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# 0 1 1 2 3 5 8 13 21
def fibonacci_iter(N : int) -> int :
coppie = [0, 1]
for i in range(N):
coppie.append(coppie[-1] + coppie[-2])
print(coppie)
return coppie[-1]
print(fibonacci_iter(7))
# MA ATTENZIONE!!!
# E' sufficiente ricordasi SOLO dei DUE mesi precedenti!
# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# Mi ricordo SOLO dei DUE mesi precedenti
def fibonacci_iter2(N : int) -> int :
corrente, precedente = 1, 0
for i in range(N):
corrente, precedente = corrente+precedente, corrente
return corrente
print(fibonacci_iter2(70))
# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# simuliamo l'allevamento anno per anno da 1 ad N con la ricorsione
# - convertiamo le variabili di stato del ciclo in argomenti della funzione
@trace
def _fibonacci_ric_efficiente(N : int, i : int,
corrente : int,
precedente : int):
if i == N:
return corrente
else:
corrente, precedente = corrente+precedente, corrente
return _fibonacci_ric_efficiente(N, i+1, corrente, precedente)
# definiamo una funzione di appoggio che inizializza le variabili di stato
def fibonacci_ric_efficiente(N : int):
return _fibonacci_ric_efficiente(N, 0, 1, 0)
# oppure potevamo dare dei valori di default appropriati alle "variabili di stato"
_fibonacci_ric_efficiente.trace(7, 0, 1, 0)
# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# proviamo invece a lavorare in uscita dalla ricorsione
# - ciascuna chiamata ritorna la coppia *corrente, precedente*
# ovvero calcoliamo F(N) -> corrente, precedente
# - nel caso base la coppia è 1, 0
# - da corrente, precedente del mese prima (N-1) posso calcolare quelli di N
@trace
def fibonacci_efficiente(N : int ) -> tuple[int,int] :
if N == 0:
return 1, 0 # all'inizio ci sono 0 ed 1 coppia
else:
# ottengo i due valori del mese precedente (F(N-1) e F(N-2))
corrente, precedente = fibonacci_efficiente(N-1)
# calcolo i due valori per questo mese (F(N) e F(N-1))
return corrente+precedente, corrente
print(fibonacci_efficiente(5)[0])
fibonacci_efficiente.trace(5)
# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ## Altro esempio: Massimo Comun Divisore di x, y interi positivi
# Ovvero dobbiamo trovare quel'intero **$M$** tale che:
# - **$x = M*k$**
# - **$y = M*j$**
# - con **$k,j>=1$** (e senza fattori comuni)
# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ### Quali sono le proprieta di **$x$** ed **$y$**?
# - se **x==y** allora **k==j==1** e **M=x** (ecco un buon **caso base**!)
# - altrimenti proviamo a sottrarre il minore dal maggiore
# - **z = x-y = M*(k-j)** quindi **z** e **y** hanno lo stesso **MCD**, # e inoltre z è più piccolo di x (ecco la nostra **riduzione**!) # - ad ogni passo si riduce la somma k+j di almeno j (il più piccolo) # - sottraendo un numero più piccolo non si può andare nei negativi # - a forza di sottrarre arriveremo per forza a j=k=1 ovvero al caso base (ed ecco la **convergenza**) # - una volta trovato **M** abbiamo la soluzione di ciascun caso __più grande__ (**ricomposizione**) # # Ottimizzazione: invece di sottrarre y da x calcoliamone il resto -> algoritmo di **Euclide** # %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"} # Sfruttiamo la definizione ricorsiva del problema # per dare una implementazione ricorsiva @trace def GCD(x : int, y : int) -> int : # FIXME: controllare che siano interi E positivi if x == y: return x else: if x>y: return GCD(x-y, y) else: return GCD(y-x, x) GCD.trace(108, 64) # %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"} ## Non è difficile farne una versione iterativa def GCD_iter(x : int, y : int) -> int : while x != y: if x > y: x -= y else: y -= x return x print(GCD_iter(75,45)) # %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"} # ## Esempio: Check se una stringa/lista è palindroma
(si legge uguale in senso inverso) # # ### soluzioni iterative # - rovescio e confronto # - scandisco gli indici degli elementi agli estremi e li confronto # %% run_control={"marked": false} from typing import Sequence ## Rovescio e confronto def palindromaP_iter1(sequenza : Sequence): rovesciata = sequenza[::-1] return rovesciata == sequenza # leggermente inefficiente, costruisco una nuova sequenza e confronto 2N elementi # (potrei confrontarne solo N) palindromaP_iter1('amoRoma') # %% slideshow={"slide_type": "slide"} ## Versione iterativa def palindromaP_iter2(sequenza : Sequence ) -> bool : for i in range(len(sequenza)//2): print('comparing', sequenza[i], sequenza[-i-1], sequenza[i] == sequenza[-i-1]) if sequenza[i] != sequenza[-i-1]: return False return True palindromaP_iter2('amoRoma') #palindromaP_iter([1, 2, 3, 4, 5, 4, 3, 2, 1]) # %% def palindroma_iter2(sequenza): inizio = 0 fine = len(sequenza)-1 while inizio < fine: print('comparing', sequenza[inizio], sequenza[fine], sequenza[inizio] == sequenza[fine]) if sequenza[inizio] != sequenza[fine]: return False inizio += 1 fine -= 1 return True palindroma_iter2([1, 2, 3, 4, 5, 4, 3, 2, 1]) # %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"} # ### soluzione ricorsiva # - **casi base**: ogni sequenza di lunghezza 0 o 1 è palindroma # - se è lunga 2 o più elementi il primo e l'ultimo devono essere uguali # - se non lo sono NON è palindroma (altro **caso base**) # - se lo sono deve essere palindromo anche il resto, tolto primo ed ultimo carattere # - (togliere i 2 caratteri = **riduzione**) # - a forza di togliere 2 caratteri si arrivarà sempre a 1 o 0 (**convergenza**) # - la stringa è palindroma se sono uguali primo e ultimo AND la sottostringa è palindroma
# (**costruzione della soluzione dalla sottosoluzione** + calcolo locale) # %% slideshow={"slide_type": "slide"} @trace def palindromaP(sequenza : Sequence ) -> bool : "predicato che verifica se una sequenza è palindroma" if len(sequenza) < 2: return True if sequenza[0] != sequenza[-1]: return False else: return palindromaP(sequenza[1:-1]) palindromaP.trace('amoRoma') # un po' inefficiente perchè crea tante sottosequenze # %% slideshow={"slide_type": "slide"} # versione che usa gli indici inizio e fine @trace def _palindromaP2(sequenza : Sequence, inizio : int, fine : int ) -> bool : if inizio >= fine: return True if sequenza[inizio] != sequenza[fine]: return False return _palindromaP2(sequenza, inizio+1, fine-1) def palindromaP2(sequenza): return palindromaP2(sequenza, 0, len(sequenza)-1) _palindromaP2.trace('amoRoma', 0, 6) # %% [markdown] slideshow={"slide_type": "slide"} # ## Esploriamo un albero di directory:
cerchiamo tutti i file .txt e la loro dimensione # # - una directory contiene files (caso base) e sottodirectory (caso ricorsivo) # - ogni volta che esaminiamo una sottodirectory abbiamo un problema simile a quello iniziale, e più piccolo # - a forza di scendere arriveremo in una sottodirectory che contiene solo file (convergenza) # - i file trovati nelle sottodirectory vanno raccolti assieme a quelli della dir iniziale (composizione) # # Per esaminare directory e files si usa la libreria **`os`** # %% slideshow={"slide_type": "subslide"} import os @trace def cerca_file_sizes(directory : str) -> dict[str, int] : "cerco tutti i file '.txt' e ne ritorno le dimensioni" risultato = {} for nome in os.listdir(directory): # ignoro file e dir che iniziano per '.' oppure '_' if nome[0] in '_.': continue fullname = directory + '/' + nome # se sono nel caso ricorsivo if os.path.isdir(fullname): trovati = cerca_file_sizes(fullname) risultato.update(trovati) # altrimenti se è un file che finisce con 'txt' elif nome.endswith('.txt'): size = os.path.getsize(fullname) risultato[fullname] = size return risultato cerca_file_sizes.trace('../lezione11') # %% ## soluzione ricorsiva che raccoglie i file ## in un dizionario fornito come argomento def cerca_file_sizes2(directory : str, dizionario : dict[str, int]) -> None: "cerco tutti i file '.txt' e ne ritorno le dimensioni" for nome in os.listdir(directory): # ignoro file e dir che iniziano per '.' oppure '_' if nome[0] in '_.': continue fullname = directory + '/' + nome # se sono nel caso ricorsivo if os.path.isdir(fullname): cerca_file_sizes2(fullname, dizionario) # altrimenti se è un file che finisce con 'txt' elif nome.endswith('.txt'): size = os.path.getsize(fullname) dizionario[fullname] = size D = {} cerca_file_sizes2('..', D) D