Matrius

Aquesta lliçó presenta una aplicació molt utilitzada dels vectors, l’ús i creació de matrius.

Introducció

Una matriu és una estructura que permet guardar diverses dades d’un mateix tipus, distribuïdes en diverses files, les quals poden tenir diverses columnes. De fet podem pensar que cada fila d’una matriu és un vector, i aquesta de fet serà la manera de construirles.

Així, per exemple, la manera en la que haurem de pensar la matriu blava del dibuix serà com un vector de dos elements (les dues files), on cada element és un vector de tres elements (les tres columnes).

De la mateixa manera que als vectors, podem definir l’índex d’un element dins d’una matriu $n \times m$ com la posició que ocupa en aquesta, tenint en compte que la primera fila és la $0$ i l’última la $n-1$, i d’igual manera la primera columna és la $0$ i l’última la $m-1$. Així, direm que l’element que està a la fila $i$ i columna $j$ té l’índex $(i,j)$.

Per referir-nos a l’element d’índex $(i,j)$, farem servir la notació [i][j] després de l’identificador del vector (com podeu veure és coherent amb la notació pels vectors, ja que una matriu M és un vector en el que l’element M[i] és un altre vector que conté a la posició [j] l’element d’índex [i][j]). Per exemple, en la matriu vermella del dibuix (que anomerarem M) tenim que M[1][0] és l’element 3, M[2][1] és l’element 2, M[0] és el vector {1, -2} i M[2] és el vector {1, 2}.

L’ús de matrius ens serà de gran utilitat per resoldre problemes de tot tipus, ja que molts taulers de jocs i moltes altres situacions es poden representar fàcilment per matrius.

Creació de matrius

Recordeu en primer lloc que, com que essencialment les matrius són vectors de vectors, per fer-les servir haurem d’incloure la línia #include <vector> a l’inici del programa.

Per crear una matriu, ho farem de la mateixa manera que creem un vector, però en aquest cas el tipus d’element d’aquest vector serà un altre cop un vector, aquest ja del tipus de dades desitjat. Així,

vector<vector<int>> laMevaMatriu;

crea una matriu buida anomenada laMevaMatriu. Les maneres d’inicialitzar una matriu són exactament les mateixes que les d’un vector, tenint en compte que una matriu no és més que un vector de vectors. Aquí teniu un recordatori:

vector<vector<double>> Res;     // matriu buida
vector<vector<int>> Files(5);   // matriu amb 5 vectors buits (files)
vector<vector<bool>> Falsos(3, vector<bool>(2));
                                // matriu 3x2 plena amb elements false
vector<vector<char>> Eses(2, vector<char>(4, 's'));
                                // matriu 2x4 plena amb elements 's'
vector<vector<int>> Nombres = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
                                // matriu 3x3 amb les files especificades

Si no recordeu alguna d’aquestes inicialitzacions podeu trobar-les explicades a la lliçó de vectors.

També podem, com als vectors, inicialitzar una matriu copiant-la d’una altra, o inclús copiant algunes files, de la manera següent:

vector<vector<int>> M = {{1, -3, 2}, {-1, 4, 3}};
vector<int> v = {2, 1, -5};

vector<vector<int>> M_copia = M;
vector<vector<int>> M_girat = {M[1], M[0]};
vector<vector<int>> M_ampliat = {M[0], M[1], v};

Aquí podeu veure com quedarien cadascuna d’aquestes matrius:

Vectors de més dimensions

Igual que per fer matrius hem fet que un vector contingui altres vectors, podem fer que aquests vectors continguin alhora més vectors, i així indefinidament. Així, podem per exemple crear un vector multidimensional de $n \times m \times r$ com

vector<vector<vector<int>>> V(n, vector<vector<int>>(m, vector<int>(r)));

Aquesta construcció ens pot servir per exemple per guardar dades sobre punts en l’espai. No obstant, no és molt habitual el seu ús als programes així que no entrarem en més detalls.

Ús de using

Com haureu vist, crear matrius pot arribar a ser una mica engorrós i complicat de llegir a causa de la notació. És per això que sovint es fan servir abreviatures, que podem definir amb la funció using. Així, posant al principi del codi

#include <iostream>
#include <vector>
using namespace std;

using vectorC = vector<char>;
using matriuC = vector<vectorC>;

int main() { ...

estem renombrant les crides a vectors i matrius de caràcters. D’aquesta manera, cada cop que escrivim vectorC serà completament equivalent a haver escrit vector<char>, i quan escrivim matriuC serà interpretat com vector<vector<char>>. Amb aquestes definicions el nostre codi quedarà més llegible i f’acil d’entendre ja que, per exemple, el que abans escriviem com

int main() {
    vector<int> v(10, 0);
    vector<vector<int>> M(8, vector<int>(5, -1));
}

ara quedarà

using vectorI = vector<int>;
using matriuI = vector<vectorI>;

int main() {
    vectorI v(10, 0);
    matriuI M(8, vectorI(5, -1)); 
}

Matrius com a paràmetres de subprogrames

En el cas de les matrius, com que en general contenen una gran quantitat d’elements, pràcticament sempre que sigui possibles les passarem per referència (o referència constant, si no les volem modificar), ja que si no estarem fent una còpia de tota la matriu i els nostres programes seran molt més lents i utilitzaran una quantitat de memòria exageradament gran, que es pot estalviar d’una manera tant senzilla com és posar un & en la especificació del paràmetre.

Un exemple d’acció molt recurrent que implementarem als nostres programes és la d’escriure una matriu en una disposició semblant a com ens la imaginem. Així, si executem l’acció

void escriu(const vector<vector<int>& M) {
    int n = M.size();               // Nombre de files (Talla de la matriu)
    int m = M[0].size();            // Nombre de columnes (Talla d'una fila)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << M[i][j]<< " ";  // Escrivim tot la fila
        }
        cout << endl;               // Canviem de línea
    }
}

amb la matriu M = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, obtindrem

1 2 3 
4 5 6
7 8 9

Nota: Amb l’acció que hem escrit, al final de cada línea estem escrivint un espai innecessari, que podem solucionar escrivint l’últim element de la fila per separat del bucle, però per ara no ens posarem meticulosos amb aquest tema.

Lectura de matrius

En general, ens interessarà llegir certs valors donats i guardar-los en una matriu. La manera més comuna de fer-ho és passar-li al programa les dimensions de la matriu que voldrem llegir, seguits dels elements de la matriu. Així, pel cas d’una matriu d’enters, el nostre codi tindrà un aspecte semblant al següent:

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n, m;
cin >> n >> m;          // Llegim les dimensions de la matriu

vector<vector<int>> M(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {       // Per cada fila
        for (int j = 0; j < m; ++j) {   // I per cada columna
            cin >> M[i][j];             // Llegim l'element corresponent
        }
    }
}

Recórrer una matriu

Com recordareu hi havia dues maneres de recórrer els elements d’un vector. En el cas de les matrius, heu de tenir sempre present quina és la seva estructura: és un vector de vectors. És un error habitual pensar que una matriu és una estructura per si mateixa que conté elements del tipus que especifiquem (int, char, etc.), i llavors podríem estar temptats a escriure un bucle com el següent

vector<vector<int>> M = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int x : M) {       // 💥 Els elements de M no són del tipus int
    cout << x << endl;
}

Això no és correcte, ja que com hem dit, el que conté la matriu M són vectors de enters, i aquests vectors són els que contenen els elements de tipus int. Així, si volem fer servir aquest tipus de bucle, hauríem d’escriure:

vector<vector<int>> M = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (vector<int>& v : M) {       // 😃 Els elements de M són del tipus vector<int>
    for (int x : v) {            // 😃 Els elements de v són del tipus int
        cout << x << endl;
    }
}

Recordeu que és recomanable passar per referència els vectors a qualsevol subprograma (en particular als bucles), per evitar-nos còpies innecessàries i costoses.

No obstant, és molt més habitual, i sovint més util i llegible, recórrer les matrius amb l’altre tipus de bucle, que ja hem presentat a l’hora de veure com llegir o escriure eles elements d’una matriu.


Fòrum







Lliçons.jutge.org
Rafah Hajjar
Universitat Politècnica de Catalunya, 2019

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.