DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Costrutti iterativi
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 20 Marzo 2013
WAT?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il bello dei feedback
WAT
 l'ingegnere Nacci è stato molto chiaro nelle
spiegazioni
 L'esercitatore ha spiegato la sua parte
troppo velocemente, senza troppa
chiarezza, parlando di una roba e di
un'altra come se stesse parlando della
stessa cosa
2
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Costrutti iterativi
 do.. while
 While
 for
3
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
4
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
5
MaIuScOli: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
6
MaIuScOli: codice corretto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
7
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
8
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
9
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);
10
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);
11
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
12
MCD: zoom
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
13
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
14
Il maggiore: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
15
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
16
Nuoto: codice - errori
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Cosa succede a giudice
ad ogni iterazione?
NIENTE!!!!
Ciclo infinito!!!
17
Nuoto: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
18
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!
19
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
20
Il maggiore: zoom sul codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
21
Il ciclo for
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
cont = 0;
while (cont < N) {
…;
…;
cont++;
}
for (cont = 0; cont < N; cont++) {
…;
…;
}
22
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
23
Il maggiore – for : codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
24
Il maggiore – while Vs for
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
25
Ora dovrebbe essere chiara…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
26
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,…
27
Il fattoriale: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
28
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
29
Coefficiente binomiale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Il numero di scelte di k oggetti fra quelli
che costituiscono un insieme di n
elementi
• Quindi il numero dei sottoinsiemi di k
elementi di un dato insieme di n oggetti,
è dato dal cosiddetto coefficiente
binomiale:
30
Coefficiente binomiale: flusso
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. Inserire K e N
2. Verifico K e N
3. Se corretti
A.
B.
C.
D.
Calcolare il fattoriale di N (FatN)
Calcolare il fattoriale di K (FatK)
Calcolare il fattoriale di N-K (FatNK)
CoefBin = FatN/(FatK)*FatNK
4. Altrimenti torno a 1
31
Coefficiente binomiale: codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
32
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
33
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/