Strutture iterative
Ver. 2.4
© 2010 - Claudio Fornaro - Corso di programmazione in C
Strutture iterative
Problema:
Visualizzare i numeri interi da 0 a 1000 Soluzione
printf("0\n");
printf("1\n");
printf("2\n");
printf("3\n");
printf("4\n");
...
Non è davvero una buona idea… ma con le conoscenze attuali non c’è alternativa
3
Strutture iterative
Vorremmo scrivere:
“ Esegui l’istruzione:
printf("%d\n", i);
con i che assume i valori da 0 a 1000 ”
i<=1000
VF
stampa i
i=0
i=i+1
percorso chiuso, detto “anello”,
“loop” o “ciclo”
4
I cicli in C
Per “tornare indietro” si potrebbe utilizzare un’istruzione apposita, ma per questioni di chiarezza si utilizzano strutture sintattiche che fanno “tornare indietro” solo se la condizione di ripetizione è vera
Le strutture iterative sono comunemente dette cicli o loop
In C i cicli sono controllati da una condizione di permanenza nel ciclo: fintantoché la
condizione è vera, si esegue il corpo del ciclo
(il blocco di codice da eseguire più volte)
Ciclo WHILE
Fa eseguire un blocco di codice fintantoché una certa condizione è vera
Valuta la condizione prima di eseguire il blocco
Se la condizione è inizialmente falsa,
il blocco non viene eseguito neppure una volta condizione
V
F
blocco
Ciclo WHILE
while (condizione) senza il ‘;’
blocco
Viene valutata la condizione:
se è vera
esegue il blocco
torna su a valutare nuovamente la condizione
se è falsa
passa ad eseguire le istruzioni successive al blocco
La condizione può essere un’espressione qualsiasi (come nel costrutto if)
7
Ciclo WHILE
Esempio
Il seguente codice somma i valori introdotti finché non viene dato il valore 0
somma = 0;
scanf("%d", &v);
while (v != 0) {
somma += v;
scanf("%d", &v);
}
printf("Somma: %d", somma);
8
Ciclo FOR
Come il ciclo WHILE fa eseguire il blocco fintantoché la condizione è vera
for (espr1;condizione;espr2) senza il ‘;’
blocco
Viene calcolata espr1 (soltanto la prima volta)
Viene valutata la condizione:
se è vera:
esegue il blocco
esegue expr2
torna su a valutare nuovamente la condizione
altrimenti (se è falsa):
passa ad eseguire le istruzioni successive a blocco
Ciclo FOR
condizione
V
F
expr2 blocco
expr1
Il flow-chart corrispondente è il seguente:
Ciclo FOR
La condizione può essere un’espressione qualsiasi, se manca viene considerata pari a 1
expr1 e/o expr2 possono mancare (ma i separatori ‘;’ devono esserci ugualmente)
Esempio
Stampa i numeri interi da 0 a 1000 for (i=0; i<=1000; i++)
printf("%d", i);
Una variabile come i nell’esempio precedente che tiene conto del numero di iterazioni viene detta variabile di conteggio o indice
Notare che, nell’esempio, dopo che il ciclo è stato eseguito completamente, i vale 1001
11
Ciclo FOR
Il ciclo FOR è un ciclo WHILE riscritto in modo tale da raggruppare tra le parentesi tutto ciò che gestisce l’indice: inizializzazione (espr1), controllo (condizione) e aggiornamento (espr2)
for (espr1;condizione;espr2) blocco
Il ciclo FOR precedente equivale a:
expr1; fuori dal corpo del ciclo!
while (condizione) {
blocco expr2;
}
12
Ciclo FOR
Esempio
Questo ciclo WHILE:
i=0;
while (i<=1000) {
printf("%d", i);
i++;
}
e questo ciclo FOR:
for (i=0; i<=1000; i++) printf("%d", i);
sono equivalenti, ma il secondo è più compatto
La variabile di conteggio
Talvolta è conveniente che il nome della
variabile di conteggio sia corto per questioni di leggibilità del codice
Esempio
for (i=0; scanf("%d",&v[i])!=EOF; i++) tot += v[i]*v[i-1]*v[i+1];
totValoriLetti = i;
Qui v[i] viene usata nel corpo del ciclo più volte, quindi è conveniente usare come indice i e non la variabile totValoriLetti che invece viene assegnata alla fine del ciclo
La modifica della variabile di conteggio dentro il ciclo for viene considerata pratica da evitare in quanto può rendere il codice complesso
Scelta tra ciclo FOR e WHILE
Quando il numero di iterazioni è noto a priori (e quindi il ciclo è controllato da un indice ), è preferibile (per chiarezza e stilisticamente) utilizzare un ciclo FOR che raggruppa in un punto solo l’inizializzazione, il controllo e l’aggiornamento dell’indice
15
Ciclo DO-WHILE
Fa eseguire un blocco di codice fintantoché una certa condizione è vera
Valuta la condizione dopo aver eseguito il blocco
Anche se la condizione è inizialmente falsa, il blocco viene eseguito almeno una volta
condizione
V
F
blocco
16
Ciclo DO-WHILE
Nella letteratura questo ciclo viene detto ciclo Repeat-Until (dove però se la condizione è vera si esce dal ciclo: non è di permanenza)
do {
blocco
}while (condizione); con il ‘;’
La condizione può essere un’espressione qualsiasi che produce un valore
Le graffe sono opzionali, ma consigliabili (proprio con la graffa di chiusura subito prima della keyword while) per distinguere
facilmente il ciclo WHILE dal ciclo DO-WHILE
Ciclo DO-WHILE
Esempio
Somma i valori dati finché non viene introdotto il valore particolare 0
somma = 0;
do {
scanf("%d", &v);
somma += v;
}while (v != 0);
Notare che il valore v viene comunque
addizionato a somma (ma in questo esempio non causa problemi: somma uno 0)
Scelta tra ciclo WHILE e DO
Si può sempre passare da un tipo di ciclo ad un’altro modificando (poco) il programma
La scelta tra ciclo WHILE e ciclo DO-WHILE è spesso ovvia e questione di preferenze
personali
19
Programmazione strutturata
Nasce dalla necessità di regolamentare e standardizzare le metodologie di
programmazione
Un linguaggio strutturato deve avere almeno i seguenti 3 tipi di strutture:
La sequenza: ossia la possibilità di definire un blocco di istruzioni (le graffe in C, ma anche il semplice elenco di istruzioni)
L’ alternativa: costrutti di selezione (if e switch)
L’ iterazione: costrutti per ripetere uno stesso blocco di istruzioni (for, while, do-while)
20
Programmazione strutturata
Le strutture di un linguaggio strutturato devono avere le seguenti caratteristiche:
ogni struttura (compresi i blocchi controllati) deve avere un unico punto di ingresso e un unico punto di uscita (così da non avere altre interazioni con l’esterno e poter essere considerata come un’unica macro-istruzione )
ogni struttura può avere nel blocco controllato altre strutture (di ogni tipo)
Un programma è strutturato se usa solo le strutture indicate nei modi indicati sopra
Il linguaggio C è strutturato, ma permette
anche di scrivere codice non strutturato
Programmazione strutturata
In Linguaggio C si ha programmazione non strutturata quando si usano le istruzioni:
goto
break
continue
return multipli in una funzione
Quando si richiede una programmazione strutturata le istruzioni precedenti sono tutte vietate
Dette istruzioni possono talvolta dare
vantaggi anche non marginali per chiarezza e velocità di esecuzione, ma non se ne abusi
Break
Per uscire da un ciclo immediatamente, senza aspettare la valutazione della condizione, si può utilizzare l’istruz. non strutturata break
Dopo il break, l’esecuzione continua dalla prima riga successiva al blocco
while (condizione) { istruzioni...
if (condizione_particolare) break;
istruzioni...
}
Il break può essere usato per gestire condizioni particolari e infrequenti (non deve essere il metodo normale di terminazione del ciclo)
23
Break
Esempio
Somma fino a 10 valori dati in input. Per introdurre meno valori, introdurre 0 somma = 0;
for (i=0; i<10; i++) {
scanf("%d", &v);
if (v == 0) break;
somma += v;
}
printf("Somma = %d\n",somma);
24
Break
La formulazione equivalente strutturata è:
esci = NO;
somma = 0;
for (i=0; i<10 && esci==NO; i++) {
scanf("%d", &v);
if (v == 0) esci=SI;
else
somma += v;
}
printf("Somma = %d\n",somma); i++
Continue
Per passare immediatamente all’iterazione successiva, si può utilizzare l’istruzione non strutturata continue
Per effetto dell’istruzione continue:
vengono saltate tutte le istruzioni dalla continue fino alla parentesi di terminazione del corpo del ciclo
se si tratta di un ciclo for, viene eseguita expr2
l’esecuzione riprende dalla valutazione della condizione
Continue
Schema con ciclo while while (condizione) {
istruzioni...
if (condizione_particolare) continue;
istruzioni saltate se eseguito continue }
27
Continue
Schema con ciclo do-while do
{
istruzioni...
if (condizione_particolare) continue;
istruzioni saltate se eseguito continue }while (condizione);
28
Continue
Esempio
Somma i valori dati finché non viene introdotto il valore 0, ignorando i negativi.
somma = 0;
do {
scanf("%d", &v);
if (v < 0) continue;
somma += v;
}while(v != 0);
Continue
La formulazione equivalente strutturata è in questo caso più chiara:
somma = 0;
do {
scanf("%d", &v);
if (v >= 0) somma += v;
}while(v != 0);
Lettura di valori
Quando non si può sapere a priori il numero di valori che verranno introdotti dall’utente si deve trovare un modo per stabilire la fine dell’input:
Si chiede all’utente quanti valori verranno introdotti
Si prevede un valore particolare che quando introdotto indica la fine dell’input, tale valore è detto sentinella (es. lo 0 degli esempi precedenti)
Si chiede all’utente di segnalare la fine dell’input mediante l’immissione di un codice di controllo detto End Of File (EOF) che viene riconosciuto e segnalato dalle stesse funzioni di input (mentre la sentinella viene riconosciuta dopo l’input)
31
Lettura di valori
La costante EOF è un valore intero definito in stdio.h (in genere vale –1)
Viene prodotto dall’utente premendo:
Windows Control-Z e poi INVIO
Linux/Unix Control-D
Le funzioni scanf e getchar restituiscono EOF quando l’utente indica la fine dell’input
In modo analogo gets restituisce NULL
N.B. Le combinazioni di tasti Control-Z e
Control-D spesso vengono scritte ^Z e ^D, ma NON si ottengono con il carattere ^ : si deve invece premere il tasto Control e poi la lettera
32
Lettura di valori
Esempio di lettura di sequenza di lunghezza ignota di valori dalla tastiera, la lettura termina con l’introduzione di un EOF printf("Terminare con EOF\n");
while (scanf("%d", &a) != EOF) somma += a;
printf("Somma=%d\n", somma);
Esempio di input:
12 22 34
^Z
Somma=68
Cicli annidati
Un ciclo può essere collocato
( completamente ) nel corpo di un altro ciclo
In genere, nel caso di cicli FOR ogni ciclo deve avere una variabile di conteggio diversa
Il ciclo esterno controlla quello interno
Il ciclo interno ricomincia sempre da capo (ad esempio l’inizializzazione dell’indice di un ciclo FOR interno ad un altro ciclo viene eseguita ogni volta)
Cicli annidati
Esempio
for (i=1; i<=7; i+=3) {
for (j=2; j<5; j++)
printf("%d,%d ", i, j);
printf("\n");
}
printf("%d,%d ", i, j);
produce il seguente output:
1,2 1,3 1,4 4,2 4,3 4,4 7,2 7,3 7,4
10,5 notare i valori di uscita
Ciclo esterno Ciclo interno
Blocco ciclo esterno
Blocco ciclo interno
35
Uscita da cicli annidati
Nel caso di cicli annidati, break fa uscire solo da un livello; per uscire contemporaneamente da tutti i cicli annidati si può usare una goto
for (i=0; i<10; i++) for (j=0; j<10; j++) { scanf("%d", &v);
if (v == 0) goto fuori;
somma += v;
} fuori:
printf("Somma = %d\n",somma);
36
Uscita da cicli annidati
Per evitare di avere codice non strutturato e a scapito di un po’ di efficienza si può scrivere:
esci = NO;
for (i=0; i<10 && esci==NO; i++) for (j=0; j<10 && esci==NO; j++) { scanf("%d", &v);
if (v == 0) esci = SI;
else
somma += v;
}
printf("Somma = %d\n",somma);
Etichette
Una label ( etichetta ) viene usata per dare un nome ad una riga, viene in genere posizionata all’inizio della riga stessa senza indentazione ed è terminata da un carattere ‘:’, esempio:
fuori:
Tutte le label devono avere nomi diversi (stesse regole sintattiche degli identificatori)
Una label è visibile in ogni punto della
funzione dove è definita, ma non al di fuori di essa
Salti
Un “salto” fa continuare l’esecuzione di un programma da un altro punto del codice
Il salto incondizionato goto ha sintassi:
goto label; label senza il carattere ‘:’
Quando viene eseguita, il programma salta alla riga con quella label e continua da lì
Una label può essere collocata in una riga precedente o successiva quella con il goto (salto indietro o avanti), ma nell’uso accettato sarà sempre avanti e in posizioni ben precise
Una label può essere usata da più goto, ma nell’uso accettato non si presenta mai il caso
39
Salti
L’utilizzo di goto produce sempre codice non strutturato e quindi potenzialmente più difficile da comprendere e da manutenere
I vecchi linguaggi di programmazione non disponevano di costrutti strutturati e l’uso del goto era indispensabile, i frequentissimi rimandi da una parte all’altra del codice lo rendevano molto intricato (“spaghetti code”)
Se il linguaggio dispone di adeguati costrutti strutturati si può sempre evitare di usare i goto. Il linguaggio C ha questi costrutti.
40
Salti
In alcuni (pochi) casi il goto può essere utile per questioni di efficienza e chiarezza
La liceità di utilizzo del goto è oggetto di diatribe, con ferventi e autorevoli sostenitori in entrambe le parti (Dijkstra vs. Knuth)
Con il goto sono “condannati” anche break,
continue e return multipli
Salti
E’ utile l’uso del goto per uscire da due o più cicli annidati, in questo caso l’etichetta DEVE essere collocata subito sotto il corpo del ciclo più esterno (senza istruzioni intermedie) ed è preferibile che sia allineata verticalmente con la keyword del ciclo più esterno da cui uscire
Allineati verticalmente
for (…
{
}
fuori:
for (…
{ … if (condizione speciale) }
goto fuori;…
Etichetta subito sotto il corpo del ciclo più esterno
Salti
Si eviti il goto in tutti gli altri casi
Alcuni linguaggi moderni (es. Java) non hanno goto, ma dispongono di costrutti aggiuntivi (es. break con etichetta) proprio per uscire da cicli annidati
43
Esercizi
1.
Scrivere un programma che calcoli la media (con parte frazionaria) di 100 valori introdotti dalla tastiera.
2.
Scrivere un programma che chieda quanti siano i valori che verranno introdotti dalla tastiera, li chieda tutti e ne stampi la somma e la media.
3.
Scrivere un programma che calcoli la media di tutti i valori introdotti dalla tastiera finché non ne viene introdotto uno non compreso tra 18 e 30, ad esempio 9999 (provare proprio
questo valore!). La visualizzazione della media deve avvenire solo alla fine (ossia non ogni volta che un valore viene introdotto).
44
Esercizi
4.
Scrivere un programma che richieda N numeri da tastiera e ne calcoli il valore massimo.
5.
Scrivere un programma che richieda N numeri da tastiera e ne calcoli il valore massimo, il valore minimo, la somma e la media.
6.
Si scriva un programma che calcoli il fattoriale di un numero intero N dato dalla tastiera. Si ricordi che il fattoriale di un numero n (simbolo
n !) viene calcolato con la seguente formula:
n ! = n ·( n –1)·( n –2)· ... ·2 ·1.
Esercizi
7.
Scrivere un programma che calcola i primi N numeri di Fibonacci, con N introdotto dalla tastiera. I numeri di Fibonacci sono una sequenza di valori interi che inizia con i due valori fissi 1 e 1 e ogni successivo valore è la somma dei due precedenti.
Ad esempio i primi 10 numeri di Fibonacci sono: 1 1 2 3 5 8 13 21 34 55.
8.
Scrivere un programma che calcoli i primi numeri di Fibonacci minori o uguali a N , con N introdotto dalla tastiera.
Ad esempio i primi numeri di Fibonacci minori o uguali a 10 sono: 1 1 2 3 5 8.
Esercizi
9.
Si scriva un programma per calcolare ex mediante il suo sviluppo in serie:
Ogni frazione aggiunge precisione al risultato, per cui conviene usare valori di n
adeguatamente elevati, ad esempio compresi tra 30 e 40. Si verifichi che i risultati calcolati in questo modo siano coerenti con quelli forniti dalla funzione intrinseca exp
calcolando la differenza dei valori.
! ...
3
! 2
! 1 1 e
3
2
x x x
x
47
Esercizi
10.
Si scriva un programma dove il calcolatore determini casualmente un numero intero compreso tra 0 e 99 e chieda all’utente di trovare il numero stesso. Ad ogni input dell’utente il calcolatore risponde con “troppo alto” o “troppo basso”, finché non viene trovato il valore corretto. Per generare valori casuali si utilizza la funzione rand.
11.
Si scriva un programma per calcolare la radice quadrata mediante la formula
iterativa di Newton:
i i
i
x
x A
x 2
1
1
48
