G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
I Diagrammi di Flusso
Soluzione agli esercizi
proposti
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
1
G. Amodeo,
C. Gaibisso
I più semplici
Calcolare il
massimo di una
sequenza non
vuota di numeri
interi positivi
terminata da un
intero negativo
Start
Nome: MaxOfSeq
Variabili: int val, max
max  -1
val
Descrizione variabili:
val:
max:
memorizza il
valore
corrente della
sequenza
memorizza il
massimo
corrente
true
val < 0
max
End
false
false
val > max
true
max  val
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
2
G. Amodeo,
C. Gaibisso
I più semplici
Acquisire due
valori interi in
due variabili e
scambiarne il
contenuto
Start
Nome: Scambia
Variabili: int A, B, aux
A, B
Descrizione variabili:
A:
B:
aux:
memorizza il
primo valore
intero
memorizza il
secondo valore
intero
variabile di
appoggio
aux  A
A B
B  aux
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
3
G. Amodeo,
C. Gaibisso
I più semplici
Start
Nome: MCM
Variabili: int A, B, max, mcm, count
A, B
Descrizione variabili:
memorizza il
primo intero
B:
memorizza il
secondo intero
max: memorizza il
massimo tra i
due interi
mcm: memorizza il
candidato
corrente a
minimo comune
multiplo
count: moltiplicato per
max genera il
prossimo
candidato a
minimo comune
multiplo
count  2
A:
max  A
max  B
A>B
true
false
mcm  max
mcm  max*count
cont  count+1
false
Calcolare il
minimo comune
multiplo tra 2
interi positivi
mcm % A = 0
and
mcm % B = 0
true
mcm
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
4
G. Amodeo,
C. Gaibisso
I più semplici
Start
Nome: MCM
Variabili: int A, B, mcm
Calcolare il
minimo comune
multiplo tra 2
interi positivi
A, B
mcm  A
Descrizione variabili:
A:
memorizza il
primo intero
B:
memorizza il
secondo intero
mcm: memorizza il
candidato
corrente a
minimo comune
multiplo
mcm  mcm+1
mcm % A = 0
and
mcm % B = 0
mcm
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
5
G. Amodeo,
C. Gaibisso
I più semplici
Start
Nome: MCD
Variabili: int A, B, min, mcd, count
Calcolare il
massimo comun
divisore tra 2
interi positivi
A, B
mcd  1
count  1
Descrizione variabili:
A:
memorizza il
primo intero
B:
memorizza il
secondo intero
min: memorizza il
minimo tra i
due interi
count: memorizza il
candidato
corrente a
massimo comun
divisore
mcd: memorizza
l’ultimo divisore
comune
individuato
false
true
min  A
min  B
A>B
count > min
true
mcd
false
End
count  count+1
false
A % count = 0
and
B % count = 0
true
mcd  count
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
6
G. Amodeo,
C. Gaibisso
Vettori
Dato un vettore
di N ≥ 1 interi,
restituirne il
contenuto
Start
Nome:
ResVett
Variabili: int curs,
int vett[N]
Descrizione variabili:
curs:
indice per la
scansione del
vettore
vett[ ]: vettore
interessato dal
processamento
curs  0
curs curs+1
curs< N
false
End
true
vett[curs]
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
7
G. Amodeo,
C. Gaibisso
Vettori
Dato un vettore
di N ≥ 1 interi,
determinarne il
massimo
elemento
Start
Nome:
MaxVett
Variabili: int curs, max
int vett[N]
curs  0
max  vett[0]
Descrizione variabili:
curs:
indice per la
curs  curs+1
scansione del
vettore
vett[ ]: vettore
interessato dal
false
processamento
max: massimo
valore
individuato fino
alla posizione
curs
curs < N
false
max
End
true
vett[curs] > max
true
max  vett[curs]
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
8
G. Amodeo,
C. Gaibisso
Vettori
Dato un vettore di N ≥
1 interi, determinarne il
massimo elemento e la
sua posizione
Start
Nome:
MaxPosVett
Variabili: int curs, max, pos
int vett[N]
curs  0
max  vett[0]
pos  0
Descrizione variabili:
curs:
indice per la
scansione del
vettore
vett[ ]: vettore
interessato dal
processamento
max: massimo
valore
individuato fino
alla posizione
curs
pos:
posizione del
valore
memorizzato
in max
End
curs  curs+1
curs < N
false
max, pos
true
false
vett[curs] > max
true
max  vett[curs]
pos  curs
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
9
G. Amodeo,
C. Gaibisso
Vettori
Start
Nome:
PosCarVett
Variabili: int curs, car, pos
char vett[N]
Verificare la presenza
di un carattere
all’interno di un
vettore di N ≥ 1
caratteri e la sua
eventuale posizione
curs  0
pos = -1
Descrizione variabili:
car
curs:
indice per la
scansione del
vettore
vett[ ]: vettore
interessato dal
processamento
car:
memorizza il
carattere di cui
verificare la
presenza
pos:
memorizza la
posizione di car
se presente, -1
altrimenti
End
curs  curs+1
false
curs < N
pos
true
false
vett[curs] = car
true
pos  curs
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
10
G. Amodeo,
C. Gaibisso
Vettori
• Algoritmo:
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Selection Sort
per ogni posizione P degli elementi del
vettore, ad esclusione dell’ultima:
1. determinare il valore minimo nel
vettore a partire dalla posizione P
inclusa. Sia Q la posizione di tale
valore minimo
2. scambiare il valore nella posizione
P con quello nella posizione Q
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
11
G. Amodeo,
C. Gaibisso
Vettori
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Selection Sort
• Sottoproblemi:
1. determinare la posizione del
valore minimo nel vettore a
partire da una posizione data
2. scambiare i valori di due variabili
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
12
G. Amodeo,
C. Gaibisso
Vettori
Determinare la
posizione del valore
minimo nel vettore
a partire da una
posizione data
Descrizione variabili:
indice per la
scansione del vettore
vett[ ]: vettore interessato
dal processamento
start: posizione dalla quale
ha inizio il
processamento
max: massimo valore
individuato fino dalla
posizione start alla
posizione curs
pos:
posizione del valore
memorizzato in max
Start
Nome:
PosMinVett
Variabili: int curs, pos, start
int vett[N]
curs  start
min = vett[start]
pos  start
curs:
End
curs  curs+1
false
true
curs = N
pos
false
vett[curs] < min
true
pos  curs
min  vett[curs]
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
13
G. Amodeo,
C. Gaibisso
Vettori
scambiare i valori
di due variabili
Descrizione variabili:
A:
B:
aux:
memorizza il
primo valore
intero
memorizza il
secondo valore
intero
variabile di
appoggio
Start
Nome: Scambia
Variabili: int A, B, aux
aux  A
A B
B  aux
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
14
G. Amodeo,
C. Gaibisso
Vettori
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Selection Sort
Start
Nome:
Selection Sort
Variabili: int curs, pos
int vett[N]
curs  0
curs = N-1
Descrizione variabili:
indice per la
scansione del
vettore
vett[ ]: vettore
interessato dal
processamento
pos:
posizione del
minimo
elemento del
vettore a
partire dalla
posizione curs
true
End
false
curs:
curs  curs+1
Applica PosMinVett a
vett[ ] a partire dalla
posizione curs e lascia il
risultato in pos
Applica scambia a
vett[curs] e vett[pos]
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
15
G. Amodeo,
C. Gaibisso
Vettori
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Bubble Sort
• Algoritmo:
1. scandire l’intero vettore confrontando
elementi adiacenti e scambiando i loro
valori se necessario
2. ripetere tale scansione fino al completo
ordinamento del vettore, cioè finchè la
scansione richiede almeno uno scambio
di valori
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
16
G. Amodeo,
C. Gaibisso
Vettori
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Bubble Sort
• Sottoproblemi:
1. scambiare i valori di due variabili
2. scandire il vettore confrontando
elementi adiacenti e scambiando i
loro valori se necessario
3. verificare se nella scansione si è
verificato almeno uno scambio di
valori
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
17
G. Amodeo,
C. Gaibisso
Vettori
Scambiare i
valori di due
variabili
Descrizione variabili:
A:
B:
aux:
memorizza il
primo valore
intero
memorizza il
secondo valore
intero
variabile di
appoggio
Start
Nome: Scambia
Variabili: int A, B, aux
aux  A
A B
B  aux
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
18
G. Amodeo,
C. Gaibisso
Vettori
Confrontare elementi adiacenti
scambiando i loro valori se
necessario, verificando nel
contempo verificato almeno uno
scambio di valori
Descrizione variabili:
indice per la
scansione del
vettore
vett[ ]: vettore
interessato dal
processamento
flag:
indica
l’avvenuto
scambio di
almeno una
coppia di valori
Start
Nome:
BubbleStep
Variabili: int curs, flag
int vett[N]
curs  0
flag  false
End
curs = N-1
flag
curs:
curs  curs+1
true
false
false
vett[curs] > vett[curs+1]
flag  true
true
Applica scambia a vett[curs]
e vett[curs+1]
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
19
G. Amodeo,
C. Gaibisso
Vettori
Ordinare, in ordine
crescente, un
vettore di N ≥ 1
interi:
Bubble Sort
Start
Nome:
BubbleSort
Variabili: int vett[N]
true
Applica
BubbleStep
a vett[ ]
Descrizione variabili:
vett[ ]: vettore interessato
dal processamento
false
End
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
20
G. Amodeo,
C. Gaibisso
Matrici
Data una matrice P x
Q interi, P ≥ 1, Q ≥ 1,
restituirne il
contenuto (per righe)
Start
Nome:
ResMat
Variabili: int riga, col
int mat[P][Q]
riga  0
col  0
false
Descrizione variabili:
indice per la
scansione delle
righe della matrice
col:
indice per la
scansione delle
colonne della
matrice
mat[ ][ ]: matrice
interessata dal
processamento
riga < P
riga:
End
true
riga  riga+1 false
col  0
col < Q
true
mat[riga][col]
col  col+1
Programmazione di Calcolatori: I diagrammi di flusso
21
G. Amodeo,
C. Gaibisso
Matrici
Start
Nome:
AcqMat
Variabili: int riga, col
int mat[P][Q]
Data una matrice P x Q
interi, P ≥ 1, Q ≥ 1,
restituirne il contenuto
(per colonne)
riga  0
col  0
Descrizione variabili:
indice per la
scansione delle
righe della matrice
col:
indice per la
scansione delle
colonne della
matrice
mat[ ][ ]: matrice
interessata dal
processamento
col < Q
riga:
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
22
G. Amodeo,
C. Gaibisso
Matrici
Data una matrice quadrata di
P x P interi, P ≥ 1,
determinarne il massimo
elemento sulla diagonale
principale e la sua posizione
Descrizione variabili:
curs:
indice per la
scansione della
diagonale
principale
curs  curs+1
mat[ ][ ]: matrice
interessata dal
processamento
max:
massimo valore
false
individuato fino
alla posizione
[curs][curs]
pos:
posizione del
valore
memorizzato
in max
Start
Nome:
MaxPosMat
Variabili: int curs, max, pos
int mat[P][P]
curs  0
max  mat[0][0]
pos  0
End
curs < P
false
max, pos
true
mat[curs][curs] > max
true
max  mat[curs][curs]
pos  curs
Programmazione di Calcolatori: I diagrammi di flusso - soluzione agli esercizi
23
G. Amodeo,
C. Gaibisso
Matrici
Contare le occorrenze di
un intero in una matrice
di P x Q interi, P ≥ 1, Q ≥ 1
Start
Nome:
AcqMat
Variabili: int riga, col, val, count
int mat[P][Q]
val
Descrizione variabili:
riga:
indice per la
scansione delle
righe della matrice
col:
indice per la
scansione delle
colonne della
matrice
val:
memorizza il valore
oggetto della
ricerca
count:
memorizza il
numero di
occorrenze del
valore
mat[ ][ ]: matrice interessata
dal processamento
riga  0
col  col+1
riga  0
col  0
count  0
col < Q
false
true
false
End
riga  riga+1
riga < P
true
false
mat[riga][col] = val
true
count  count+1
Programmazione di Calcolatori: I diagrammi di flusso
24