Laboratorio di Python - DISIzuppirol/lez5.pdf · Correzione esercizi Fase di Progettazione -...

Correzione eserciziFase di Progettazione - Algoritmi

EserciziEsercizi per casa

Laboratorio di PythonAlgoritmo, Esercizi sulle liste

Sara Zuppiroli

Università di Bologna

3 e 5 aprile 2013

Sara Zuppiroli Laboratorio di Python



Sommario

1 Correzione esercizi

2 Fase di Progettazione - Algoritmi

3 Esercizi

4 Esercizi per casa




Correzione

scrivere e documentare un programma con un menu dove:la funz prende in input una tupla e restituisce il primo valorepresente nella lista che massimizzi la distanza dal valorem=(max+min)/2la funz prende in input due tuple e restituisce la somma delle duetuple solo se le tuple hanno lunghezza ugualela funz prende in input tre punti A(x1,y1) B(x2,y2) C(x3,y3) erestituisce True se questi punti possono formare un triangolo.False altrimentila funz prende in input due liste e restituisce la lista dei valoriappartenenti ad entrambe le tupleper uscire dal programma




Correzione

def menu_2():print("seleziona 1 ...")print("seleziona 2 ...")print("seleziona 3 ...")print("seleziona 4 ...")print("seleziona 5 ...") #ricevo la scelta#x=int(input("Digita la tua scelta \t"))while 1<=x<=5:

if x==1:#caso sel:1#A=tuple(input("inserisci la tupla"))#ricevo i dati#def sel1_(B):

for i in range(len(B)):if B[i] is max(B) or B[i] is min(B):

#il valore che massimizza e' per forza o il minimo o il massimo#print(B[i])return B[i]

sel1_(A)x=int(input("Digita la tua scelta \t"))

La struttura di questo codice come vi sembra?Cosa accade con (6,10)?




Correzione

Esercizio

def triangle(x,y,z):l1=lenght(x,y)l2=lenght(y,z)l3=lenght(x,z)if l1<l2+l3:

return Trueelse:

return False

Cosa manca?




Fase di progettazione

La fase di progettazione, consistente nel determinare il metodo per lasoluzione problema.Le sequenza di operazioni finite che descrivono il procedimento disoluzione a un determinato problema é detto algoritmo.L’algoritmo non é legato al linguaggio di programmazione che siutilizzerá per implementare la soluzione.




Algoritmo Deterministico

Un algoritmo é definito da una lista finita di istruzioni che specificanoil procedimento esatto da eseguire per ottenere un determinatorisultato.In ogni momento di esecuzione dell’algoritmo si sa esattamentequale sia l’operazione successiva da eseguire e quale sia lo stato delsistema.




Esempi di algoritmo

Problema: Date due matrici calcolarne il prodotto. Algoritmorisolutivo:

1 Memorizzare le matrici An,k , Bk,m

2 Verificare che il numero di colonne della prima, sia uguale alnumero di righe della seconda:

Se vero Allora calcolare ogni elemento mr,c della matrice Mn,m come:mr,c=

∑ki=0 ar,i ∗ bi,c , calcolato per ogni 1 ≤ r ≤ n e per ogni

1 ≤ c ≤ m.Se Falso Rilevo un errore e lo memorizzo come risultato

3 Restituisco il risultato




Passare dall’algoritmo alla sua implementazione

Per fare questo passaggio bisogna prendere in considerazionealcune informazioni:

La rappresentazione che si sta utilizzando per salvare i dati.Come rappresento le matrici?I comandi e le funzioni che ho a mia disposizione per larisoluzione del mio problema.Riconoscere e scomporre in sotto-problemi piú facili. (es. [Severo] non é altro che il prodotto scalare tra due vettori eseguitom*n volte)




La nostra rappresentazione

La matrice An,m é una sequenza di sequenze cosí rappresentata:Ri = (ai,1, · · · ,ai,m)La matrice risulta essere quindi: An,m = R1, · · · ,Rn




Quindi moltiplicare le due matrici significa

Abbiamo la matrice An,m rappresentata come: ARi = (ai,1, · · · ,ai,m)An,m = AR1 , · · · ,ARne la matrice Bm,r rappresentata come:BRi = (bi,1, · · · ,bi,r )quindi:Bm,r = BR1 , · · · ,BRm

Eseguire il prodotto di AxB significa costruire la seguente matriceCn,r :Ogni riga della nostra matrice avrá la seguente struttura dove B[r] é lanostra colonna:CRk = ARk B[1], · · · ,ARk B[r ]e quindiCn,r = CR1 , · · ·CRn




Come calcolare tutte le CRk ?

Per calcolare CRk ad esempio dobbiamo eseguire queste operazioni:1 per tutti gli i compresi tra 0 e le r − 1 colonne di B:2 Si inserisce nella sequenza al posto i − esimo il valore di CRk [i]

che é dato dal risultato del prodotto scalare tra ARk B[i]Dobbiamo poi calcolare tutte le n-righe della nostra matrice. Quindi:

1 per tutti i k compresi tra 0 e le n − 1 righe di A:2 si inserisce nella sequenza che rappresenta le righe della

matrice la k − esima riga calcolata come abbiamo visto al puntoprecedente.




Come calcolare tutte le CRk ?

In definitiva devo usare due cicli, uno dentro l’altro (annidati):1 per tutti i k compresi tra 0 e le n − 1 righe di A:

1 per tutti gli i compresi tra 0 e le r − 1 colonne di B:2 Si inserisce nella sequenza al posto i − esimo il valore di CRk [i]

che é dato dal risultato del prodotto scalare tra ARk xB[i]2 si inserisce nella sequenza che rappresenta le righe della

matrice la k − esima riga calcolata come abbiamo visto al puntoprecedente.




Le funzioni a mia disposizione

Abbiamo giá implementato il prodotto scalare tra due vettoriPer una maggiore facilitá nella gestione delle colonne nellamatrice B possiamo calcolarne la trasposta. (la matrice traspostaha come generico elemento di indici (i,j) l’elemento di indici (j,i)della matrice originaria.)




Calcolo della matrice trasposta

def trasposta(v):a=[] #sequenza in cui memorizzo la mia traspostafor i in range (0, len(v[0])): # ciclo sugli elementi della colonna

c=[]for j in range(0, len(v)): # ciclo su tutte le righe

c.append(v[j][i]) #elemento (i,j) che diviene l'elemento (j,i)a.append(c) #inserisco la riga alla mia matrice trasposta a

return a




Calcolare AxB

Ecco come risulta la sequenza di istruzioni finali.1 verifico se sia possibile eseguire la moltiplicazione (funzione giá

implementata)Se falso Restituisco erroreSe Vero Eseguo le seguenti istruzioni:

1 Calcolo la trasposta di B (BT )2 per tutti i k compresi tra 0 e le n − 1 righe di A:

1 per tutti gli i compresi tra 0 e le r − 1 righe di BT :2 Si inserisce nella sequenza al posto i − esimo il valore

di CRk [i] che é dato dal risultato del prodotto scalare traARk xBT

Ri

3 si inserisce nella sequenza che rappresenta lerighe della matrice la k − esima riga calcolata comeabbiamo visto al punto precedente.

4 Restituisco la sequenza che mi rappresenta lamatrice




Esprimiamo in python questo algoritmo

..




TxV

def molt_mat(t,v):if se_molt(t,v): # se posso eseguire la molt

c=[] #sequenza di outputr=trasposta(v) #trasposta di rfor i in range(0,len(t)):

rig=[]for j in range(0, len(r)):#ciclo sulle righe della trasposta

k=molt_vet(t[i],r[j]) #prodotto scalarerig.append(k) #inseriesco elemento nella riga

c.append(rig) #inserisco la riga in creturn(c) #restituisco il ris

else:return(False)




Esercizio

Si scriva la funzione iterativa che preso come argomento unasequenza restituisca la sequenza dove tutti gli elementi adiacentiuguali siano stati ridotti a un solo elemento.Esempio: rimdup([1,2,3,3,3,2,4,4,3])→ [1,2,3,2,4,3]




Soluzione

def rimdup(s):if len(s)<=1:

return(s)else:

o=[]conf=s[0]o.append(conf)for i in range(1,len(s)):

if conf<>s[i]:conf=s[i]o.append(conf)

return o




Esercizi

Scrivere e documentare le funzioni che risolvano i seguenti problemi:1 Definire una funzione che presa una sequenza come parametro

restituisca il valore della media geometrica di tale sequenza2 Definire una funzione che presa una terna di valori come

parametro mi dica se questa é una terna pitagorica o meno3 Definire una funzione che presa un sequenza mi restituisca tutti i

possibili suffissi di tale sequenza (es. (1,4,3)→ (), (3,), (4,3),(1,4,3)) usare l’iterazione e la ricorsione

4 Definire una funzione che presa un sequenza e un parametrointero mi restituisca tutti i possibili suffissi di tale sequenza finoalla lunghezza definita dal parametro intero (es. preso (1,4,3), 1→ (), (3,)) usare l’iterazione e la ricorsione

Inviate gli esercizi svolti a: [email protected]




Cosa abbiamo fatto?

1 Correzione esercizi

2 Fase di Progettazione - Algoritmi

3 Esercizi

4 Esercizi per casa


Laboratorio di Python - DISIzuppirol/lez5.pdf · Correzione esercizi Fase di Progettazione -...

Documents

Transcript of Laboratorio di Python - DISIzuppirol/lez5.pdf · Correzione esercizi Fase di Progettazione -...