3e5aprile2013 Algoritmo,EsercizisullelisteSaraZuppiroli LaboratoriodiPython

Esercizi per casa

Laboratorio di Python

Algoritmo, Esercizi sulle liste

Sara Zuppiroli

Università di Bologna

3 e 5 aprile 2013

Esercizi per casa

Sommario

1 Correzione esercizi

2 Fase di Progettazione - Algoritmi

3 Esercizi

4 Esercizi per casa

Esercizi per casa

Correzione

scrivere e documentare un programma con un menu dove:

la funz prende in input una tupla e restituisce il primo valore presente nella lista che massimizzi la distanza dal valore m=(max+min)/2

la funz prende in input due tuple e restituisce la somma delle due tuple solo se le tuple hanno lunghezza uguale

la funz prende in input tre punti A(x1,y1) B(x2,y2) C(x3,y3) e restituisce True se questi punti possono formare un triangolo.

False altrimenti

la funz prende in input due liste e restituisce la lista dei valori appartenenti ad entrambe le tuple

per uscire dal programma

Esercizi per casa

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)

Esercizi per casa

Correzione

Esercizio

def triangle(x,y,z):

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

return True else:

return False

Cosa manca?

Esercizi per casa

Fase di progettazione

La fase di progettazione, consistente nel determinare il metodo per la soluzione problema.

Le sequenza di operazioni finite che descrivono il procedimento di soluzione a un determinato problema é detto algoritmo.

L’algoritmo non é legato al linguaggio di programmazione che si utilizzerá per implementare la soluzione.

Esercizi per casa

Algoritmo Deterministico

Un algoritmo é definito da una lista finita di istruzioni che specificano il procedimento esatto da eseguire per ottenere un determinato risultato.

In ogni momento di esecuzione dell’algoritmo si sa esattamente quale sia l’operazione successiva da eseguire e quale sia lo stato del sistema.

Esercizi per casa

Esempi di algoritmo

Problema: Date due matrici calcolarne il prodotto. Algoritmo risolutivo:

1 Memorizzare le matrici A^n,k, B^{k ,m}

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

Se vero Allora calcolare ogni elemento mr ,cdella matrice M^n,mcome:

mr ,c=Pk

i=0ar ,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

Esercizi per casa

Passare dall’algoritmo alla sua implementazione

Per fare questo passaggio bisogna prendere in considerazione alcune 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 la risoluzione del mio problema.

Riconoscere e scomporre in sotto-problemi piú facili. (es. [Se vero] non é altro che il prodotto scalare tra due vettori eseguito m*n volte)

Esercizi per casa

La nostra rappresentazione

La matrice A^n,mé una sequenza di sequenze cosí rappresentata:

Ri = (ai,1, · · · ,ai,m)

La matrice risulta essere quindi: A^n,m=R₁, · · · ,R_n

Esercizi per casa

Quindi moltiplicare le due matrici significa

Abbiamo la matrice A^n,mrappresentata come: ARi= (ai,1, · · · ,ai,m) A^n,m =A_R1, · · · ,AR_n

e la matrice B^m,r rappresentata come:

B_Ri = (b_i,1, · · · ,b_i,r) quindi:

B^m,r =B_R1, · · · ,B_Rm

Eseguire il prodotto di AxB significa costruire la seguente matrice C^n,r:

Ogni riga della nostra matrice avrá la seguente struttura dove B[r] é la nostra colonna:

CRk =ARkB[1], · · · , A˙ RkB[r ]˙ e quindi

C^n,r =CR1, · · ·CRn

Esercizi per casa

Come calcolare tutte le C

?

Per calcolare C_Rk 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 ARkB[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 punto precedente.

Esercizi per casa

Come calcolare tutte le C

?

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 CR_k[i]

che é dato dal risultato del prodotto scalare tra AR_kxB[i]

2 si inserisce nella sequenza che rappresenta le righe della matrice la k − esima riga calcolata come abbiamo visto al punto precedente.

Esercizi per casa

Le funzioni a mia disposizione

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

Esercizi per casa

Calcolo della matrice trasposta

def trasposta(v):

a=[] #sequenza in cui memorizzo la mia trasposta

for 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

Esercizi per casa

Calcolare AxB

Ecco come risulta la sequenza di istruzioni finali.

1 verifico se sia possibile eseguire la moltiplicazione (funzione giá implementata)

Se falso Restituisco errore

Se Vero Eseguo le seguenti istruzioni:

1 Calcolo la trasposta di B (B^T)

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 B^T:

2 Si inserisce nella sequenza al posto i − esimo il valore di CR_k[i] che é dato dal risultato del prodotto scalare tra AR_kxB_R^T

i

3 si inserisce nella sequenza che rappresenta le righe della matrice la k − esima riga calcolata come abbiamo visto al punto precedente.

Esercizi per casa

Esprimiamo in python questo algoritmo

..

Esercizi per casa

TxV

def molt_mat(t,v):

if se_molt(t,v): # se posso eseguire la molt c=[] #sequenza di output

r=trasposta(v) #trasposta di r for 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 scalare

rig.append(k) #inseriesco elemento nella riga c.append(rig) #inserisco la riga in c

return(c) #restituisco il ris else:

return(False)

Esercizi per casa

Esercizio

Si scriva la funzione iterativa che preso come argomento una sequenza restituisca la sequenza dove tutti gli elementi adiacenti uguali siano stati ridotti a un solo elemento.

Esempio: rimdup([1,2,3,3,3,2,4,4,3])→ [1,2,3,2,4,3]

Esercizi per casa

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 per casa

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 sequenza

2 Definire una funzione che presa una terna di valori come parametro mi dica se questa é una terna pitagorica o meno

3 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 parametro intero mi restituisca tutti i possibili suffissi di tale sequenza fino alla 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]

Esercizi per casa

Cosa abbiamo fatto?

1 Correzione esercizi

2 Fase di Progettazione - Algoritmi

3 Esercizi

4 Esercizi per casa