Le istruzioni cicliche o iterative: for e while
Ciclo o iterazione: un gruppo di istruzioni che può essere ripetuto più volte.
Supponiamo di avere a disposizione 10 raggi e di voler calcolare 10 circonferenze.
L’algoritmo sarà allora:
ripeti 10 volte:
leggi(raggio)
circonferenza ¬2* 3.1415*raggio stampa(circonferenza)
In via del tutto generale l’utente dice al programma quante circonferenze deve calcolare come segue:
leggi(n)
ripeti n volte:
leggi(raggio)
circonferenza ¬2* 3.1415*raggio stampa(circonferenza)
C istruzioni iterative
Istruzione ciclica for:
for (inizializza; condizione; modifica) { istruzione;
} ...
dove:
– inizializza é un'espressione eseguita la prima volta, (serve per inizializzare le variabili di ciclo)
– condizione é un'espressione logica
– modifica é un'espressione eseguita alla fine di ogni iterazione (serve per aggiornare le variabili di ciclo)
– il programma esegue ripetutamente il blocco di istruzioni finché la condizione é true e passa all'istruzione successiva appena la condizione diventa false
– Le 3 espressioni nel for sono opzionali
no
Inizializz.
modifica Istruzione
...
si cond?
C istruzioni iterative
Implementiamo in C l’algoritmo per calcolare n volte la circonferenza di un cerchio
...main () {
const float pi=3.1415;
float circonf, raggio;
int n,i;
printf(”Dimmi quanti raggi hai: \n“);
scanf("%d",&n);
for (i=1;i<=n;++i) {
printf(“Inserisci il raggio: \n");
scanf("%f",&raggio);
circonf=2*pi*raggio;
printf("circonferenza = %f\n",circonf);}
}
eser2.4.cpp
Esempio
Assegnato un numero n compreso tra 1 e 10, stampare la tabellina relativa a un numero preassegnato. Per es. se n=4 deve stampare
4x1=4 4x2=8 4x3=12 ………..4x10=40 L’algoritmo relativo diventa:
leggi(numero)
for (i¬1;i<=10;++i) stampa(numero*i)
Il ciclo for può essere utilizzato solo se si conosce a priori quante volte il corpo del
ciclo deve essere ripetuto.
Esercizio
Sommare gli interi pari compresi tra 2 e 20…
C istruzioni iterative
Tornando al problema del calcolo della circonferenza si vuole consentire all’utente di calcolare un numero imprecisato circonferenze fino a quando non si dà un raggio uguale a zero.
Un possibile algoritmo è il seguente:
leggi (raggio)
finchè raggio>0 ripeti:
circonferenza ¬2* 3.14*raggio stampa(circonferenza)
leggi(raggio)
Qui sappiamo che il corpo del ciclo deve essere eseguito ogni volta che il numero letto è diverso da zero.
In questi casi possiamo ricorrere al ciclo while.
C istruzioni iterative
Istruzione ciclica while:
while (condizione) { istruzione;
} ...
dove:
– condizione é un'espressione logica che viene verificata all'inizio di ogni iterazione del ciclo
• se la condizione é già inizialmente false, il ciclo non viene eseguito mai
– il programma esegue ripetutamente il blocco di istruzioni finché la condizione é true e passa all'istruzione successiva appena la condizione diventa false
– affinché il loop (ciclo) non si ripeta all'infinito, il blocco di
istruzioni deve modificare qualche parametro della condizione
si
Istruzione ...
cond?
no
C istruzioni iterative
...main () {
const float pi=3.1415;
float circonf,raggio;
printf(”Dammi il raggio: \n“);
scanf("%f",&raggio);
while (raggio > 0) {
circonf=2*pi*raggio;
printf("circonferenza = %f\n",circonf);
printf(”Dammi il raggio: \n“);
scanf("%f",&raggio);
}
return 0;
}
C istruzioni iterative
Il corpo del loop può essere un’istruzione semplice o composta.
Supponiamo di dover ripetere un gruppo di istruzioni soltanto nel caso che a sia minore di b, con a e b numeri interi Scriveremo qualcosa del tipo:
while (a<b) {
(gruppo di istruzioni da ripetere) }
Il gruppo di istruzioni all’interno del ciclo è il corpo del ciclo,
l’espressione booleana (a<b) viene chiamata condizione di ingresso;
la sua negata rappresenta la condizione di uscita dal ciclo.
Una singola esecuzione della sequenza di istruzioni che formano il corpo del ciclo è detta passo del ciclo.
C istruzioni iterative
Siano a e b due numeri interi i cui valori iniziali sono: a=5; b=10;
(rappresentano le inizializzazioni delle variabili del ciclo necessarie per poter valutare l’espressione booleana; se fosse b=10 e a=12 il ciclo non verrebbe proprio eseguito).
Quale sarà il valore di a che verrà stampato alla fine del ciclo?
Dopo l’inizializzazione con a=5 e b=10 entriamo nel ciclo while (la condizione (a<b) è vera)
- otteniamo a=6 e b=9
Si ritorna alla condizione di controllo del ciclo, (a<b), e poiché 6<9, si esegue un altro ciclo
- a=7 e b=8
Si ritorna ancora al controllo (a <b), si verifica che 7<8
- a=8 e b=7
la condizione (a <b) è falsa per cui si salta il ciclo e si esegue l’istruzione subito dopo il
- computer scriverà sul video a=8
a=5;
b=10;
while (a<b) { a++;
b--;
}
passo a b inizio 5 10
N. 1 6 9 N. 2 7 8 N. 3 8 7
esercizio6.6.cpp
C istruzioni iterative
Problema: somma di n numeri
– Dato un numero intero positivo n supponiamo di voler calcolare la somma dei primi n numeri interi positivi: Somma = 1 + 2 + … + n
– Algoritmo 1:
• Definiamo una variabile contatore che assuma come valore, di volta in volta, i numeri interi da 1 a n
• Definiamo una variabile somma che conterrà le somme parziali:
– contatore = 1, somma = (0) + 1 = 1 – contatore = 2, somma = (0+1) + 2 = 3 – contatore = 3, somma = (0+1+2) + 3 = 6
La condizione di iterazione è contatore ≤ n
I valori che abbiamo posto tra parentesi rappresentano la somma ottenuta
al passo precedente;
somma=somma+contatore;
somma+=contatore;
leggi(n)
contatore ß 1 somma ß 0
while (contatore ≤ n):
stampa(somma)
somma ß somma + contatore contatore ß contatore + 1
Algoritmo 1
eser2.8.cpp
ALGORITMO 1 - SOMMA DEI PRIMI N INTERI inizializza contatore a 1 e somma a 0
while contatore <= N ripeti:
incrementa il valore della variabile somma con il contenuto di contatore
incrementa il contatore di 1
Altra possibilità è di inzializzare sia contatore che somma a zero; in tal caso l’algoritmo si modifica come segue:
ALGORITMO 2
inizializza contatore e somma a 0 while contatore < N ripeti
incrementa il contatore di 1
incrementa il valore della variabile somma con il contenuto di contatore
Esempi
OFF BY ONE
ALGORITMO 3
inizializza contatore e somma a 0
finché contatore <= N esegui le due istruzioni incrementa il contatore di 1
incrementa il valore della variabile somma con il contenuto di contatore
ALGORITMO 4
inizializza contatore ad 1 e somma a 0 finché contatore < N ripeti
incrementa il valore della variabile somma con il contenuto di contatore
incrementa il contatore di 1
C istruzioni iterative
...main () {
int somma, contatore, N;
printf(“Calcola la somma dei primi N numeri \n”);
printf(“Inserisci N=\n”);
scanf("%d",&N);
contatore=0; somma=0;
while (contatore<N) {
contatore++;
somma+=contatore }
printf("Somma = %d",somma);
} return 0;
}
C istruzioni iterative
Algoritmo 2 (Gauss):
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 1 2 3 4
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 0 1 2 3
leggi(n)
somma = (n+1)*n/2 stampa(somma)
Algoritmo 2 8 7 6 5
+ + + +
9 + 9 + 9 + 9 = 9 * 4 = (n+1)*(n/2)
7 6 5 4 + + + +
7 + 7 + 7 + 7 = 7 * 4 = n*(n+1)/2
Ciclo Infinito
Se la condizione all’interno del while non è tale da rendere ad un certo punto la condizione falsa, si ha un ciclo infinito perché il programma non ha mai modo di terminare.
Questo può far sembrare il programma bloccato.
C istruzioni iterative
Esempio: calcolo del MCD di due numeri naturali a e b Algoritmo di Euclide (~300 A.C.):
1. Dividere a per b
2. Se il resto r è nullo MCD è b
3. Altrimenti assegna aßb e bßr e torna la passo 1.
a b a/b r passi
93217 1843 50 1067 1
1843 1067 1 776 2
1067 776 1 291 3
776 291 2 194 4
291 194 1 97 5
194 97 2 0 6
eser2.10.cpp
C istruzioni iterative
INPUT a,b
Finché il resto della divisione tra a e b è diverso da ZERO esegui le istruzioni:
Calcola il resto dei due numeri interi a e b Poni b in a (poni il divisore nel dividendo)
Poni il resto della divisione in b
Quando il resto è ZERO allora il MCD è il numero intero contenuto in b Scrivi il MCD b
Notiamo che, poiché il ciclo termina quando il resto della divisione è zero, non è
perfettamente determinato il numero di
passi da eseguire: in tal caso non è possibile utilizzare il ciclo for ma è necessario servirsi del while.
leggi(a,b)
r ß modulo(a,b) while (r > 0):
stampa(b) a ß b b ß r
r ß modulo(a,b)
Algoritmo di Euclide
eser2.10.cpp
C istruzioni iterative
...int a,b,r;
r=a % b;
while (r>0) {
a=b;
b=r;
r= a % b;
}
printf("%d\n",b);
return 0;
}
esercizio6.7.cpp
C++ uso del debug
Debug del programma per il calcolo MCD con DevCpp
– Impostiamo la compilazione in modo da generare informazioni di debug
• StrumentiàOpzioni di compilazioneàGenerazione di
codice/OttimizzazioneàLinkeràGenera informazioni di debug (Yes)
– Ricompiliamo il codice
– Inserimento del breakpoint
• cliccare con il mouse alla sinistra della istruzione di beakpoint
• il breakpoint è un punto di arresto dell’esecuzione del programma, che consente di proseguire passo passo nell’esecuzione
– Eseguiamo il programma fino al breakpoint
• Clicchiamo il tasto di Debug nella finestra di debug (l’esecuzione si arresta al breakpoint)
– Specifichiamo le variabili di osservazione:
• Nella finestra “Debug” clicchiare su Nuova Osservazione e immettere il nome della variabile da osservare
• Le variabili con i valori sono visualizzate nella parte sinistra dell’intefaccia
– Per eseguire istruzione dopo istruzione
• Cliccare su Step succ.
– Per eseguire fino alla fine o al prossimo breakpoint
• Cliccare su Step esterno
– Per interrompere l’esecuzione
• Cliccare su Fema l’esecuzione
ESERCIZI
1- Tenendo presente il programma che calcola la somma dei primi N numeri interi scrivere un programma che determini:
- la somma di tutti i numeri pari e la somma di tutti i numeri dispari inclusi tra 1 ed N;
- la differenza tra i due valori ottenuti
- la somma di tutti gli inversi tra 1 ed N, cioè: 1 + 1/2+1/3 +…+1/n
2- Dato il programma che calcola il Massimo Comun Divisore:
verificare cosa accade se i valori immessi sono entrambi negativi, uno negativo e l’altro positivo, uno positivo ed uno nullo. Apportare al programma le modifiche necessarie affinché dia sempre risposte coerenti.
Esercizi
Calcolare il prodotto dei primi N interi.
Viene spontaneo sostituire il simbolo del prodotto al posto di quello della somma. Se provate a farlo otterrete uno strano risultato: utilizzate il debug (o, ancora meglio, ragionateci sopra).
Quali modifiche devono essere apportate nel programma per eseguire la somma di tutti gli interi inclusi tra due numeri N1 ed N2 prefissati (con N1< N2) ?
Calcolo della Conversione da decimale a Binario.
