G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione V
I Diagrammi di Flusso
Programmazione di Calcolatori: I diagrammi di flusso
1
G. Amodeo,
C. Gaibisso
Nozione intuitiva di algoritmo
• Nozione intuitiva di algoritmo
• è una sequenza finita di istruzioni
• ogni istruzione è costruita a partire da un
alfabeto di dimensione finita
• ogni istruzione nella sequenza è codificata
con una quantità finita di informazione
• deve esistere un agente di calcolo C capace
di eseguire le istruzioni dell’algoritmo
• C deve avere capacità di memorizzazione
• …..
Programmazione di Calcolatori: I diagrammi di flusso
2
G. Amodeo,
C. Gaibisso
I diagrammi di flusso
• Diagrammi di Flusso:
• un formalismo grafico per la descrizione
di algoritmi
• un particolare simbolo grafico detto
blocco è associato ad ogni tipo di
istruzione elementare
• i blocchi sono collegati tra loro da archi
che definiscono l’ordine di esecuzione
delle istruzioni
Programmazione di Calcolatori: I diagrammi di flusso
3
G. Amodeo,
C. Gaibisso
Esempio
• Calcolare la somma dei numeri 1 i  N
Start
Nome:
SommaN
Variabili: int
N, cont, somma
Acquisizione del numero di
valori da sommare
Aggiornamento della somma
parziale e del contatore
Inizio della
sequenza
Inizializzazione della
somma parziale e del
contatore
N
somma  0
cont  0
Restituzione del valore
calcolato
cont  cont+1
somma  somma+cont
true
cont < N
Verifica sul numero di
somme effettuate
false
somma
End
Termine della
sequenza
Programmazione di Calcolatori: I diagrammi di flusso
4
G. Amodeo,
C. Gaibisso
Capacità di memorizzazione
• Modello:
descrizione della realtà limitatamente agli aspetti di
interesse
• Modello di memoria:
• insieme di locazioni
• ogni locazione può memorizzare un
valore di tipo intero, carattere, o
booleano
• una locazione o è correntemente in
uso o è disponibile

intero
A

carattere
B
‘c’

boleano
in uso
disponibile
3
C
true
• locazioni correntemente in uso sono
dette variabili
• ogni variabile è identificata da un
nome e da un tipo
Programmazione di Calcolatori: I diagrammi di flusso

5
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Molto informalmente:
è una “foto” istantanea della memoria
• E’ determinato:
a) dal numero delle variabili
b) dal loro nome, tipo e valore
Programmazione di Calcolatori: I diagrammi di flusso
6
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
SI
D
2

D
2

A
‘c’

A
‘c’

B
120

B
120

C
‘d’

C
‘d’

Stato1
Stato2
Programmazione di Calcolatori: I diagrammi di flusso
7
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
NO
D
2

D
2

A
‘c’

A
‘c’

B
120

C
‘d’

C
‘d’
Stato1

Stato2
Programmazione di Calcolatori: I diagrammi di flusso
8
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
NO
D
2

D
8

A
‘c’

A
12

B
120

B
‘m’

C
‘d’

C
‘d’

Stato1
Stato2
Programmazione di Calcolatori: I diagrammi di flusso
9
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
NO
D
8

D
8

A
12

A
12

C
‘m’

E
‘m’

E
‘d’

C
‘d’

Stato1
Stato2
Programmazione di Calcolatori: I diagrammi di flusso
10
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
SI
A

A

B

B

C

C

D

D

Stato1
Stato2
Programmazione di Calcolatori: I diagrammi di flusso
11
G. Amodeo,
C. Gaibisso
Stato della Memoria
• Stato1 = Stato2 ?
SI
D
8

A
12

A
12

D
8

B
true

B
true

C
‘d’

C
‘d’

Stato1
Stato2
Programmazione di Calcolatori: I diagrammi di flusso
12
G. Amodeo,
C. Gaibisso
Tipologia dei blocchi
• Blocchi di inizio e di termine
Nome del
diagramma
Definizione delle
variabili utilizzate
Start
Nome:
SommaN
Variabili: int
N, somma, cont
Tipo delle variabili
N
intero:
-2, -1, 0, 1, 2 ….
carattere: ‘c’, ‘2’, ‘!’ …
booleano: true, false
cont  cont+1
somma  somma+cont
Inizio del
diagramma
1
Nome delle variabili
somma  0
cont  0
true
+ di 1
cont < N
false
Termine della
sequenza
somma
End
Programmazione di Calcolatori: I diagrammi di flusso
13
G. Amodeo,
C. Gaibisso
Definizione di una variabile
• Blocco di inizio
Per ognuna delle variabili elencate nel blocco
1. si individua una locazione di memoria disponibile
2. si riserva tale locazione
3. si associano a tale locazione il nome e il tipo specificati
A
B
2
120
StatoI


A
Start
Nome: SommaN
Variabili: int
N,
somma,
cont
intero
2

N
B

120

StatoF
Programmazione di Calcolatori: I diagrammi di flusso
14
G. Amodeo,
C. Gaibisso
Tipologia dei blocchi
• Blocco di termine:
si rilascia la memoria allocata ad ognuna delle
variabili elencate nel blocco “Start”
cont
4

cont
4

N
4

N
4

somma
10

somma
10
StatoI

End
StatoF
Programmazione di Calcolatori: I diagrammi di flusso
15
G. Amodeo,
C. Gaibisso
Tipologia dei blocchi
• Blocchi di acquisizione e di restituzione dati
Start
Nome:
SommaN
Variabili: int
N, somma, cont
Il dato acquisito è
memorizzato nella variabile N
N
Blocco di acquisizione
somma  0
cont  0
cont  cont+1
somma  somma+cont
true
cont < N
Restituisce il contenuto della
variabile somma
false
somma
Blocco di
restituzione
End
Programmazione di Calcolatori: I diagrammi di flusso
16
G. Amodeo,
C. Gaibisso
Tipologia dei blocchi
• Blocco di elaborazione
Start
Nome:
SommaN
Variabili: int
N, cont, somma
Formato di un’operazione di
assegnamento:
nome  espressione
N
Blocco di elaborazione
cont  cont+1
somma  somma+cont
true
Blocco di elaborazione
somma  0
cont  0
cont < N
Contiene una sequenza
di operazioni di
assegnamento
false
Le operazioni di
assegnamento vengono
considerate nell’ordine in cui
compaiono nel blocco
dall’alto verso il basso
somma
End
Programmazione di Calcolatori: I diagrammi di flusso
17
G. Amodeo,
C. Gaibisso
Operazioni di assegnamento
• nome  espressione
1.
Si valuta il valore di espressione
2.
Si aggiorna con tale valore il contenuto della variabile
identificata da nome

somma
3
N
3

cont
0

StatoI
1
cont  cont+1
somma  somma+cont
4
somma
0
4

N
3

cont
01

StatoF
Programmazione di Calcolatori: I diagrammi di flusso
18
G. Amodeo,
C. Gaibisso
Tipologia dei blocchi
• Blocco di decisione
Start
Nome:
SommaN
Variabili: int
N, cont, somma
N
somma  0
cont  0
cont  cont+1
somma  somma+cont
true
cont < N
Blocco di decisione
Confronta due o più espressioni
secondo diverse modalità
Sulla base del risultato del
confronto individua il prossimo
blocco del flusso
false
somma
End
Programmazione di Calcolatori: I diagrammi di flusso
19
G. Amodeo,
C. Gaibisso
Riassumendo ….
• Blocco di inizio
int
bool
char
Start
Nome:
Variabili:
• Blocco di termine
nome del diagramma
tipo1 nome1
tipo2 nome2
……
End
• Blocco di acquisizione
nome1, nome2, …
• Blocco di restituzione
nome1, nome2, …
• Blocco di elaborazione
nome1  espressione1
nome2  espressione2
……
Programmazione di Calcolatori: I diagrammi di flusso
20
G. Amodeo,
C. Gaibisso
Riassumendo ….
• Blocco di decisione
true
espressione a
valore booleano
Programmazione di Calcolatori: I diagrammi di flusso
false
21
G. Amodeo,
C. Gaibisso
Operatori ….
• Operatori aritmetici
 + : int x int  int
somma tra interi
 - : int x int  int
differenza tra interi
 * : int x int  int
prodotto tra interi
 / : int x int  int
divisione intera
 % : int x int  int
intera
resto della divisione
• Operatori logici
 not : bool  bool
negazione
 and : bool x bool  bool
and logico
 or : bool x bool  bool
or logico
Programmazione di Calcolatori: I diagrammi di flusso
22
G. Amodeo,
C. Gaibisso
Operatori ….
• Operatori di confronto tra interi
 = : int x int  bool
test di uguaglianza
 > : int x int  bool
strettamente maggiore
 ≥ : int x int  bool
maggiore o uguale
 < : int x int  bool
strettamente minore
 ≤ : int x int  bool
minore uguale
Programmazione di Calcolatori: I diagrammi di flusso
23
Ordinamento lessicografico
Tabella dei codici ASCII
G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori: I diagrammi di flusso
24
G. Amodeo,
C. Gaibisso
Operatori ….
• Operatori di confronto tra caratteri
 = : char x char bool
test di uguaglianza
 < : char x char  bool
precede lessicograficamente
 ≤ : char x char  bool uguale o precede
lessicograficamente
 > : char x char  bool
segue lessicograficamente
 ≥ : char x char  bool uguale o segue
lessicograficamente
Programmazione di Calcolatori: I diagrammi di flusso
25
G. Amodeo,
C. Gaibisso
Condizioni di validità
• Esiste un solo blocco di inizio ed ha un solo arco uscente;
• esistono uno o più blocchi di termine
• ciascun blocco di elaborazione, di acquisizione, di
restituzione ha un solo arco entrante e un solo arco
uscente;
• ciascun blocco di decisione ha un solo arco entrante e
due uscenti;
• ciascun arco entra in un blocco o si innesta su un altro
arco;
• ciascun blocco è raggiungibile dal blocco iniziale;
• da qualsiasi blocco è possibile raggiungere almeno uno
dei blocchi di termine.
Programmazione di Calcolatori: I diagrammi di flusso
26
G. Amodeo,
C. Gaibisso
Un semplice esempio
Calcolare il
massimo di una
sequenza di N≥1
numeri interi
Start
Nome:
MaxTraN
Variabili: int N, count, max, val
int count
N, val
max  val
count  1
count = N
true
max
false
false
max val
true
val > max
count  count+1
End
val
Programmazione di Calcolatori: I diagrammi di flusso
27
G. Amodeo,
C. Gaibisso
Vettori
• Vettore (monodimensionale) di n elementi:
definisce una corrispondenza biunivoca tra un insieme
omogeneo di n elementi e l’insieme di interi {0, 1, …,
n-1}
• Esempio:
Vettore di 5 interi
• Definizione
0
1
5
-1
2
32
3
-4
4
27
costante intera
tipoVettore nomeVettore [dimVettore]
Programmazione di Calcolatori: I diagrammi di flusso
28
G. Amodeo,
C. Gaibisso
Vettori
• Effetto
A

2
A
2
Start
…
Variabili: int Vett[3]



intero
B

120

B
StatoI
120
Vett[0]
Vett[1]
Vett[2]

StatoF
• Accesso all’elemento di un vettore
0  espressione a valore intero  dimVettore-1
nomeVettore [indice]
Programmazione di Calcolatori: I diagrammi di flusso
29
G. Amodeo,
C. Gaibisso
Vettori
• Esempio
Start
Nome:
AcqVett
Variabili: int index,
int vett[K]
Acquisizione del
contenuto di un
vettore di K interi
index  0
index  index+1
index < K
false
End
true
vett[index]
Programmazione di Calcolatori: I diagrammi di flusso
30
G. Amodeo,
C. Gaibisso
Matrici
• Matrice di n x m elementi:
definisce una corrispondenza biunivoca tra un insieme
omogeneo di n x m elementi e l’insieme di coppie di
interi {(0,0), (0,1), …., (n-1, m-1)}
• Esempio:
Matricedi 5 x 2 interi
• Definizione
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
8
7
15
4
7
4
-1
12
-9
4
(0,1)
(1,1)
(2,1)
(3,1)
(4,1)
costanti intere
tipoMatrice nomeMatrice [dimRighe] [dimColonne]
Programmazione di Calcolatori: I diagrammi di flusso
31
G. Amodeo,
C. Gaibisso
Matrici
• Accesso all’elemento di una matrice
0  espressione a valore intero  dimColonne-1
nomeMatrice [indiceRiga][indiceColonna]
0  espressione a valore intero  dimRighe-1
Programmazione di Calcolatori: I diagrammi di flusso
32
G. Amodeo,
C. Gaibisso
Matrici
• Esempio
Start
Nome:
AcqMatRighe
Variabili: int riga, col
int mat[P][Q]
Acquisizione del
contenuto di una
matrice di
P x Q interi (per
righe)
riga  0
col  0
riga < P
false
End
true
riga  riga+1 false
col  0
col < Q
true
mat[riga][col]
col  col+1
Programmazione di Calcolatori: I diagrammi di flusso
33
G. Amodeo,
C. Gaibisso
Matrici
Start
Nome:
AcqMatCol
Variabili: int riga, col
int mat[P][Q]
• Esempio
riga  0
col  0
Acquisizione del
contenuto di una
matrice di
P x Q interi (per
colonne)
col < Q
false
End
true
riga  0
col  col+1
false
riga < P
true
mat[riga][col]
riga  riga+1
Programmazione di Calcolatori: I diagrammi di flusso
34
G. Amodeo,
C. Gaibisso
Matrici
Start
Nome:
AcqMat
Variabili: int riga, col, max
int mat[P][Q]
• Esempio
riga  0
col  0
max  mat[0][0]
col < Q
false
End
true
riga  0
col  col+1
false
riga < P
true
mat[riga][col] > max
Restituzione del
massimo
elemento di una
matrice di P x Q
interi, P ≥ 1, Q ≥ 1
false
riga  riga+1
true
max  mat[riga][col]
Programmazione di Calcolatori: I diagrammi di flusso
35
Scarica

c - Informatica