Post on 16-Oct-2020
Corso di Programmazione e Metodi NumericiIngegneria Aerospaziale – BAER
Unità 7
Matrici
Unità 7
Domenico Daniele Bloisi
Docenti
Metodi Numericiprof. Vittoria Brunivittoria.bruni@sbai.uniroma1.it
Programmazioneprof. Domenico Daniele Bloisibloisi@dis.uniroma1.itbloisi@dis.uniroma1.it
Sito del corso http://www.dis.uniroma1.it/~pmn
Nota: %7E corrisponde alla tilde ~
Pagina 22011/2012MatriciUnità 7
Orario delle Lezioni
Lunedì 10.15 – 11.45Martedì 08.30 – 10.00Martedì 08.30 – 10.00Giovedì 10.15 – 11.45Venerdì 10.15 – 11.45
Aula 15, Via Scarpa 14Aula 15, Via Scarpa 14
Pagina 32011/2012MatriciUnità 7
Informazioni Generali
Ing. Domenico Daniele Bloisi, PhD
Dipartimento di Ingegneria Informatica Automatica e GestionaleAutomatica e GestionaleVia Ariosto 25(adiacente Piazza Dante,
A fermate Manzoni, Vittorio Emanuele,Tram 3 fermata via Labicana)
mailto:bloisi@dis.uniroma1.it
http://www.dis.uniroma1.it/~bloisiPagina 42011/2012Matrici
Unità 7
Ricevimento
Martedì 15.00 – 17.00DIS via Ariosto 25DIS via Ariosto 25
Aula docenti adiacente aula A4
Si consiglia di inviare una email per conferma edi controllare preventivamente la bacheca degli avvisiavvisi
Pagina 52011/2012MatriciUnità 7
Sommario – Unità 7
• Array come collezione di elementi• Dichiarazione di variabili array• Creazione di oggetti array• Creazione di oggetti array• Accesso agli elementi di un oggetto array• Espressioni che rappresentano oggetti array• Ricerca sequenziale di un elemento in un array
• Array come risultato di una funzione• Array come risultato di una funzione• Matrici (come array di array)
Pagina 62011/2012MatriciUnità 7
Variabili array e puntatori
const int N=4;int A[N] = {1,2,3,4};int *B;int *B;B = A;for (int i=0; i < N; i++)
cout << B[i] << endl;B[0] = 10;cout << "A[0] = " << A[0] << endl;
La variabile array A può essere assegnata ad una La variabile array A può essere assegnata ad una variabile puntatore ad interi B. Dopo l’assegnazione Bpuò essere usata come una variabile array.
Pagina 72011/2012MatriciUnità 7
EsecuzioneIl frammento di codice precedente, se eseguito, pro duce il seguente output11234A[0] = 10
Nota: una variabile array non può essere assegnata ad un’altra variabile array.un’altra variabile array.
Pagina 82011/2012MatriciUnità 7
Ricerca sequenziale di un elemento in un arrayScriviamo una funzione cercaArray che prende come parametri un array di interi v , un intero n corrispondente alla dimensione dell’array ed un intero e da cercare alla dimensione dell’array ed un intero e da cercare nell’array. La funzione restituisce true se il valore e è presente nell’array, false altrimenti:
bool cercaElemArray(int v[], int n, int e) {for (int i=0; i < n; i++)
if (e == v[i])return true;return true;
return false;}
Pagina 92011/2012MatriciUnità 7
Esempio d’uso
int main () {const int n = 4;int x[n] = {1, 2, 3, 4};int x[n] = {1, 2, 3, 4};cout << "Array-x: " << endl;for(int i = 0; i < n; i++)
cout << x[i] << endl;// cerca il valore 3 nell’array xif(cercaElemArray(x, n, 3))
cout << "trovato" << endl;cout << "trovato" << endl;else
cout << "non trovato" << endl;}
Pagina 102011/2012MatriciUnità 7
Esecuzione
Array -x:11234trovato
Pagina 112011/2012MatriciUnità 7
Ricerca del valore massimo in un arrayScriviamo una funzione massimoArray che prenda come parametro un array a e la sua lunghezza n e restituisca il massimo valore in a (si assuma che l’array contenga massimo valore in a (si assuma che l’array contenga almeno un elemento).Una possibile realizzazione è la seguente:
long massimoArray(long a[], int n) {long max = a[0];int i;for (i = 1; i < n; i++)for (i = 1; i < n; i++)
if (a[i] > max)max = a[i];
return max;}
Pagina 122011/2012MatriciUnità 7
Esempio d’usoint main () {
const int n=5;long x[n] = { 5, 3, 9, 5, 12 }; // creazione array
// x di 5 long// x di 5 longfor (int i=0; i<n; i++)
cout << x[i] << endl;cout << "massimo = " << massimoArray(x,n) << endl;
}
Output5
Pagina 132011/2012MatriciUnità 7
539512massimo = 12
Rovesciare i valori di un array
Scriviamo una funzione rovesciaArray che prenda come parametro un array e ne modifichi il contenuto mett endo gli elementi in ordine inverso, dall’ultimo al prim o.gli elementi in ordine inverso, dall’ultimo al prim o.
void scambia(int &i, int &j){ int t=i; i=j; j=t; }
void rovesciaArray(int v[], int n) {for (int i=0; i < n/2; i++)
scambia(v[i], v[n - i - 1]);scambia(v[i], v[n - i - 1]);return;
}
Pagina 142011/2012MatriciUnità 7
Esempio d’usoint main () {
const int n=5;int x[n] = { 5, 3, 9, 5, 12 }; // creazione array
//x di 5 int//x di 5 intfor (int i=0; i<n; i++) // stampa 5 3 9 5 12
cout << x[i] << " ";cout << endl;rovesciaArray(x,n); // rovescia l’array xfor (int i=0; i<n; i++) // stampa 12 5 9 3 5
cout << x[i] << " ";cout << endl;cout << endl;return EXIT_SUCCESS;
}
Pagina 152011/2012MatriciUnità 7
Esecuzione
5 3 9 5 1212 5 9 3 512 5 9 3 5
Si noti che il meccanismo di passaggio dei parametri fornisce come parametro attuale al metodo rovesciaArray il riferimento ad array contenuto in x , che viene copiato nel parametro formale v .formale v .Quindi v ed x si riferiscono al medesimo array.
Pagina 162011/2012MatriciUnità 7
Array come risultato di una funzione
La funzione copiaInversa prende come parametro un array e restituisce un array con gli elementi in or dine inverso, dall’ultimo al primo.
int* copiaInversa(int v[], int n) {int* temp = new(int[n]);for (int i=0; i<n; i++) {
temp[n-1-i] = v[i];}return temp ;
inverso, dall’ultimo al primo.
return temp ;} In questo caso, poiché si vuole
restituire un array, l’array viene creato dinamicamente all’interno della funzione.
Pagina 172011/2012MatriciUnità 7
Esempio d’usoint main () {
const int n=5;int x[n] = { 5, 3, 9, 5, 12 };for (int i=0; i<n; i++) // stampa 5 3 9 5 12for (int i=0; i<n; i++) // stampa 5 3 9 5 12
cout << x[i] << " ";cout << endl;int* y = copiaInversa(x,n); // restituisce un
// array con gli// elementi in ordine inverso
for (int i=0; i<n; i++) // stampa 12 5 9 3 5cout << y[i] << " ";cout << y[i] << " ";
cout << endl;return EXIT_SUCCESS;
}
Pagina 182011/2012MatriciUnità 7
Nota
Il risultato di una funzione può essere un riferimento ad un array, ma occorre usare esplicitamente il puntatore , cioè non si può esplicitamente il puntatore , cioè non si può scrivere int [] come risultato della funzione.
In alternativa, si sarebbe potuto usare un parametro di tipo array anche per il risultato, con la relativa dichiarazione fatta (staticamente) con la relativa dichiarazione fatta (staticamente) nel main .
Pagina 192011/2012MatriciUnità 7
NotaArray allocati staticamente non devono essere deall ocati esplicitamente. L’array x nell’esempio precedente sarà deallocato automaticamente al termine del bloccodeallocato automaticamente al termine del bloccodi codice in cui è definito (cioè nel main ).
Invece, quando si alloca dinamicamente un array, al termine del suo uso bisogna deallocare la memoria occupata esplicitamente, tramite l’operatore delete .
Nell’esempio presedente si può aggiungere nellafunzione main la seguente istruzione per rilasciare la funzione main la seguente istruzione per rilasciare la memoria allocata nella funzione copiaInversa
delete(y);
Pagina 202011/2012MatriciUnità 7
Matrici
Una matrice è una collezione in forma tabellare di elementi dello stesso tipo , ognuno dei quali è indicizzato da una coppia di numeri che indicizzato da una coppia di numeri che identificano riga e colonna dell’elemento.
Una matrice può essere rappresentata in C++ mediante un array multidimensionale .
Pagina 212011/2012MatriciUnità 7
Esempi
Dichiarazione di una matrice 3x5 accessibile mediante la variabile m:mediante la variabile m:
int m[3][5];
Dichiarazione di una matrice NxM mat
int mat[N][M];
Pagina 222011/2012MatriciUnità 7
Accesso agli elementi della matrice
Per accedere ai singoli elementi della matrice si p uò procedere come segue:
// assegnazione dell’elemento della matrice m// alla riga 1, colonna 2m[1][2] = 39;// assegnazione dell’elemento della matrice m// alla riga 0, colonna 0m[0][0] = 4;m[0][0] = 4;cout << m[1][2]; // stampa 39
Pagina 232011/2012MatriciUnità 7
Rappresentazione grafica
Pagina 242011/2012MatriciUnità 7
Espressioni che denotano oggetti matrice Poiché una matrice è semplicemente un array i cui elementi sono a loro volta array, nella definizione di matrici è possibile utilizzare espressioni che denota no matrici è possibile utilizzare espressioni che denota no matrici come nel seguente esempio:
int m[][2] = {{ 3, 5 },{ 9, 12 }
};
Nota: solo la prima dimensione dell’array può essere non specificata.
Pagina 252011/2012MatriciUnità 7
Esempioint main () {
int m[][2] = {{ 3, 5 }, Cosa stampa questo { 3, 5 },{ 9, 12 }
};int i, j;for(i = 0; i < 2; i++) {
for(j = 0; j < 2; j++) {cout << m[i][j] << " ";
Cosa stampa questo programma?
}cout << endl;
}}
Pagina 262011/2012MatriciUnità 7
Esecuzione
La definizione di matrice
int m[][2] = {int m[][2] = {{ 3, 5 },{ 9, 12 }
};
è equivalente a:
int m[2][2];int m[2][2];m[0][0] = 3; m[0][1] = 5;m[1][0] = 9; m[1][1] = 12;
Pagina 272011/2012MatriciUnità 7
Numero di righe e colonne di una matriceUsando l’operatore sizeof è possibile risalire al numero di elementi dell’array, anche nel caso multidimensi onale.
int x[][2]= {{ 3, 5}, {9, 12}};cout << "dimensione array " <<
sizeof(x) << " bytes" << endl;
stampa il valore 16, che corrisponde al numero di b yte per memorizzare 4 int (4 byte ciascuno)
Pagina 282011/2012MatriciUnità 7
Stampa di una matrice per righe
for (int i=0; i<N; i++) {
stampa di una matrice per righe
for (int i=0; i<N; i++) {for (int j=0; j<M; j++)
cout << m[i][j] << " ";cout << endl;
}
Si noti che per accedere a tutti gli elementi della matrice musiamo Si noti che per accedere a tutti gli elementi della matrice musiamo due cicli for annidati: quello esterno scandisce le righe ( i ), quello interno scandisce gli elementi di ogni riga ( j ).Quando tutti gli elementi di una riga sono stati st ampati, viene scritto un ritorno a capo.
Pagina 292011/2012MatriciUnità 7
Stampa di una matrice per colonne
for (int j=0; j<M; j++) {for (int i=0; i<N; i++)
Stampa di una matrice per colonne
for (int i=0; i<N; i++)cout << m[i][j] << " ";
cout << endl;}
Esercizio 7.5Scrivere un programma che stampi prima per Scrivere un programma che stampi prima per righe e poi per colonne la matrice1 2 34 5 6
Pagina 302011/2012MatriciUnità 7
Somma di matrici
Si assuma che A e B abbiano le stesse dimensioni (stesso numero di righe e stesso numero di colonne).Vogliamo definire i valori di una nuova matrice C ottenutaVogliamo definire i valori di una nuova matrice C ottenutasommando gli elementi corrispondenti di A e B.
for (i = 0; i < N; i++)for (j = 0; j < M; j++)
C[i][j] = A[i][j] + B[i][j];
Per accedere a tutti gli elementi della matrice A (e a Per accedere a tutti gli elementi della matrice A (e a quelli di B) usiamo due cicli for annidati: quello esterno scandisce le righe ( i ), quello interno scandisce gli elementi di ogni riga ( j ).
Pagina 312011/2012MatriciUnità 7
Prodotto di matrici
Scriviamo un frammento di codice che definisca i valori di una nuova matrice Cottenuta come prodotto di A e B.ottenuta come prodotto di A e B.
Si assuma che
1. Le matrici siano quadrate, cioè abbiano lo stesso numero di righe e colonne
2. Le matrici abbiano le stesse dimensioni.2. Le matrici abbiano le stesse dimensioni.
Pagina 322011/2012MatriciUnità 7
Prodotto di matrici
Ogni elemento C[i][j] del prodotto di matrici A・・・・B è ottenuto come prodotto scalare della riga i di A con la colonna j di B,i di A con la colonna j di B,cioè per ogni coppia di indici i,j , si ha:
Pagina 332011/2012MatriciUnità 7
Esecuzione
for (i = 0; i < N; i++)for (j = 0; j < N; j++) {
C[i][j] = 0;C[i][j] = 0;for (k = 0; k < N; k++)
C[i][j] += A[i][k] * B[k][j];}
Si noti che per calcolare il prodotto delle matriciC = A x B usiamo tre cicli for annidati :quello esterno scandisce le righe ( ) di , quello quello esterno scandisce le righe ( i ) di C, quello intermedio scandisce le colonne ( j ) di C, mentre quello più interno calcola il prodotto scalare della riga i di A con la colonna j di B, che viene assegnato a C[i][j] .
Pagina 342011/2012MatriciUnità 7
Passaggio di parametri matrice
Nel passaggio dei parametri per le matrici (e in ge nerale per array multi-dimensionali) è necessario specific are nell’intestazione della funzione tutte le dimensioni nell’intestazione della funzione tutte le dimensioni dell’array, eccetto la prima.Per le matrici, è quindi necessario specificare il numero di colonne.
void stampaMatrice (int A[][3], ...) {...}
Pagina 352011/2012MatriciUnità 7
Passaggio di parametri matrice
La funzione stampaMatrice stampa solo matrici con 3 colonne!Il meccanismo quindi non consente di scrivere Il meccanismo quindi non consente di scrivere una funzione che stampi matrici di qualsiasi dimensione.Per risolvere questi problemi possono essere utilizzate altre strutture di dati che rappresentan o matrici, oppure apposite librerie matematiche matrici, oppure apposite librerie matematiche (e.g., gsl ).
Pagina 362011/2012MatriciUnità 7
Esercizi
Esercizio 7.6Scrivere una funzionebool arrayUguali(int[] A, int[] B, int n)bool arrayUguali(int[] A, int[] B, int n)
che restituisca
� true se gli array A e B sono uguali (cioè hanno tutti gli elementi corrispondenti uguali)
� false altrimenti.
Pagina 372011/2012MatriciUnità 7
Esercizi
Esercizio 7.7Una matrice Msi dice diagonale se tutti gli elementi M[i][j] con i diverso da j (cioè che elementi M[i][j] con i diverso da j (cioè che non appartengono alla diagonale principale) valgono zero.Scrivere una funzione che restituisca true se la matrice Mè diagonale e false altrimenti.
Pagina 382011/2012MatriciUnità 7
Allocazione dinamica di matrici
In C++ è possibile creare una matrice allocando memoria dinamicamente. A tale scopo utilizzeremo un puntatore a puntatore.puntatore a puntatore.
Esempio
int **m;
L’idea è quella di creare dinamicamente un array di puntatori che rappresenti le righe della matrice.puntatori che rappresenti le righe della matrice.Ogni riga punterà ad una colonna, rappresentata da un array allocato dinamicamente.
Pagina 392011/2012MatriciUnità 7
Allocazione dinamica di matrici
int i;int** m;m = new (int*[ROWS]);m = new (int*[ROWS]);for(i = 0; i < ROWS; i++) {
m[i] = new (int[COLUMNS]);}
ROWS = 3COLUMNS = 2COLUMNS = 2
array di puntatoriarray di int
Pagina 402011/2012MatriciUnità 7
Allocazione dinamica di matrici
m[0][1] = 5;m[0][1] = 5;m[2][0] = 6;
ROWS = 3COLUMNS = 2
5
COLUMNS = 2
array di puntatoriarray di int6
Pagina 412011/2012MatriciUnità 7
Esercizio
Si scriva una funzione creaMat che presi in ingresso due interi r e c , restituisca una matrice creata dinamicamente.creata dinamicamente.
Si realizzi un programma di prova che utilizzi creaMat per creare la matrice3 6 8 9
12 54 6 8912 54 6 89stampandone il contenuto
Pagina 422011/2012MatriciUnità 7
Funzione creaMat
int** creaMat(int r, int c) {int i;int** m;int** m;m = new (int*[r]);if(m == NULL)
return NULL;for(i = 0; i < r; i++) {
m[i] = new (int[c]);if(m[i] == NULL)if(m[i] == NULL)
return NULL;}return m;
}Pagina 432011/2012Matrici
Unità 7
Mainint main() {
int r = 2, c = 4;int i, j;int **m = creaMat(r, c);int **m = creaMat(r, c);if(m == NULL)
return EXIT_FAILURE;m[0][0] = 3; m[0][1] = 6; m[0][2] = 8; m[0][3] = 9;m[1][0] = 12; m[1][1] = 54; m[1][2] = 6; m[1][3] = 89;for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {cout << m[i][j] << " ";cout << m[i][j] << " ";
}cout << endl;
}return EXIT_SUCCESS;
}Pagina 442011/2012Matrici
Unità 7
Deallocazione di una matrice allocata dinamicamente
63 8 9
Cosa accade se si esegue delete(m) ?
5412 6 89
63 8 9
5412 6 89
Pagina 452011/2012MatriciUnità 7
Deallocazione di una matrice allocata dinamicamente
63 8 9
Prima di eseguire delete(m) è necessario effettuare una deletesu ogni riga.
delete(m[0]);
6
54
3 8 9
12 6 89
5412 6 89
Pagina 462011/2012MatriciUnità 7
Deallocazione di una matrice allocata dinamicamente
Deallocazione corretta
for(i = 0; i < r; i++) {for(i = 0; i < r; i++) {delete(m[i]);
}delete(m);
Pagina 472011/2012MatriciUnità 7
Modifica main precedente...
for(i = 0; i < r; i++) {for(j = 0; j < c; j++) {
cout << m[i][j] << " ";cout << m[i][j] << " ";}cout << endl;
}for(i = 0; i < r; i++) {
delete(m[i]);}delete(m);for(i = 0; i < r; i++) {for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {cout << m[i][j] << " ";
}cout << endl;
}...
Pagina 482011/2012MatriciUnità 7
Esecuzione
3 6 8 912 54 6 8912 54 6 894072432 4069128 8 94069128 4072880 4063544 1662624681
Pagina 492011/2012MatriciUnità 7
Accesso ad una matrice tramite aritmetica dei puntatoriSia A una matrice 5x4 allocata dinamicamente.Se si vuole accedere all’elemento A[3][2] è possibi le utilizzare l’aritmetica dei puntatori nel seguente mo do:utilizzare l’aritmetica dei puntatori nel seguente mo do:
*(*(A+3)+2)
(A+3) è il quarto puntatore dell’array che rapprese nta le righe*(A+3) è l’indirizzo del primo elemento della quarta riga*(A+3)+2 è l’indirizzo del terzo elemento della quarta riga*(A+3)+2 è l’indirizzo del terzo elemento della quarta riga*(*(A+3)+2) è il contenuto della cella puntata dal puntatore al terzo elemento della quarta riga
Pagina 502011/2012MatriciUnità 7
Accesso ad una matrice tramite aritmetica dei puntatori
0
0 1 2 3A(0,0)
0
1
2
3
A(3,2)
4
Pagina 512011/2012MatriciUnità 7