Programare Competitivă

Tablouri multidimensionale

Un tablou multidimensional este un tablou indexat cu mai mulți indici. Dacă un vector are un singur indice (v[i]), un tablou bidimensional are doi (a[i][j]), iar unul tridimensional are trei (a[i][j][k]).

Cu alte cuvinte, este extensia naturală a vectorilor la mai multe dimensiuni.

De la vector la tablou multidimensional

Vector (1D)

int v[101];

Accesăm elementele cu un singur indice:

  • v[1]
  • v[2]
  • v[i]

Matrice (2D)

int a[101][101];

Accesăm elementele cu doi indici:

  • a[1][1]
  • a[2][3]
  • a[i][j]

Acesta este cazul cel mai frecvent și l-ai văzut deja la matrici.

Tablou tridimensional (3D)

int b[11][21][31];

Accesăm elementele cu trei indici:

  • b[1][1][1]
  • b[2][3][4]
  • b[i][j][k]

Ne putem imagina un tablou 3D ca pe o colecție de straturi, unde fiecare strat este o matrice.

Cum arată un tablou tridimensional?

Să presupunem că avem 2 straturi, fiecare cu 3 linii și 4 coloane.

Stratul 1

1 2 3 4
5 6 7 8
9 1 2 3

Stratul 2

4 5 6 7
8 9 1 2
3 4 5 6

Putem spune că:

  • b[1][1][1] = 1
  • b[1][2][3] = 7
  • b[2][3][4] = 6

În notația b[i][j][k]:

  • i = stratul
  • j = linia
  • k = coloana

Ideea-cheie: o matrice este doar un tablou bidimensional. Un tablou tridimensional este un „teanc de matrici”.

Declararea unui tablou multidimensional

Bidimensional

int a[101][101];

Tridimensional

int b[11][101][101];

Acesta poate memora, de exemplu, cel mult:

  • 10 straturi
  • 100 linii pe fiecare strat
  • 100 coloane pe fiecare strat

Avem nevoie și de dimensiunile efective:

int p, n, m; // p = straturi, n = linii, m = coloane

Citirea unui tablou tridimensional

Dacă primim p, n, m, apoi valorile pentru toate elementele, folosim 3 bucle imbricate.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int b[11][101][101];
int p, n, m;

int main()
{
    fin >> p >> n >> m;

    for (int i = 1; i <= p; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                fin >> b[i][j][k];

    return 0;
}

date.in:

2 2 3
1 2 3
4 5 6
7 8 9
10 11 12

Aici avem:

  • 2 straturi
  • 2 linii
  • 3 coloane

Afișarea unui tablou tridimensional

De obicei afișăm pe straturi:

for (int i = 1; i <= p; i++) {
    fout << "Stratul " << i << ":\n";
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= m; k++)
            fout << b[i][j][k] << " ";
        fout << "\n";
    }
}

Parcurgerea completă

La un tablou cu d dimensiuni, avem în general nevoie de d bucle.

Pentru 2D

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        // procesăm a[i][j]

Pentru 3D

for (int i = 1; i <= p; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            // procesăm b[i][j][k]

Suma tuturor elementelor

int suma = 0;

for (int i = 1; i <= p; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            suma = suma + b[i][j][k];

fout << suma;

Maximul dintr-un tablou 3D

int maxim = b[1][1][1];

for (int i = 1; i <= p; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            if (b[i][j][k] > maxim)
                maxim = b[i][j][k];

fout << maxim;

Suma pe fiecare strat

Fiecare strat este, practic, o matrice.

for (int i = 1; i <= p; i++) {
    int suma = 0;
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            suma = suma + b[i][j][k];
    fout << "Stratul " << i << ": " << suma << "\n";
}

Suma pe o linie fixă din toate straturile

De exemplu, vrem suma elementelor de pe linia x din toate straturile:

int x;
fin >> x;

int suma = 0;

for (int i = 1; i <= p; i++)
    for (int k = 1; k <= m; k++)
        suma = suma + b[i][x][k];

fout << suma;

Numărarea elementelor cu o proprietate

Câte elemente pare sunt în tot tabloul?

int cnt = 0;

for (int i = 1; i <= p; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            if (b[i][j][k] % 2 == 0)
                cnt++;

fout << cnt;

Matricea este un caz particular

Un tablou bidimensional este exact o matrice. De aceea:

  • la 2D vorbim despre linii și coloane
  • la 3D vorbim despre straturi, linii și coloane
  • la 4D și mai sus, ideea este aceeași, doar că apar mai mulți indici

În practică, la concursuri apar cel mai des:

  • vectori (1D)
  • matrici (2D)
  • mai rar tablouri 3D

Exemplu complet

Citim un tablou 3D și afișăm suma fiecărui strat și maximul global.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int b[11][101][101];
int p, n, m;

int main()
{
    fin >> p >> n >> m;

    for (int i = 1; i <= p; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                fin >> b[i][j][k];

    int maxim = b[1][1][1];

    for (int i = 1; i <= p; i++) {
        int suma = 0;
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++) {
                suma = suma + b[i][j][k];
                if (b[i][j][k] > maxim)
                    maxim = b[i][j][k];
            }
        fout << "Stratul " << i << ": suma = " << suma << "\n";
    }

    fout << "Maximul: " << maxim << "\n";

    return 0;
}

date.in:

2 2 3
1 2 3
4 5 6
7 8 9
10 11 12

date.out:

Stratul 1: suma = 21
Stratul 2: suma = 57
Maximul: 12

Memorie și limitări

Un tablou multidimensional ocupă multă memorie.

De exemplu:

int b[11][101][101];

are aproximativ 11 * 101 * 101 ≈ 112000 elemente.

Dacă fiecare int ocupă 4 bytes, atunci memoria folosită este de aproximativ:

112000 * 4 ≈ 448000 bytes

adică aproximativ 448 KB.

La dimensiuni mari, tablourile multidimensionale se declară global, nu local.

Greșeli frecvente

1. Ordinea indicilor este încurcată

b[j][i][k] // GREȘIT dacă ordinea este [strat][linie][coloana]
b[i][j][k] // CORECT

Mereu trebuie să știm clar ce reprezintă fiecare indice.

2. Numărul de bucle nu corespunde dimensiunilor

Pentru un tablou 3D avem nevoie de 3 bucle, nu de 2.

for (int i = 1; i <= p; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= m; k++)
            fin >> b[i][j][k];

3. Dimensiunile sunt declarate prea mici

Dacă p <= 10, n <= 100, m <= 100, declarăm ceva de forma:

int b[11][101][101];

ca să putem indexa de la 1.

4. Tabloul este declarat local și ocupă prea mult

int main() {
    int b[50][500][500]; // PERICOL!
}

Tablourile mari se declară global.

5. Confuzia dintre „dimensiune” și „indice”

În:

int b[11][101][101];
  • 11, 101, 101 sunt dimensiunile maxime
  • i, j, k sunt indicii cu care accesăm elementele

Ce să reții

  • Un tablou multidimensional are 2 sau mai mulți indici.
  • Matricea este un tablou bidimensional.
  • Un tablou 3D se poate vedea ca un set de straturi, fiecare fiind o matrice.
  • Pentru un tablou cu d dimensiuni folosim, de regulă, d bucle imbricate.
  • Accesul se face cu notații de forma a[i][j], b[i][j][k].
  • Tablourile mari se declară global.
  • În practică, cele mai importante sunt tablourile 2D și 3D.
Cuprins Inapoi Inainte