Programmazione Procedurale in Linguaggio C++

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Programmazione Procedurale in Linguaggio C++

Strutture di Dati La Matrice

versione 2.1

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

Sommario

m

Introduzione

m

Definizione di Matrice

ðOperazioni su una Matrice

m

Matrici di Dimensione Costante

m

Matrici di Dimensione Variabile

ðRappresentazione con Record e Array

m

Il Problema delle Matrici Sparse

Strutture di Dati: La Matrice >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

m

Strutture di dati

ðorganizzazioni frequenti dei dati di un problema

ðnelle lezioni precedenti: la lista (struttura lineare e monodimensionale)

ðma la lista non è l’unica struttura di dati notevole

m

In questa lezione

ðla matrice matematica

4

Definizione di Matrice

m Matrice Matematica

ðcollezione di elementi tutti dello stesso tipo (tipicamente numeri)

ðbidimensionale: organizzata in righe e colonne ðogni elemento è caratterizzato dall’indice di riga e

l’indice di colonna

ðalcuni elementi possono essere “nulli” (tipicamente uguali a 0)

m Per semplicità

ðsupporremo che righe e colonne siano numerate con base 0 e non 1

Strutture di Dati: La Matrice >> Definizione di Matrice

(3)

Definizione di Matrice

m

Matrici speciali

ðmatrice nulla (tutti gli elementi sono nulle) ðmatrici quadrate (n. righe = n. colonne) ðmatrici quadrate diagonali (solo gli elementi

della diagonale sono non nulli)

ðmatrici quadrate triangolari superiori/inferiori (tutti gli elementi sotto/sopra la diagonale sono nulli)

Definizione di Matrice

m Esempio di matrice di numeri interi

ð[ 1 2 34 2]

ð[ 0 4 -1 3]

ð[11 2 8 0]

m In questa matrice

ð3 righe (0-2), 4 colonne (0-3) (matr. rettangolare) ðl’elemento (0, 2) vale 34

ðl’elemento (1, 1) vale 4 ðl’elemento (3, 5) non esiste ðci sono due elementi nulli

(4)

m

Operazioni essenziali su una matrice

ðaccedi all’elemento i, j: preleva il valore

dell’elemento in posizione i, j (se esiste) ðassegna valore all’elemento i, j: assegna un

valore all’elemento in posizione i, j (se esiste) ðnumero di righe: restituisce il numero di righe ðnumero di colonne: restituisce il numero di

colonne

8

Definizione di Matrice

m

Tutte le altre operazioni

ðsono riconducibili a queste essenziali

m

Esempi

ðvalori della i-esima riga ðvalori della j-esima colonna ðvalori della diagonale

ðnumero di elementi nulli

(5)

Definizione di Matrice

m

Due tipologie principali di matrici

ðmatrici di dimensioni costanti: il numero di righe e il numero di colonne è fissato

matrici di dimensioni variabili: il numero di righe e di colonne può variare (tra

un’esecuzione ed un’altra del programma)

m

Per ciascuna

ðuna tecnica di rappresentazione appropriata

Matrici di Dimensioni Costanti

m

Sono le più frequenti

ðil numero di righe ed il numero di colonne sono fissate e non possono cambiare ðes: matrice di un sistema 3 x 3

ðes: scacchiera per giocare a scacchi

m

In questo caso

ðbasta un array bidimensionale

ðcon componenti del tipo appropriato

Strutture di Dati: La Matrice >> Matrici di Dimensione Costante

(6)

m

Un esempio: matrice quadrata di interi

ðun programma che consente di effettuare

elaborazioni su una matrice quadrata NxN ðlettura da tastiera

ðgenerazione di matrici particolari (diagonali, triangolari)

ðstampa

ðelaborazioni (somme di righe, colonne, diagonale)

>> elaboraMatriceQuadrata.cpp

12

Matrici di Dimensioni Costanti

m

La rappresentazione della matrice

const int N = 10;

int matrice[N][N];

m

La struttura del programma

ðun menu con comandi numerici

ðche consente di effettuare le varie operazioni sulla matrice

(7)

Matrici di Dimensioni Costanti

void leggiMatrice(int matrice[N][N]) { cout << "Immetti gli elementi \n";

cout << "---\n";

for (int i = 0; i < N; i++) {

cout << "Riga n. " << i << endl;

for (int j = 0; j < N; j++) {

cout << "Elemento (" << i << "," << j << ")";

cin >> matrice[i][j];

} } return;

}

Matrici di Dimensioni Costanti

void stampaMatrice(int matrice[N][N]) { cout << "Valori della matrice \n";

cout << "---\n";

for (int i = 0; i < N; i++) { cout << "\t";

for (int j = 0; j < N; j++) { cout << matrice[i][j] << "\t";

}

cout << endl;

} return;

}

(8)

m

Generazione della matrice diagonale

ðsolo gli elementi sulla diagonale sono non

nulli

ðelemento sulla diagonale: i == j

4 3 2 1 0

16

Matrici di Dimensioni Costanti

void generaMatDiagonale(int matrice[N][N], int valore) { for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) { if (i == j) {

matrice[i][j] = valore;

} else {

matrice[i][j] = 0;

} } } return;

}

(9)

Matrici di Dimensioni Costanti

m

Generazione della matrice triangolare inf.

ðsolo gli elementi sulla diagonale e quelli sotto sono non nulli

ðelemento sulla o sotto la diagonale: i >= j

4 3 2 1 0

Matrici di Dimensioni Costanti

void generaMatTriangolare(int matrice[N][N], int valore) { for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) { if (i >= j) {

matrice[i][j] = valore;

} else {

matrice[i][j] = 0;

} } } return;

}

(10)

m

Una annotazione importante

ðla matrice nel suo complesso è una struttura bidimensionale

ðper le elaborazioni servono due cicli

m

Ma

ðle righe, le colonne e la diagonale sono strutture monodimensionali

ðper le elaborazioni basta un unico ciclo

20

Matrici di Dimensioni Costanti

m

Infatti

ðper gli el. di una riga l’indice di riga è fissato ðper gli el. di una colonna l’indice di colonna è

fissato

4 3 2 1 0

(11)

Matrici di Dimensioni Costanti

int sommaRiga(int matrice[N][N], int riga) { int somma = 0;

for (int j = 0; j < N; j++) { somma += matrice[riga][j];

}

return somma;

}

int sommaColonna(int matrice[N][N], int colonna) { int somma = 0;

for (int i = 0; i < N; i++) { somma += matrice[i][colonna];

}

return somma;

}

Matrici di Dimensioni Costanti

m

La diagonale

ðun elemento per ciascuna riga

ðl’indice di colonna è uguale all’indice di riga

int sommaDiagonale(int matrice[N][N]) { int somma = 0;

for (int i = 0; i < N; i++) { somma += matrice[i][i];

}

return somma;

}

(12)

m

Attenzione

ðin questo esempio: somma

ðma allo stesso modo si programmano le altre tecniche algoritmiche notevoli

ðes: conteggio

ðes: massimo (della matrice, di una riga, di una colonna, della diagonale)

ðes: verifica di condizioni (sulla matrice, su una riga, su una colonna, sulla diagonale

24

Matrici di Dimensione Variabile

m

In alcuni casi

ðla matrice può avere un numero di righe e di colonne variabile

ðes: scacchiera per giocare a battaglia navale

m

In questo caso

ðsi può usare una rappresentazione basata su array e record simile a quella per la lista

ðcon due indicatori di riempimento: uno per le righe e uno per le colonne

Strutture di Dati: La Matrice >> Matrici di Dimensione Variabile

(13)

Matrici di Dimensione Variabile

m Un esempio: il gioco della vita

ðun gioco di simulazione

ðsi gioca su una scacchiera (max. NxN elementi) ðogni elemento della scacchiera può contenere una

cellula viva oppure meno

ðda una scacchiera iniziale vengono prodotte varie configurazioni successive

ðnelle configurazioni successive la vita in un elemento si evolve secondo precise regole che dipendono dal numero di cellule negli elementi “vicini”

Matrici di Dimensione Variabile

m

Elementi vicini ad una cella

ðelementi del “contorno”

ðnormalmente sono 8 es: elemento (2, 1)

ðper le celle sui bordi possono essere meno

es: elemento (1, 0) es: elemento (4, 4)

4 3 2 1 0

8 7 6

5 x 4

3 2 1

4 3 2 1 0

x 3

2 1 4 5

3 x

2 1

(14)

m

Le regole del gioco della vita

ðse nell’elemento i,j c’è una cellula viva

ðse tra i vicini ci sono meno di due cellule vive, nella conf. succ. la cellula muore di solitudine ðse tra i vicini ci sono più di tre cellule vive, nella

conf. succ. la cellula muore per sovraffollamento ðaltrimenti la cellula sopravvive

ðse nell’elemento i,j non c’è una cellula viva

ðse tra i vicini ci sono esattamente tre cellule vive, nella conf. successiva nasce una cellula viva

28

Matrici di Dimensione Variabile

m

Il gioco

ðviene acquisita da un file la configurazione iniziale della scacchiera (matrice di 0 e 1, dove 1 vuol dire cellula viva)

ðviene chiesto all’utente quante configurazioni generare

ðvengono generate e stampate le configurazioni successive del gioco

>> giocoDellaVita.cpp

(15)

Matrici di Dimensione Variabile

m

La rappresentazione dei dati

const int MAXDIM = 10;

struct matrice { int righe;

int colonne;

int elementi[MAXDIM][MAXDIM];

};

void main() {

matrice scacchiera;

...

}

array bidimensionale di dimensione MAXDIMxMAXDIM indicatore di riempimento per le righe

indicatore di riempimento per le colonne

Matrici di Dimensione Variabile

m

Esempio

4 5 6 7 8

4 5 6 7 8 9 3

2 1 0

9 3 2 1 MAXDIM = 10; 0

scacchiera.righe = 4;

scacchiera.colonne = 6;

scacchiera.elementi elementi significativi

(16)

m

Nota

ðin teoria, come per le liste, questa

rappresentazione consente di aggiungere righe e colonne ad una matrice esistente ðma questo è necessario di rado

ðtipicamente: i due indicatori di riempimento vengono inizializzati all’avvio del programma e non vengono più cambiati

32

Il Diagramma delle Chiamate

main matrice scacchiera

schermoNomeFile (string &nomeFile)

stampaScacchiera (matrice scacchiera)

simula (matrice &scacchiera,

int ripetizioni) const int N = ... ; struct matrice {

int righe;

int colonne;

int elementi[N][N];

};

carica (matrice &scacchiera,

string nomeFile, bool &esito)

schermoRipetizioni (int &ripetizioni)

generaNuovoCiclo (matrice &scacchiera)

int nuovoValore (matrice &scacchiera,

int x, int y) for (int i=0; i < ripetizioni; i++)

for (int i=0; i < scacchiera.righe; i++) { for (int j=0; j < scacchiera.colonne; j++)

int contaVicini (matrice &scacchiera,

int x, int y)

copiaScacchiera (matrice scacchiera,

matrice &copia)

(17)

Matrici di Dimensione Variabile

m

Alcune operazioni interessanti

ðil caricamento della matrice dal file

ðil calcolo delle cellule vive negli elementi vicini

m

Caricamento dal file

ðal solito, il file contenente la matrice deve avere un formato preciso

Matrici di Dimensione Variabile

m

Il formato del file

ðprima riga: numero di righe

ðseconda riga: numero di colonne

ðrighe successive:

elementi per righe e colonne (0 oppure 1)

Righe: 5 Colonne: 5 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1

>> vita5x5.txt

>> vita7x9.txt

(18)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 35 ifstream file (nomeFile.c_str());

file >> tmp;

file >> righe;

file >> tmp;

file >> colonne;

if (righe <= MAXDIM && colonne <= MAXDIM) { scacchiera.righe = righe;

scacchiera.colonne = colonne;

for (int i = 0; i < scacchiera.righe; i++) { for (int j = 0; j < scacchiera.colonne; j++) {

file >> scacchiera.elementi[i][j];

} }

esito = true;

} else {

esito = false;

} return;

}

36

Matrici di Dimensione Variabile

m

L’analisi dei vicini

ðdata una cella x, y, bisogna contare gli 1 nel contorno ðrighe coinvolte: da x-1 a x+1 ðcol. coinvolte: da y-1 a y+1 ðes: x=2, y=1

ðattenzione agli sconfinamenti ðes: x=1, y=0

4 3 2 1 0

(19)

Matrici di Dimensione Variabile

int contaVicini (matrice scacchiera, int x, int y) { int conta = 0;

for (int i = x - 1; i <= x + 1; i++) { for (int j = y - 1; j <= y + 1; j++) {

if (i >= 0 && i < scacchiera.righe &&

j >= 0 && j < scacchiera.colonne) { conta += scacchiera.elementi[i][j];

} } }

return conta - scacchiera.elementi[x][y];

}

Il Problema delle Matrici Sparse

m

Matrice sparsa

ðmatrice in cui più del 90% degli elementi ha valore nullo (es: 0)

m

In questi casi

ðle due rappresentazioni viste hanno un notevole difetto

ðspreco di memoria: più del 90% dello spazio di memoria è sprecato

ðspreco di tempo: lunghe scansioni inutili

Strutture di Dati: La Matrice >> Il Problema delle Matrici Sparse

(20)

m

Una rappresentazione più adeguata

ðuna rappresentazione che si limiti a riservare memoria per le componenti non nulle

m

Intuizione

ðuna collezione ordinata delle componenti non nulle

ðper ciascuna: le coordinate (indice di riga e indice di colonna) e il valore

40

Il Problema delle Matrici Sparse

m

In teoria

ðsarebbe possibile utilizzare una lista, mantenendola ordinata

m

Ma

ðnella lista sarebbero frequentemente necessarie inserimenti e cancellazioni ðla rappresentazione che abbiamo (array e

record) non è particolarmente adatta

ðvedremo in seguito una soluzione più adatta

Strutture di Dati: La Matrice >> Il Problema delle Matrici Sparse

(21)

Riassumendo

m

Introduzione

m

Definizione di Matrice

ðOperazioni su una Matrice

m

Matrici di Dimensione Costante

m

Matrici di Dimensione Variabile

ðRappresentazione con Record e Array

m

Il Problema delle Matrici Sparse

Strutture di Dati: La Matrice >> Sommario

Termini della Licenza

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Termini della Licenza

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.