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