DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Costrutti iterativi
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 27 Marzo 2015
Umh…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Per farvi aggiungere al gruppo su
Facebook…
…usate un nome significativo!
2
Umh…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Per farvi aggiungere al gruppo su
Facebook…
…usate un nome significativo!
3
Umh…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Per farvi aggiungere al gruppo su
Facebook…
…usate un nome significativo!
4
Ma prima…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
5
Problema: errori sull’input
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Preso un dato inserito da tastiera
 Per potervi applicare la trasformazione di
nostro interesse
 Dobbiamo prima verificare che il dato sia
coerente con quanto ci aspettiamo
• Soluzione
 Definire l’insieme dei caratteri validi
 Verificare l’appartenenza del carattere
inserito, all’insieme dei caratterei validi
6
Pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati
 L’insieme dei caratteri ammissibili
{a, b, c, …, z}
1.
2.
3.
4.
Richiedere l’inserimento di un carattere
Se carattere inserito corretto
Allora stampa a video carattere-32
Altrimenti stampa a video un messaggio
di errore
7
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati
 L’insieme dei caratteri ammissibili
{a, b, c, …, z}
• Il carattere inserito deve essere
 =>a
 <= z
8
Maiuscolo: solo if
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
9
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
10
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
 Se X = 0?
11
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita FALSA
12
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita FALSA
 Se Y = 0?
13
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita FALSA
 Se Y = 0? Vogliamo una uscita FALSA
14
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita FALSA
 Se Y = 0? Vogliamo una uscita FALSA
 Se X = 1 e Y = 1? Uscita VERA!
15
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
0
0
0
1
16
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
0
0
0
1
17
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
0
0
0
1
18
Condizione da verificare
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il carattere inserito deve essere
 X: =>a
 Y: <= z
• Come vogliamo che si comporti il nostro
modello rispetto a X e Y?
X
0
0
1
1
Y X AND Y
0
0
1
0
0
0
1
1
(prodotto logico)
19
Maiuscolo: AND
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
20
Tornando ad oggi…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
21
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Costrutti iterativi
 do.. while
 While
 for
22
Problema: caratteri MaIuScOli
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva un programma che, preso un
carattere minuscolo da tastiera, ne
riporta a video l’equivalente maiuscolo
 Si continui a chiedere l’inserimento del
carattere, fino a quando questo non è
corretto
23
Pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati
 L’insieme dei caratteri ammissibili
{a, b, c, …, z}
1.Richiedere l’inserimento di un carattere
2.Se carattere inserito corretto
A.Allora stampa a video carattere-32
3.Altrimenti
A.stampa a video un messaggio di errore
B.ritorno ad 1
24
MaIuScOli: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
25
MaIuScOli: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
26
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come si comporta il nostro modello
rispetto a X e Y?
NOTA: quando VERA, continua!
27
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come si comporta il nostro modello
rispetto a X e Y?
NOTA: quando VERA, continua!
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
28
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come si comporta il nostro modello
rispetto a X e Y?
NOTA: quando VERA, continua!
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
29
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come si comporta il nostro modello
rispetto a X e Y?
NOTA: quando VERA, continua!
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
30
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come si comporta il nostro modello
rispetto a X e Y?
NOTA: quando VERA, continua!
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
NO!
31
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
 Se X = 0?
32
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita VERA
33
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita VERA
 Se Y = 0?
34
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita VERA
 Se Y = 0? Vogliamo una uscita VERA
35
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
 Se X = 0? Vogliamo una uscita VERA
 Se Y = 0? Vogliamo una uscita VERA
 Se X = 1 e Y = 1? Uscita FALSA!
36
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
1
1
1
0
37
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
1
1
1
0
38
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
1
1
1
0
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
39
Ma il modello è corretto?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• X: ‘a’ <= carattere
• Y: ‘z’ <= carattere
• Come vorremmo che si comportasse il
nostro modello rispetto a X e Y?
X
0
0
1
1
Y
0
1
0
1
USCITA
1
1
1
0
X
0
0
1
1
Y
0
1
0
1
X AND Y
0
0
0
1
X
0
0
1
1
Y
0
1
0
1
Z: X AND Y
0
1
0
1
0
1
1
0
!Z
40
MaIuScOli: codice corretto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
41
MaIuScOli: codice corretto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
42
MCD: pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
2.
3.
4.
Leggi A e B
min= il minimo tra A e B
trovato = 0; MCD = min;
Finche’ trovato != 1
1. Se MCD divide A e B
1. Allora trovato = 1
2. Altrimenti MCD = MCD - 1
5. Stampa MCD
43
MCD: diagramma di flusso
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Inizio
Leggi A e B
min=minimo{A,B}
trovato = 0
MCD=min
Stampa MCD
no
trovato!=1?
si
no
Fine
MCD divide
AeB
MCD=MCD -1
si
trovato = 1
44
Come traduco il finché? WHILE
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Itera l’esecuzione di una istruzione finché una
certa condizione è vera
int a, b;
condizione di
scanf("%d%d", &a, &b);
PERMANENZA
while ( b > 0 ) {
nel ciclo
a = a + a;
--b;
}
printf ("Il valore di a ora è %d", a);
45
Il ciclo (loop) while
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Itera l’esecuzione di una istruzione
fintantoché una certa condizione è vera
int a, b;
scanf("%d%d", &a, &b);
Che cosa calcola?
while ( b > 0 ) {
a = a + a;
a*2b se b>0
la funzione f(a,b) =
--b;
a
se b≤0
}
printf ("Il valore di a ora è %d", a);
46
Tornando al MCD… il codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
trovato = 0;
1.
Leggi A e B
1.
min= il minimo tra A e B
2.
3.
MCD = min;
Finche’ trovato != 1
1.
Se MCD divide A e B
1. Allora trovato = 1
2. Altrimenti MCD = MCD - 1
4.
Stampa MCD
47
MCD: zoom
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
48
Il maggiore tra N numeri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Trovare il maggiore tra N numeri positivi
inseriti da tastiera
• Soluzione
 Conoscere N
 Richiedere l’inserimento degli N valori
 Ricerca del maggiore tra gli N valori
49
Il maggiore: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
50
La gara di nuoto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Si hanno10 giudici
• 1 giudice = 1 voto
 Ogni voto è nell’itervallo 0-10
 Dato un tuffo, calcolare
• La media dei voti
• Il voto massimo ed il voto minimo
51
Nuoto: codice - errori
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
52
Nuoto: codice - errori
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Cosa succede a giudice
ad ogni iterazione?
53
Nuoto: codice - errori
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Cosa succede a giudice
ad ogni iterazione?
NIENTE!!!!
Ciclo infinito!!!
54
Nuoto: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
55
Osservazioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema 1
 Si continui a chiedere l’inserimento del
carattere, fino a quando questo non è
corretto
• Problema 2
 Trovare il maggiore tra N numeri inseriti da
tastiera
56
Osservazioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema 1
 Si continui a chiedere l’inserimento del
carattere, fino a quando questo non è
corretto
• Problema 2
 Trovare il maggiore tra N numeri inseriti da
tastiera
Del problema 2 conosco il numero di
iterazioni!
57
Il maggiore tra N numeri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Trovare il maggiore tra N numeri inseriti da
tastiera
• Soluzione
 Conoscere N
 Richiedere l’inserimento degli N valori
 Ricerca del maggiore tra gli N valori
58
Il maggiore: zoom sul codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
59
Il maggiore tra N numeri: osservazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Osservazione: Perchè usare un while se
conosco il numero di iterazioni del cliclo?
60
Il ciclo for
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
cont = 0;
while (cont < N) {
…;
…;
cont++;
}
for (cont = 0; cont < N; cont++) {
…;
…;
}
61
Il ciclo for
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
for ( exp.A; cond; exp.I ) {
ist.1;
...
ist.N;
}
exp.A;
while ( cond ) {
ist.1;
...
ist.N;
exp.I;
}
ATTENZIONE
62
Il maggiore – for : codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
63
Il maggiore – while Vs for
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
64
Ora dovrebbe essere chiara…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
65
Il fattoriale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dato n, intero positivo, si definisce n
fattoriale e si indica con n! il prodotto dei
primi n numeri interi positivi minori o uguali
di quel numero. In formule
• Nota:
 0! = 1
 1! = 1
 2! = 2, 3! = 6,…
66
Il fattoriale: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
67
Nota sul fattoriale: permutazioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Vi sono n! diverse sequenze formate da n
oggetti distinti
 Vi sono n! permutazioni di n oggetti
 iI fattoriali enumerano le permutazioni
68
Problemi di fine giornata…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Modificare gli esercizi di oggi, andando,
dove necessario, ad inserire il controllo
sugli ingressi
• Trovare il maggiore tra N numeri positivi
inseriti da tastiera (richiedendo il
numero se negativo)
• Dati N numeri, dire se questi sono tutti
positivi
• Dati N numeri, riportarne a video il
modulo
69
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 Informatica arte e mestiere, S. Ceri, D.
Mandrioli, L. Sbattella, McGrawHill
• Capitolo 6

• Credits
 Daniele Braga - http://home.dei.polimi.it/braga/