Parte 4Dai diagrammi di flusso alla

programmazione strutturata: le istruzioni if, for, while, …

Informatica A.A. 2009/2010

Corso A: Prof. Stefano Berardi http://www.di.unito.it/~stefano Corso B: Prof. Ugo de’ Liguoro http://www.di.unito.it/~deligu

“Corrado Bohm”

Milano, 1923. Professore emerito di Teoria e applicazione delle macchine calcolatrici

presso l’Università di Roma La Sapienza

Indice Parte 4: Diagrammi

1. Il flusso dell’esecuzione e i diagrammi di flusso.

2. Il salto condizionale: l’istruzione IF.3. Iterazione: le istruzioni WHILE e

FOR.4. La programmazione strutturata e il

teorema di Bohm-Jacopini.I diagrammi di flusso venivano usati per

descrivere i programmi nell’epoca in cui si programmava in Assembly. Oggi sono ancora adatti per spiegare programmi molto brevi.

1. Il flusso dell’esecuzione

• L’esecuzione dei programmi C++, assembly, e in generale dei programmi detti “imperativi”, consiste in una successione di trasformazioni dello stato (delle memorie della RAM e del program counter, l’indirizzo della prossima istruzione da eseguire)

• Ogni trasformazione di stato è l’effetto dell’esecuzione di un’istruzione. Per es., una assegnazione x=3; oppure un’istruzione JB L1 che fa “saltare” l’esecuzione a un’istruzione lontana di indirizzo L1 se una certa condizione è vera.

• Il flusso è l’ordine in cui le istruzioni di un programma vengono eseguite.

4-Diagrammi

Diagrammi di flusso

• I diagrammi di flusso sono una rappresentazione in forma di grafo del flusso dell’esecuzione di un programma. Erano un progresso rispetto al linguaggio assembly, perché spostavano l’attenzione dalle istruzioni del programma alla loro relazione reciproca.

inizio/fine

assegnazione

decisione

input/output

direzione del flusso

4-Diagrammi

Esempio di diagramma di flusso:

area di un rettangoloinizio

leggi base

area = base*altezza

leggi altezza

stampa area

fine

Ogni freccia rappresenta la scelta della prossimaistruzione da eseguire.

Il programma C++ corrispondente

inizio

leggi base

area = base*altezza

leggi altezza

stampa area

fine

inizio

leggi base

area = base*altezza

leggi altezza

stampa area

fine

int main() {double base, altezza, area;

cout << "base = ";

cin >> base;

cout << "altezza = ";

cin >> altezza;

area = base*altezza;

cout << "area = "

<< area << endl;

system(“pause”); }4-Diagrammi

Sequenza di diagrammi e Blocchi di istruzioni in C++

{C1;

C2;

…

Ck;}

Blocco di istruzioni

C1

C2

Ck

…

Più in generale, rappresentiamo una sequenza di diagrammi in C++ scrivendo le istruzioni che li rappresentano di seguito, quindi racchiudendole tra graffe, per formare una singola istruzione detta istruzione composta o blocco.

Sequenza di diagrammi

4-Diagrammi

Il flusso dell’esecuzione in C++

• Per gestire le variabili il C++ segue da vicino la nozione di indirizzo di macchina di von Neumann.

• Invece per la gestione dei “salti” da una istruzione all’altra il C++ segue un’idea completamente diversa, quella della programmazione strutturata.

• Noi spiegheremo la programmazione strutturata attraverso i diagrammi di flusso.

• I diagrammi di flusso spiegano come un programma funziona, ma hanno l’incoveniente di essere leggibili solo per programmi brevissimi.

4-Diagrammi

Programmazione strutturata

• La programmazione strutturata individua i diagrammi di flusso piu’ utili tra quelli con una sola entrata ed una sola uscita. Per ciascuno di essi viene introdotto una istruzione: blocchi, IF, WHILE, FOR, … del C/C++. I programmi in C++ sono costruiti con le istruzioni if, while, for cosi’ introdotte.

• Oggi usiamo i diagrammi di flusso per introdurre le istruzioni IF, WHILE, FOR, … e in pochi altri casi.

• Vediamo ora i diagrammi di flusso più importanti insieme alla loro traduzione in C++. 4-Diagrammi

2. Il diagramma di selezione (IF)

L’istruzione IF rappresenta in C++ e in quasi tutti i linguaggi il seguente “diagramma di selezione a due vie”

L’IF fa “saltare” l’esecuzione all’indirizzo di C se l’espressione B vale vero, e all’indirizzo dell’istruzione D se B vale falso.

if (B)

C;

else

D;

B

C D

true false

L’istruzione IF in C++

if (<espr.booleana>) <istruzione1>; else <istruzione2>;

L’IF viene tradotto nei compilatori nel linguaggio Assembly con un salto condizionato, che fa eseguire come prossima istruzione C oppure D a seconda se B è vero oppure falso. Noi utilizzeremo l’IF solo come istruzione primitiva, con la seguente sintassi:

Al posto di istruzione1 e istruzione2 possiamo scrivere una qualunque istruzione o blocco di istruzioni del C++, compresi altri IF: in questo caso si parla di IF annidati.

Il C++ consente un secondo tipo di IF, l’IF tronco.

IF “tronco” (senza ELSE)

if (B)

C;

if (<espr. booleana>) <istruzione>;

B

C

true false

L’IF tronco rappresenta la selezione a due vie con una sola azione C. Se l’espressione booleana B è falsa saltiamo all’istruzione

successiva senza far nulla

Vediamo ora alcuni esempi di uso di IF, IF tronco e IF annidato

Primo esempio di IF: equazione di 1° grado ax=b

Discussione: se a = 0 eq. indeterminata o impossibile, altrimenti x = b/a.

inizio

leggi a, b

a 0true false

stampa b/a stampa “indet. o imposs.”

fine4-Diagrammi

Il programma per l’equazione di 1° grado

inizio

leggi a, b

a 0true false

stampa b/a stampa “no sol.”

fine

inizio

leggi a, b

a 0true false

stampa b/a stampa “no sol.”

fine

int main()

{ double a, b;

cout << "a = ";

cin >> a;

cout << "b = ";

cin >> b;

if (a != 0) cout << "x = " << b/a << endl;

else cout << “Indet. o impossibile" << endl;

system(“pause”);}4-Diagrammi

Secondo esempio di IF: equazione di 2° grado, IF

“annidati”02 cbxax acb 42

1. > 0: due soluzioni reali

2. = 0: una soluzione reale

3. < 0: non ci sono soluzioni reali.

Per scrivere questo programma dovremo utilizzare IF scritti dentro altri IF (IF“annidati”), per distinguere il secondo caso dal terzo.

a

b

2

a

b

2

Sia:

Esempio di IF: diagramma equazione di 2°

gradoinizio leggi a, b, c Delta=b*b–4*a*c

Delta>0

Stampa: (– b rad)/(2*a)

true

rad=Delta Delta=0

Stampa:–b/(2*a) Stampa: “no sol. reali”

fine

true

false

false

Questa viene

detta una decisione annidata

4-Diagrammi

Soluzione eq. di 2° grado in C++main(){ double a, b, c; cin >> a; cin >> b; cin >> c;double Delta = b*b - 4*a*c;if (Delta > 0){double rad= sqrt(Delta); cout << "prima sol. reale = " << (-b + rad)/2*a << endl;cout << "seconda sol. reale = "<< (-b -

rad)/2*a<<endl;}else if (Delta == 0) cout << "Unica sol. reale = " << -b/(2*a) << endl;else cout << "Nessuna soluzione reale" << endl;system("pause");}

sqrt = radice quadrata (funzione

della libreria cmath)

Questo else si riferisce al secondo ifMa come facciamo a stabilirlo?

Questo è un if “annidato”

Quando ci sono IF “annidati” come accoppiamo un if con un

else?Per definizione, la clausola else si riferisce all’ultimo if non accoppiato con un else precedente:

if (B)

if (B’) C;

else C’;

else D;Il secondo “else” viene accoppiato con il primo IF. In questo caso, l’istruzione D verrà eseguita se B è falso; l’istruzione C’ verrà eseguita se B è vero, ma B’ è falso.

4-Diagrammi

If “annidati”: un altro esempio ambiguita’

Dato che la clausola else si riferisce all’ultimo if non accoppiato con un else precedente, se manca un solo else (se un IF è tronco) tutto cambia:

if (B)

if (B’)

C;

else D;Questa volta “else” viene accoppiato con il secondo IF. Dunque l’istruzione D verrà eseguita se B è vero e B’ è falso, non se B è falso.

4-Diagrammi

If annidati: come eliminare le ambiguita’

Avvolgendo ogni sottoistruzione in parentesi graffa ogni ambiguitá scompare:

if (B)

{ if (B’) C; }

else D;L’istruzione D verrà eseguita se B è falso. Le parentesi non sono sempre necessarie come in questo caso, peró sono sempre utili per aggiungere chiarezza.

Queste parentesi sono necessarie se

vogliamo accoppiare il primo IF con l’else

Esempio: es. 3.14 Hubbard: ``indovina il numero’’

Come rappresentare una scelta tra n+1 blocchi

if (B1) <blocco_1>; //se B1 veraelse if (B2) <blocco_2>; //se B1 falsa e B2 veraelse if (B3) <blocco_3>; //se B1,B2 false e B3 vera… … … …else <blocco_(n+1)>;//se B1,…,Bn false

È sufficiente annidare n comandi IF, ciascuno dopo l’else dell’IF precedente. Il risultato è un’istruzione composta che esegue il primo blocco se la prima espressione booleana è vera, il secondo blocco se la prima è falsa e la seconda è vera, eccetera, l’ultimo blocco se tutte le espressioni booleane sono false.

Un IF con più di due scelte: l’istruzione

SWITCH(sconsigliata)• Un tempo per rappresentare la scelta tra più di due alternative veniva usata una istruzione chiamata SWITCH.

• Per completezza nel prossimo lucido spieghiamo il funzionamento dello SWITCH. Tuttavia ne sconsigliamo l’uso, sia per ragioni semplicità di scrittura, sia perché è facile sbagliarsi a usarlo.

• Al posto dello SWITCH, usate un IF annidato come spiegato nel lucido precedente.

Esecuzione dello SWITCH

switch (<espressione>) { case <costante_1>: <istruzioni_1>;

break;...case <costante_k>: <istruzioni_k>;

break;default: <istruzioni>; }

Esecuzione dello SWITCH. Confrontiamo il valore dell’espressione con le costanti. Trovata la prima che coincide col valore eseguiamo le istruzioni relative. Arrivati al break usciamo dal blocco (le parentesi {…}). Quando non troviamo una costante uguale al valore, eseguiamo le istruzioni che seguono il “default”.

3. L’iterazione: il ciclo while

• L’iterazione è l’esecuzione ripetuta di una o più istruzioni (dette “corpo” dell’iterazione). Un diagramma iterativo viene detto un ciclo.

• Un ciclo è controllata dal valore di verità di un certo test. Viene tradotto dal compilatore in linguaggio Assembly mediante un “salto” condizionato JB (ovvero mediante una assegnazione del program counter) che va “all’indietro”, verso una istruzione già eseguita in precedenza.

• Come primo e fondamentale esempio di ciclo vediamo il ciclo while.

Il diagramma di flusso del ciclo while

while (B)

C;

B

C

true false

Il corpo puo’ essere un qualunque blocco di istruzioni C++. Finché B è vero, il while esegue il corpo C e poi di nuovo B. La prima volta che B è falso il while termina: dunque se B è sempre vero il while non termina mai. La sintassi del while è

while (<espr. booleana>) <corpo>;

Un ciclo while rappresenta il seguente diagramma di flusso:

Un programma che richiede il while: la somma dei reciproci

• Problema: dato un intero n calcolare e stampare:

nis

n

i

1

3

1

2

11

1

1

4-Diagrammi

• Soluzione: utilizziamo il seguente algoritmo. Partiamo con s=0, i=1. Finché i<=n, eseguiamo s=s+1.0/i, i=i+1. In questo modo, s prende i valori 1, 1+1/2, 1+1/2+1/3, …, mentre i prende i valori 1, 2, 3, … . Quando i>n, terminiamo e stampiamo s, che a questo punto vale (1+1/2+1/3 + … 1/n).

• Vediamo ora come tradurre tutto con un while.

Somma dei reciproci calcolata con un while

int main() { int n;

cout << "n = "; cin >> n;

double s = 0.0;

int i = 1;

while (i <= n)

{s = s + 1.0/i; i++;}

cout << "La somma dei primi " << n

<< " reciproci = " << s << endl;

system("pause");}

Scrivendo invece: s = s + 1/i; la divisione 1/i è intera, dunque viente arrotondata: per es. 1/2 diventa 0

++i è detto incremento. Cosa succede se lo eliminiamo ???

Il ruolo di ++i nella “somma dei reciproci”

L’incremento ++i modifica il valore di verità del test,l’azione svolta dal corpo, ed è cruciale per il buon funzionamento del ciclo. Se lo eliminiamo e lasciamo:

while (i <= n) {s = s + 1.0/i;}

allora, mentre ripetiamo il corpo {s = s + 1.0/i;} del ciclo while, il valore di i non cambia. Resta il valore iniziale i=1.

Dunque continuiamo a eseguire s=s+1.0/i con i=1: quindi continuiamo a eseguire s = s + 1; ne segue che s assume i valori 0,1,2,3,4, …, anziche’ 1,1+1/2, … come dovrebbe.

Inoltre il test (i <= n) resta uguale a (1 <= n) e quindi vale sempre true, il ciclo continua per sempre.

Un altro esempio di iterazione:

il ciclo forfor ([<inizializzazione>]; [<test>]; [<step>]) <corpo>• Le inizializzazioni sono definizioni di variabili o

assegnazioni di valori a variabili precedentemente dichiarate; se più d’una, sono separate da virgole (e non da punti e virgole come al solito)• Lo step o incremento di solito è l’incremento di una o più variabili; se più d’una, sono separate da virgole. L’incremento serve a modificare il valore di verità del test e, a volte, l’azione svolta dal corpo.• Nota. A differenza di quanto avviene per il for nel Pascal, il test è un’espressione booleana arbitraria.

4-Diagrammi

Il diagramma di flusso per il ciclo for

for (I; B; S)

C;I

B

C

S

true

false

L’inizializza-zione I viene eseguita una

sola volta prima di

entrare nel ciclo

Lo step S viene eseguito al termine di ogni esecuzione

del corpo C

Al termine di S avviene sempre un salto all’indietro, verso l’istruzione che prima calcola B, poi a seconda del valore di B sceglie se ripetere il corpo del for o saltare alla prima istruzione dopo il for

La relazione tra while e for• A differenza di quanto succede in altri linguaggi, in C++

il ciclo while ed il ciclo for sono interdefinibili, usando le seguenti equazioni:

for(I;B;S) C; = {I; while(B){C;S;}}while(B) C; = for(;B;) C;

• Ne segue che la differenza tra i due cicli è solo di stile: di solito il for è più chiaro, perché mette in evidenza la parte di inizializzazione e incremento.

• Come capita per il while, il for non termina mai se il test B resta sempre vero.

• Vediamo ora come usare il for per ripetere n volte la stessa azione.

4-Diagrammi

Il for consente di ripetere n volte una certa azione

for(i=0,n=100;i<n;++i)

cout << “CIAO”;i = 0 n = 100

i<n

Scrivi “CIAO”

++i

true false

Inizialmente i vale 0

Al termine di ogni

iterazione i viene

incrementato di 1

Il ciclo viene eseguito 100 volte, mentre i cresce da 0 a 99. Ogni volta stampiamo un “CIAO”.

Quando i vale 100 il ciclo termina

Un diagramma per il calcolo della media aritmetica m = (a0 + … an-1)/

ninizio

leggi n

i = 0

i < n

s = 0

leggi a

s = s + a

stampa m = s/n

fine

i = i + 1

true

false

a = i-esimoaddendo ai

A partire da questo diagramma di flusso si puó scrivere un programma in C++ usando un ciclo FOR

Il diagramma di flusso per la media (definito da un

for)

for (I; B; S)

C; i = 0 s = 0

i<n

Leggi a s = s + a

++i

true false

Eseguito una sola

volta prima di entrare nel ciclo

Eseguito al termine di ogni

iterazione4-Diagrammi

Un programma C++ per la media aritmeticaint main(){int n; int i, a, s;

cout << "Media di n valori. n="; cin >> n;

for (i = 0, s = 0; i < n; i++)

{ cout << "inserisci un valore=";

cin >> a;

s = s + a;}

cout << "Media = " << (double) s / (double) n

<< endl; system("pause");}

“Casting” necessario per avere la divisione senza troncamento

++i è detto incremento. Se lo eliminiamo cosa succede ???

4-Diagrammi

Il ruolo di ++i nella “media aritmetica”

L’incremento ++i serve a modificare il valore di verità del test, ed è cruciale per il buon funzionamento del ciclo. Se lo eliminiamo e lasciamo:

for (i = 0, s = 0; i < n; )

{cout << "inserisci un valore=";

cin >> a; s = s + a;}

allora mentre il corpo del ciclo for viene ripetuto il valore di i non cambia, resta il valore iniziale i=0.

Dunque il test (i < n) resta uguale (0 < n) e quindi vale true. Il ciclo for continua per sempre. In generale, se dimentico di inserire gli incrementi il ciclo (for o while) non termina.

4-Diagrammi

Un ciclo meno usato: l’istruzione do…while

do

C;

while (B);

do <comando>; while

(<espr. booleana>);

B

C

true false

La differenza con il while è che il corpo del do while viene eseguito almeno una volta

Vi chiediamo di saper riconoscere questa istruzione, ma vi consigliamo di usare solo while e for. Il Pascal ha una istruzione simile: do … until, che esce però quando il test è vero.

4-Diagrammi

Esempio: stampa dei fattoriali inferiori a un certo

limiteint main(){ long limite;

cout << "Inserire una limitazione superiore: ";

cin >> limite;

cout << "Elenco fattoriali minori di " << limite << endl;

long f = 1, i = 0; /* f=1=0!=i! Faremo sì che la condizione f=i! resti vera durante tutta l’esecuzione del ciclo

(continua nel prossimo lucido)

*/ 4-Diagrammi

Esempio: stampa dei fattoriali inferiori a un certo

limite/* (continua dal lucido precedente) */

do {cout << i <<"! = " << f << endl; //stampo i! = f

f = f * (i+1); //ora f vale: f*(i+1)=i!*(i+1)=(i+1)!

i++; /*aggiorno i ad (i+1), di modo che per la nuova i (uguale alla vecchia i+1) valga la condizione f=i!.*/ }

while (f < limite);

system("pause");}

++i è detto incremento. Provate a eliminarlo e vedrete che, anche in questo caso, il ciclo continua per sempre 4-Diagrammi

4. Programmazione strutturata

• Un’istruzione di “jump” (salto) è ad esempio:JB <etichetta>

dove l’etichetta indica il punto del programma a cui saltare. JB è un’istruzione tipica del linguaggio Assembly, come abbiamo visto parlando della macchina di Von Neumann. In C++ l’istruzione JB esiste e si scrive goto.

• La programmazione strutturata, tuttavia, proibisce l’uso delle istruzioni di salto anche se disponibili, e si basa soltanto su sequenza (blocchi), selezione (IF) ed iterazione (WHILE, FOR, ecc.) per controllare il flusso del programma.

Programmazione strutturata

• L’esperienza mostra che si parte da un diagramma non strutturato (cioè non combinazione di diagrammi per if e while) è difficile trasformarlo in un programma strutturato equivalente.

• Ma almeno in linea di principio, è sempre possibile trasformare un diagramma qualunque in uno equivalente, che pero’ corrisponda a un programma strutturato, cioè scritto con solo if e while? La risposta è

si’ per il Teorema di Böhm-Jacopini del 1966• In altre parole: if e while sono in linea di principio

sufficienti a scrivere qualunque programma.

4-Diagrammi

Teorema di Böhm-JacopiniOgni funzione Turing calcolabile è definibile in un linguaggio di programmazione con i comandi di:

Blocco di istruzioni, IF e WHILE

Ogni funzione Turing calcolabile è definibile in un linguaggio di programmazione con i comandi di:

Blocco di istruzioni, IF e WHILE

Ma cosa sono le funzioni Turing calcolabili? Per mostrare l’idea della prova senza definire le funzioni Turing-calcolabili, assumiamo che tutti gli algoritmi si possano descrivere con diagrammi di flusso, e mostriamo come un diagramma qualsiasi si possa tradurre in un programma strutturato con solo blocchi, if, while.

Cenno di prova: partiamo da un

diagramma qualunque …

B1

C1 C2

C5

C3B3B2

C4

+

++

-

--

1

3 24

5 67

8 9

10

… e ad ogni nodo del “grafo” associamo un numero

4-Diagrammi

Dopo aver numerato i nodi …

4-Diagrammi

… usiamo una variabile contatore cp per sapere in

quale nodo ci troviamo e per

decidere verso quale nodo proseguire. A

questo punto …

B1

C1 C2

C5

C3B3B2

C4

+

++

-

--

1

3 24

5 67

8 9

10

main(){int cp = 1;//cp=nodo del diagramma in cui ci troviamowhile (cp < 10) { if (cp == 1) cp = 2; else if (cp == 2) {if (B1) cp = 3; else cp = 4;} else if (cp == 3) {C1; cp = 5;} else if (cp == 4) {C2; cp = 6;} else if (cp == 5) {if (B2) cp = 8; else cp = 4;} else if (cp == 6) {if (B3) cp = 9; else cp = 7;} else if (cp == 7) {C3; cp = 2;} else if (cp == 8) {C4; cp = 3;} else if (cp == 9) {C5; cp = 10}}}

… traduciamo il nostro diagramma con un ciclo while

e tanti if:

4-Diagrammi

B1

C1 C2

C5

C3B3B2

C4

+

++

-

--

1

3 24

5 67

8 9

10

Conclusioni

• In base al Teorema di Böhm-Jacopini, per il controllo del flusso sono sufficienti i costrutti programmativi della programmazione strutturata (blocchi, if, while, senza l’istruzione goto).

• Attenzione però: la dimostrazione del teorema di Böhm-Jacopini non ci dà alcuna informazione su come trasformare un diagramma caotico in un programma strutturato leggibile.

• Per questo motivo non useremo i diagrammi di flusso, ma scriveremo direttamente il codice in forma strutturata, con if, while, for, ….

4-Diagrammi

Istruzioni di cui sconsigliamo l’uso

Il C/C++ comprende, oltre al goto, altre istruzioni di salto che erano tipiche dei più antichi linguaggi Assembly. Noi però non ne faremo uso, perche’ i “salti” producono facilmente errori e programmi poco leggibili. Solo per completezza, elenchiamo qui le istruzioni di salto del C++:• goto• break• continue• exit.Un’altra istruzione che sconsigliamo è lo SWITCH.

Vedi esempi 4.16 e 4.19 dell’Hubbard