13e15marzo2013 Problemsolving,Ricorsione,IterazionecondizionataSaraZuppiroli LaboratoriodiPython

(1)

Iterazione condizionata

Laboratorio di Python

Problem solving, Ricorsione, Iterazione condizionata

Sara Zuppiroli

Università di Bologna

13 e 15 marzo 2013

(2)

Sommario

1 Correzione esercizi

2 Problem Solving

3 Ricorsione e i sotto-problemi

4 Iterazione condizionata Sintassi ed Esempi

(3)

Errore di semantica

Esercizio

def vocali(s):

voc='' for c in s:

if c in 'aeiou':

voc=voc+c return voc

Cerchiamo di capire cosa fa questo programma

Provate la funzione vocali nel modo seguente: vocali (’CASA’)

(4)

Errore di specifica

Esercizio

X=str(input('inserisci stringa')) def rev(x):

ris='' for c in x:

ris=c+ris print (ris) rev(X)

Scrivere una funzione che presa una stringa in input e non come parametro la scriva al contrario

(5)

Errore

Esercizio

def palin(s):

n=0

for c in s:

if c==s[len(s)-1-n]:

n=n+1

return 'stringa palindroma' else:

return

Cosa non é corretto in questa soluzione?

(6)

Problem solving

Definizione informale

É una attivitá del pensiero che si mette in atto per raggiungere un determinato risultato.

Puó essere svolta in maniera intuitiva o metodologica.

Fasi del metodo intuitivo:

Individuazione del problema Suddivisione in sotto-problemi Formulazione e verifica dell’ipotesi Valutazione delle soluzioni

Implementazione della soluzione migliore

(7)

Problem solving e produzione del Software

Problem solving produzione del Software Individuazione e suddivisione del problema Analisi

Verifica e valutazione delle soluzioni Progettazione Implementazione della soluzione Implementazione

Verifica dei risultati Debugging

Tabella:Problem solving vs produzione del Software

(8)

Strumenti per la suddivisione in sotto-problemi

Analizzando il problema ci si puó accorgere che questo sia suddivisibile in problemi piú semplici

Ogni paradigma di programmazione prevede diverse tecniche per raggiungere questo obiettivo:

Il paradigma di programmazione imperativa suddivide il programma in funzioni raggruppate in moduli raggruppati poi in package Il paradigma ad oggetti progetta classi che sono raggruppate in package

(9)

Ricorsione e la scomposizione in sotto-problemi

Una funzione matematica é definita ricorsivamente quando nella sua definizione compare un riferimento a se stessa

Operativamente, risolvere un problema con un approccio ricorsivo comporta:

l’identificazione di un ’caso base’ (n = n0) in cui la soluzione sia nota

esprimere la soluzione al caso generico n con (n ≥ n0)mediante la soluzione allo stesso problema basandosi su uno o piú casi precedenti (n − 1, n − 2, · · · ).

La ricorsione é basata sul principio di induzione dei numeri Naturali.

Quindi stiamo risolvendo il problema a riconoscendo un caso base su cui costruire tutte le altre soluzioni.

(10)

Principio di induzione e ricorsione

Unasuccessione di proposizioni logiche (P_n)_n∈Né una successione di affermazioni con identico predicato P riferito ad espressioni dipendenti da un numero naturale n.

Principio di induzione:

Data Pnuna successione di proposizioni logiche tale che:

P_n₀ é una proprietá che vale per n₀∈ N (caso base) e se risulta Pnk vera → Pnk +1vera, nk ≥ n₀(passo induttivo) allora P(n) é vera per ogni n ≥ n₀

Questo é il principio su cui si basa la ricorsione

(11)

Come definire una funzione ricorsiva

Quindi per definire una funzione ricorsiva bisogna:

individuare il caso base di cui si ha una soluzione

cogliere il passo induttivo, esprimendo la stessa funzione per un generico n rispetto a uno o piú soluzioni precedenti

Utilizzando la ricorsione si puó testare la nostra funzione usando la dimostrazione per induzione

(12)

Esempio funzione ricorsiva

def palin(s):

x=len(s)

if x==0 or x==1:

return 'palindroma' if s[0]==s[x-1]:

return palin(s[1:x-1]) else:

return 'non palindroma'

(13)

Esempio

Alice distribuisce i suoi dadi colorati (r ) in un numero n di scatole.

Alice li distribuisce in modo tale che in ogni scatola ci sia un diverso numero di dadi colorati, e ne sia presente almeno uno in ogni scatola.

Qual é il numero minimo di dadi colorati posseduti da Alice?

Individuiamo le possibili soluzioni a questo problema.

(14)

Soluzioni

1 Metodo iterativo

2 Metodo ricorsivo

3 Applicazione di una formula

(15)

Soluzioni

1 Possiamo mettere tutte le scatole in fila e poi inseriamo un dato in ogni scatola, finite le scatole riparto con la stessa operazione partendo dalla seconda scatola e cosí fino all’ultima.

2 Se ho una scatola allora il numero di dati sará 1. Se ho un numero n di scatole allora il mio numero totale di dadi sará il mio numero n sommato al numero di dati che avrei avuto con n − 1 scatole.

3 Ci potremmo accorgere che questo non vuol dire altro che applicare la formula della somma dei primi n numeri naturali, e quindi basterá restituire il risultato di questa formula n ∗ (n + 1)/2

(16)

Testiamo le soluzioni

Proviamo le nostre funzioni con diversi dati alice(3), alice(10), alice (100)

vediamo qualche differenza percettibile nell’esecuzione dei nostri programmi?

(17)

Esempio di Ricorsione

Data la serie di Fibonacci cosí definita:

F₀=1 F1=1 Fn=Fn−1+Fn−2

Scrivere una funzione che prenda come parametro n, dove tale parametro rappresenta l’ennesimo valore nella serie di fibonacci e restituisca il valore di Fn.

(18)

Outline

2 Problem Solving

(19)

Iterazione Sintassi

while <condizione>:

<istruzioni_while>

while: indica l’operatore di iterazione condizionata.

condizione: é l’espressione booleana che viene controllata la prima volta che si incontra l’istruzione while e ogni volta che si conclude la sequenza di <istruzioni_while>

istruzioni_while: sono l’insieme di istruzioni che vengono eseguite se e soltanto se risulta True la condizione Attenzione:

Se si usa l’iterazione condizionata bisogna verificare che

(20)

Iterazione esempio

def menu():

print('Seleziona 1 per calcolare la somma dei primi n numeri') print('Seleziona 2 per calcolare le soluzioni della disequazione') print('Seleziona 3 per calcolare l''equazione di secondo grado') print('Seleziona 5 per uscire')

x= int(input('Digita la tua scelta')) while 1<=x<=3:

if x==1:

a=somma_nat_input() print(somma_nat(n))

x= int(input('Digita la tua scelta')) elif x==2:

a,b,c=equazione_sec_grad_input() print(diseq_sec_grado(a,b,c))

x= int(input('Digita la tua scelta')) elif x==3:

a,b,c=equazione_sec_grad_input()

(21)

Break

break: si trova annidato in un ciclo (for while). Interrompe l’esecuzione del ciclo

(22)

Esempi

Scrivere una funzione che dato un numero mi restituisca tutti i suoi divisori.

Utilizzare il ciclo for e while

(23)

Soluzione Divisori

for

def divisori(x):

for i in range(x+1)[1:]:

if x%i==0:

print(i)

var: in questo esempio é chiamata i. Per ogni i appartenente alla tupla si esegue l’istruzione condizione: < if x%i==0: print(i)>

sequenza: é creata dalla funzione range(x+1) che crea un tipo range che implementa l’iterazione e attraverso [1:] per indicare che il primo valore su cui fare l’iterazione é 1. Quindi si

eseguono le iterazioni per i ∈ {1, · · · , x }. Si parte da 1 per non dividere per 0.

istruzioni_for: se il modulo della divisione tra x e i é 0 allora

(24)

Soluzione Divisori

while

def divisori(x):

i=1

while i<=x : if x%i==0:

print(i) i+=1

i viene inizializzata

si implementa il ciclo col controllo su i e x

(25)

While e for a confronto

(a) (b)

(26)

Confronto

Il while e il for sono equivalenti?

(27)

Esercizi

Scrivere una funzione che dati due numeri mi stampi il MCD tra i due numeri usando ciclo for e while

Scrivere una funzione che dato un numero dica se questo é primo usando ciclo for e while

Scrivere una funzione che dato un numero mi stampi tutti i numeri primi che lo dividano usando ciclo for e while

(28)

Esercizi a casa

Scrivere un programma che sia in grado di calcolare le seguenti serie:

la somma dei primi n numeri naturali (soluzione iterativa con for) la serie geometrica (soluzione ricorsiva)

la somma dei primi n numeri dispari (soluzione iterativa con while) Inviate gli esercizi svolti a: labinfo.mat.unibo@gmail.com

(29)

Cosa abbiamo fatto?

2 Problem Solving