G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
I vettori
Soluzione agli esercizi
proposti
Programmazione di Calcolatori: i vettori - soluzione agli esercizi
1
G. Amodeo,
C. Gaibisso
Esercizio 1: diagramma di flusso
Determinare il
massimo elemento di
un vettore di N interi
Start
Nome:
MaxOfVettInt
Variabili: int curs, max
int vett[N]
curs  0
max  vett[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 < N
curs  curs+1
false
max
true
false
vett[curs] > max
true
max  vett[curs]
Soluzione in: EsProposti\Lezione_XIV\Esercizio_1.c
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
2
G. Amodeo,
C. Gaibisso
Esercizio 1: il codice
// sorgente: EsProposti\Lezione_XIV\Esercizio_1.c
// direttive per il preprocessore
#include <stdio.h>
// definisce la dimensione del vettore
#define N 5
// funzione per l'acquisizione del contenuto di
// un vettore di interi
void AcqVettInt(int Vett[], int dim)
{
// definisce la variabile per la scansione del vettore
int pos;
// scandisce il vettore, acquisendone il contenuto
for (pos = 0; pos < dim; pos++)
{
printf("\nVett[%d]? ", pos);
scanf("%d", &Vett[pos]);
};
};
// funzione che determina il massimo elemento di un vettore di N interi
int MaxofVettInt(int *vett, int dim)
{
// definisce la variabile per la scansione del vettore e per il massimo
// corrente
int curs;
int max;
// inizializza la variabile per il massimo corrente
max = vett[0];
continua …
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
3
G. Amodeo,
C. Gaibisso
Esercizio 1: il codice
continua …
// scandisce il vettore
for (curs = 0; curs < dim; curs++)
// aggiorna, se necessario, il massimo corrente
if (vett[curs] > max)
max = vett[curs];
// restituisce il massimo elemento
return(max);
};
// chiamante
int main ()
{
// definisce il vettore
int vettore[N];
// inizializza il contenuto del vettore
AcqVettInt(vettore, N);
// visualizza il massimo elemento del vettore
printf("\nIl massimo elemento e': %d", \
MaxofVettInt(vettore, N));
return(1);
}
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
4
G. Amodeo,
C. Gaibisso
Esercizio 2: diagramma di flusso
Restituire la posizione di un valore
all’interno di un vettore di N
interi, se presente, -1 altrimenti
Descrizione variabili:
indice per la
scansione del
vettore
Vett[ ]: vettore
interessato dal
processamento
val:
memorizza il
valore di cui
verificare la
presenza
Start
Nome:
PosValVett
Variabili: int curs, val
int Vett[N]
curs  0
curs:
End
val
curs
false
curs  curs+1
false
curs < N
curs  -1
true
Vett[curs] = val
true
Soluzione in: EsProposti\Lezione_XIV\Esercizio_2.c
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
5
G. Amodeo,
C. Gaibisso
Esercizio 2: il codice
// sorgente: EsProposti\Lezione_XIV\Esercizio_2.c
// direttive per il preprocessore
#include <stdio.h>
// definizione della dimensione del vettore
#define N 6
// funzione per l'acquisizione del contenuto di un vettore di interi
void AcqVettInt(int Vett[], int dim)
{
// definisce la variabile per la scansione del vettore
int pos;
// scandisce il vettore, acquisendone il contenuto
for (pos = 0; pos < dim; pos++)
{
printf("\nVett[%d]? ", pos);
scanf("%d", &Vett[pos]);
};
};
// funzione che verificare la presenza di un valore all’interno di un vettore di N
// interi e se presente restituisce la sua posizione, -1 altrimenti
int PosValVett(int val, int *Vett, int dim)
{
// definizione della variabile per la scansione del vettore
int curs;
continua …
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
6
G. Amodeo,
C. Gaibisso
Esercizio 2: il codice
continua …
// scansione del vettore alla ricerca del valore
for (curs = 0; curs < dim; curs ++)
// se individuato restituisce la sua posizione
if(Vett[curs] == val)
return(curs);
// altrimenti restituisce -1
return(-1);
};
// chiamante
int main ()
{
// definizione della variabile per il valore di cui verificare la presenza e del vettore
int cerca, vettore[N];
// inizializzazione del contenuto del vettore
AcqVettInt(vettore, N);
// acquisizione del valore di cui verificare la presenza
printf("\nCerca il valore? ");
scanf("%d", &cerca);
// visualizza la posizione del valore all'interno del vettore, se presente, -1 altrimenti
printf("\nLa posizione di %d e' la %d", \
cerca, PosValVett(cerca, vettore, N));
return(1);
}
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
7
G. Amodeo,
C. Gaibisso
Esercizio 3: Algoritmo
• Algoritmo:
Ordinare un vettore di N
interi in ordine crescente:
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
Soluzione in: EsProposti\Lezione_XIV\Esercizio_3.c
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
8
G. Amodeo,
C. Gaibisso
Esercizio 3: Algoritmo
Ordinare, in ordine
crescente, un vettore di N
interi:
Selection Sort
• Sottoproblemi:
1. determinare la posizione del
valore minimo a partire da una
posizione data
2. scambiare i valori di due variabili
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
9
G. Amodeo,
C. Gaibisso
Esercizio 3: diagramma di flusso
Start
Nome:
PosMinVett
Variabili: int curs, pos, start
int vett[N]
Determinare la
posizione del valore
minimo a partire da
una posizione data
curs  start
min = vett[start]
pos  start
Descrizione variabili:
curs:
indice per la
scansione del vettore
vett[ ]: vettore interessato
dal processamento
start: posizione dalla quale
ha inizio il
processamento
max: massimo valore
individuato dalla
posizione start alla
posizione curs
pos:
posizione del valore
memorizzato in max
End
curs  curs+1
false
true
curs = N
pos
false
vett[curs] < min
true
pos  curs
min  vett[curs]
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
10
G. Amodeo,
C. Gaibisso
Esercizio 3: diagramma di flusso
Scambiare i
valori di due
variabili
Descrizione variabili:
A:
memorizza il
primo valore
B:
memorizza il
secondo
valore
aux: variabile di
appoggio
Start
Nome: Scambia
Variabili: int A, B, aux
aux  A
A B
B  aux
End
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
11
G. Amodeo,
C. Gaibisso
Esercizio 3: diagramma di flusso
Ordinare, in ordine
crescente, un
vettore di N interi:
Selection Sort
Start
Nome:
Selection Sort
Variabili: int curs, pos
int vett[N]
curs  0
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
curs = N-1
curs:
true
End
false
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: Le strutture di controllo - soluzione agli esercizi
12
G. Amodeo,
C. Gaibisso
Esercizio 3: il codice
// sorgente: EsProposti\Lezione_XIV\Esercizio_3.c
// direttive per il preprocessore
#include <stdio.h>
// definizione della dimensione del vettore
#define N 6
// funzione per l'acquisizione del contenuto di un vettore di interi
void AcqVettInt(int Vett[], int dim)
{
// definisce la variabile per la scansione del vettore
int pos;
// scandisce il vettore, acquisendone il contenuto
for (pos = 0; pos < dim; pos++)
{
printf("\nVett[%d]? ", pos);
scanf("%d", &Vett[pos]);
};
};
// funzione per la restituzione del contenuto di un vettore di interi
void ResVettInt(int Vett[], int dim)
{
// definizione della variabile per la scansione del vettore
int pos;
// scansione del vettore e restituzione del suo contenuto
for (pos = 0; pos < dim; pos++)
printf("\nVett[%d]: %d", pos,Vett[pos]);
};
continua …
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
13
G. Amodeo,
C. Gaibisso
Esercizio 3: il codice
continua …
// funzione che determina la posizione del minimo elemento all'interno
// di un vettore a partire da una posizione data
int PosMinVett(int *Vett, int dim, int start)
{
// definisce la variabile per la scansione del vettore
int curs;
// definisce e inizializza le variabili per il minimo e per la sua posizione
int min = Vett[start]; int pos = start;
// scandisce il vettore
for (curs = start; curs < dim; curs ++)
// se necessario aggiorna il minimo e la sua posizione
if(Vett[curs] < min)
{
min = Vett[curs];
pos = curs;
};
// restituisce la posizione del minimo elemento
return(pos);
};
// funzione che scambia il contenuto di due variabili
void scambia(int *A, int *B)
{
// definisce una variabili di appoggio
int aux;
// scambia il contenuto delle due variabili tramite la variabile di appoggio
aux = *A; *A = *B; *B = aux;
};
continua …
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
14
G. Amodeo,
C. Gaibisso
Esercizio 3: il codice
continua …
// funzione di ordinamento
void InsertionSort(int *Vett, int dim)
{
// definisce la variabile per la scansione del vettore
int curs;
// scandisce il vettore
for (curs = 0; curs < dim-1; curs++)
{
// definisce la variabile per la posizione del minimo
int pos;
// determina la posizione del minimo a partire da quella corrente
pos = PosMinVett(Vett, dim, curs);
// scambia il valore dell'elemento corrente con quello del minimo
scambia(Vett+curs,Vett+pos);
};
};
// chiamante
int main ()
{
// definisce il vettore
int vettore[N];
// inizializza, ordina e restituisce il contenuto del vettore
AcqVettInt(vettore, N);
InsertionSort(vettore, N);
ResVettInt(vettore, N);
return(1);
};
Programmazione di Calcolatori: Le strutture di controllo - soluzione agli esercizi
15
Scarica

curs - Informatica