Quinta lezione: Riassunto e qualche proposta di esercizio riassuntivo In seguito vi propongo degli esercizi da risolvere. Potete trovare delle soluzioni (che pero' mettero' online solo fra qualche giorno) nel notebook 'soluzioni.ipynb' e negli scripts (da essere eseguiti da terminale, #python nomedelloscript.py): 'EX6finitedifference.py', '' ''. Vi ricordo che per aprire il notebook potete fare, da terminale: # jupyter notebook soluzioni.ipynb Prima del testo degli esercizi, vi scrivo qualche dritta, piuttosto fondamentale, sugli errori comuni e sui dettagli ai quali fare attenzione. ############################################ (1) Non confondere variabili di tipo stringa con il contenuto della stringa. Molte funzioni di Python ricevono come argomento una variabile di tipo stringa, per esempio con il nome del file da trattare (da aprire, da leggere, ecc), ma NON il contenuto della stringa. Per esempio, la funzione del modulo 'os.path': >os.path.isdir(yourfavoritepath) richiede come argomento una variabile di tipo stringa, non il contenuto della stringa. Se si vuole verificare se il file 'testo.txt' e' una cartella, evitate di fare >os.path.isdir(testo.txt) fate bensi' >os.path.isdir('testo.txt') oppure > stringa='testo.txt' >os.path.isdir(stringa) ############################################ (2) Nell'implementazione di funzioni ricorsive, le funzioni devono sempre avere una condizione sotto la quale non chiamano se stesse, e anche in quel caso hanno da ritornare le variabili adatte. Per esempio, la seguente implementazione della funzione merge-sort: >def mergesort(lista): > L =len(lista) > if L==1: > return > l1=lista[:L/2] > l2=lista[L/2:] > > mergesort(l1) > mergesort(l2) > > return merge(l1,l2) e' sbagliata per due motivi. Intanto, perche', quando la lunghezza della lista in input e' 1, la funzione non ritorna niente. Ma il risultato della chiamata a mergesort() quando la lista di input ha lunghezza 1 viene ripreso, per via della ricorsivita', dalla chiamata di mergesort() quando la lista ha lunghezza due, e cosi' ricorsivamente. La correzione necessaria e', dunque: > if L==1: > return lista ##################################################### (3) Un errore comune e' quello che consiste nell'eseguire funzioni che non hanno nessun effetto all'interno delle funzioni che le chiamano. Per esempio, l'implementazione di mergesort() qua sopra e' sbagliata anche perche' la chiamata a mergesort non ha nessun effetto. La chiamata corretta e': > l1=mergesort(l1) > l2=mergesort(l2) cosi' si sostituisce la lista l1 per il risultato di mergesort(l1). Altrimenti le liste l1,l2 restano cosi' com'erano, non vengono modificate. V. anche il seguente punto. ##################################################### (4) Un punto sul quale vi consiglio di stare attenti e' il seguente. In Python, come in C, gli argomenti di funzioni di tipo lista (in C, di tipo array) vengono passati per referenza, ilche' vuol dire che le variabili di tipo lista che si passano come argomento alle funzioni vengono modificate: >def prova(lista): lista[2]=20 >lista=range(20) >prova(lista) la variabile 'lista' e' stata modificata. In Python di solito uno non utilizza questo meccanismo per modificare le liste che vuole modificare. Suggerisco di fare piuttosto come in questo esempio in cui una funzione scambia i terzi elementi di due liste che riceve come argomento: >def prova(lista1,lista2): > lista1n=lista1[:] > lista2n=lista2[:] > lista1n[2] , lista2n[2] = lista2n[2] , lista1n[2] > return lista1n,lista2n poi, per modificare due liste: >l1=[1,2,3] >l2=[3,2,1] >l1,l2=prova(l1,l2) Cioe' le funzioni restituiscono con 'return' il risultato, e non modificano le liste originali. Questo e' particolarmente importante nelle implementazioni ricorsive. Avete un esempio utile di un possibile errore legato a questo meccanismo nell'implementazione della funzione Scegli() (c.f. EX6, qua sotto) che trovere nel notebook con le soluzioni, e la cui soluzione in pseudo-codice potete trovare qua sotto (il problema si presenta quando c'e' scritto "ATTENZIONE"). ##################################################### (5) Forse l'errore piu' comune e' quello che consiste nel fornire come argomento alle funzioni che processano un file (il cui percorso viene dato come argomento), il nome del file, non del path completo corrispondente al file. Per esempio, mi faccio dare il nome della cartella, nella variabile chiama nomecartella, e apro ogni file presente in tale cartella: >for miofile in os.listdir(cartella): > myfile=open(miofile,'r') in generale non funzionera', dato che il file il cui nome e' dato dalla variabile miofile non si trova in generale nella presente cartella e. Uno deve fornire il percorso completo del file: >for miofile in os.listdir(cartella): > myfile=open(cartella+miofile,'r') ##################################################### ESERCIZI PROPOSTI ##################################################### EX1) EX6 della lezione lesson2. Cioe': Write a Python function that opens a file and creates a second file in which it is written, in one column, the finite difference between the elements of the n-th column of the original file (i.e., the i-th row of the output column should be the difference a(i+1)-a(i), being a(i) the i-th row of the n-th column of the original file). The function should take n and the filename as arguments. You can test your program with the test file ‘BinderL128.dat’. La soluzione nel notebook 'soluzioni.ipynb' EX2) Scrivere uno script di Python (non una funzione) che riceve per riga di comando il percorso corrispondente a una cartella, e stampa la lista dei file (non delle cartelle) contenute nella cartella specificata per riga di comando. La soluzione nello script 'EX2writefilenames.py' EX3) Scrivere uno script di Python (non una funzione) che riceve per riga di comando il percorso corrispondente a una cartella e, per ogni file di estensione '.txt' presente nella cartella corrispondente al percorso, fa la seguente operazione: se il nome generico del file e' 'file.txt', crea un nuovo file chiamato 'file_alt.txt' che contiene le due ultime righe del file 'file.txt'. La soluzione nello script 'EX3write2lastlines.py' EX4) Scrivere una funzione che ordina una lista. La soluzione nel notebook 'soluzioni.ipynb' EX5) Implementare una funzione ricorsiva dell'algoritmo merge-sort. Stimare la complessita' (< oppure > ~L**2) dell'algoritmo merge-sort e dell'algoritmo implementato in EX4 su liste casualmente disordinate, mediante lo script 'timeTestSortFunctions.ipynb'. La soluzione nel notebook 'soluzioni.ipynb' EX6) Implementare ricorsivamente una funzione che scrive tutte le combinazioni "M scegli n". Cioe' la funzione >scegli(M,n) deve ritornare una lista di liste in numero pari al numero combinatorio M su n, ciascuna di queste liste e' una lista di lunghezza n contenente n elementi diversi tratti dall'insieme di numeri naturali minori o uguali a M. Per esempio, scegli(5,3) deve ritornare la lista di liste: [ [1,2,3] [1,2,4] [1,2,5] [1,3,4] [1,3,5] [1,4,5] [2,3,4] [2,3,5] [2,4,5] [3,4,5] ] Vi propongo una possibile soluzione: la funzione ricorsiva potrebbe ricevere tre argomenti, >def scegli(M,n,listaausiliare,listadiliste): > > for j in range M, M-1 , ..., 1: > > l'n-esimo elemento della lista ausiliare va messo a j > > #cosi' esaurisco le possibilita' di quella casella della lista > #per ciascuna di quelle possibilita', devo esaurire le possibilita' della casella precedente > #e per ciascuna di quelle, quelle della casella precedente, e cos' via. cioe': > > se n > 1: #cioe' se ancora non ho finito > #risolvo il problema per quello che resta A SINISTRA di n: > #partendo da un numero minore, poiche' gli elementi della lista devono essere ordinati > #(per evitare ripetizioni di combinazioni) > > listaausiliare, listadiliste = scegli(j-1 ,n-1,listaausiliare,listadiliste) > > altrimenti: > aggiungo (ATTENZIONE: UNA COPIA DI !!) listaausiliare a listadiliste > > #quanto ha finito con l'nesimo elemento, la funzione restituisce le liste: > # me le porto sempre appresso nelle recursioni > return listaausiliare, listadiliste La funzione ricorsiva va poi chiamata con una lista vuota come "listadiliste" e con una qualsiasi lista di taglia n come "listaausiliare", cosi': >lista=range(n) # per esempio: basta avere una lista di lunghezza n >scegli(M,n,lista,[]) La soluzione completa in 'soluzioni.ipynb'