Matrici e array multidimensionali

Argomento di Programmazione 1. Fatto a lezione a ottobre, deck 4.1: slide 53-66 (dichiarazione, disposizione in memoria, inizializzazione, lettura e stampa), slide 67-73 (esercizi: lettura e stampa, matrice simmetrica), slide 93-100 (trasposta, matrici magiche). Prima: Array.

Il filo della seconda parte del deck:

int a[10][5]          10 righe, 5 colonne, indici 0..9 e 0..4, a[i][j]
   |
in memoria            lineare: una riga dopo l'altra
   |
inizializzazione      {{...},{...}}, oppure lista piatta; si omette solo la prima dimensione
   |
lettura e stampa      due for annidati: righe fuori, colonne dentro
   |
simmetrica            a[i][j] == a[j][i]: quattro versioni, sempre meno confronti
   |
trasposta, magica     AT[i][j] = A[j][i]; somme di righe, colonne, diagonali

1Definizioni

Array bidimensionale (matrice) (slide 53-54). In C si dichiara con due coppie di parentesi quadre:

int a[10][5];        matrice di 10 righe e 5 colonne

Gli indici vanno, come al solito, da 0 alla dimensione meno uno: le righe da 0 a 9, le colonne da 0 a 4. L’elemento in riga $i$ e colonna $j$ è a[i][j]. La dichiarazione int a[N][M] alloca $N \cdot M$ variabili intere, e il valore iniziale di ognuna è, al solito, indefinito.

Con una coppia di parentesi in più per ogni dimensione si dichiarano array a tre o più dimensioni: int a[10][5][20] ha $10 \cdot 5 \cdot 20 = 1000$ elementi.

Assegnazione (slide 58). Con int matrice[10][10];, l’istruzione matrice[2][4] = 12; assegna 12 al quinto elemento della terza riga: gli indici partono da 0.

Array di array. Il titolo delle slide 65-66 dice cosa è davvero una matrice in C: int a[4][5] è un array di 4 elementi, ognuno dei quali è un array di 5 int. a[1] è la seconda riga intera, e a[1][3] è il quarto elemento di quella riga. Per questo le quadre si scrivono separate (a[i][j], mai a[i, j]), e sizeof(a[0]) è la dimensione di una riga.

Disposizione in memoria (slide 56-57). Anche se accediamo agli elementi come a una tabella, la rappresentazione in memoria è lineare: il C memorizza le matrici una riga dopo l’altra (in inglese row-major order).

In una matrice con $M$ colonne, a[i][j] è la cella numero $i \cdot M + j$ contando da a[0][0]: prima ci sono $i$ righe complete da $M$ elementi, poi $j$ elementi della riga $i$. Per questo il compilatore deve conoscere il numero di colonne: senza $M$ non saprebbe dove comincia la riga $i$.

2Concetti

2.1Inizializzazione

(slide 55 e slide 59-64) Una matrice si inizializza con una lista di righe, ognuna fra graffe:

int a[4][5] = { {2, 5, -8, 7, 6},
                {3, 10, 7, 6, 1},
                {-1, 8, -8, 5, 3},
                {2, 5, 8, 4, 2} };

Le varianti della slide 64, con il motivo:

float A[3][2];                    3 righe, 2 colonne, valori indefiniti
int B[3][2] = {1,2,3,4,5,6};      lista piatta: riempie per righe, {1,2},{3,4},{5,6}
int C[2][3] = {{1,2,3},{4,5,6}};  una graffa per riga: la forma chiara
int D[][] = {1,2,3,4};            errore: mancano entrambe le dimensioni
int E[2][] = {1,2,3,4};           errore: manca il numero di colonne
int F[][2] = {1,2,3,4};           ok: 2 colonne, quindi 2 righe

La regola: si può omettere solo la prima dimensione, quella delle righe, che il compilatore deduce dal numero di valori. Il numero di colonne serve a sapere dove finisce ogni riga, come nella formula $i \cdot M + j$.

La lista piatta di B e F è C valido ma gcc con -Wall avvisa “missing braces around initializer”: meglio scrivere {{1, 2}, {3, 4}, {5, 6}}. Con le graffe per riga si può anche inizializzare in parte ogni riga: int m[2][3] = {{1}, {4, 5}}; dà le righe 1 0 0 e 4 5 0, perché le celle non elencate valgono 0, riga per riga.

#include <stdio.h>

#define RIGHE 4
#define COLONNE 5

int main(void)
{
    int a[RIGHE][COLONNE] = {
        {2, 5, -8, 7, 6},
        {3, 10, 7, 6, 1},
        {-1, 8, -8, 5, 3},
        {2, 5, 8, 4, 2}
    };
    int i;
    int j;

    for (i = 0; i < RIGHE; i++)
        for (j = 0; j < COLONNE; j++)
            printf("%d ", a[i][j]);
    printf("\n");
    printf("a[1][0] dista %d celle da a[0][0]\n", (int)(&a[1][0] - &a[0][0]));
    printf("a[2][3] dista %d celle da a[0][0]\n", (int)(&a[2][3] - &a[0][0]));
    printf("sizeof(a)=%zu sizeof(a[0])=%zu\n", sizeof(a), sizeof(a[0]));
    return 0;
}

Output (verificato, int da 4 byte):

2 5 -8 7 6 3 10 7 6 1 -1 8 -8 5 3 2 5 8 4 2 
a[1][0] dista 5 celle da a[0][0]
a[2][3] dista 13 celle da a[0][0]
sizeof(a)=80 sizeof(a[0])=20

La prima riga è la sequenza della slide 57, quella che sta in memoria. a[1][0] sta subito dopo a[0][4], 5 celle dopo l’inizio; a[2][3] sta alla cella $2 \cdot 5 + 3 = 13$. La differenza fra due indirizzi la vedremo con i puntatori: qui serve solo a mostrare la formula.

2.2Righe fuori, colonne dentro

Lo schema per visitare tutta una matrice è un for sulle righe che contiene un for sulle colonne. Il ciclo interno riparte da 0 a ogni riga, come in Cicli for e do-while. Per la stampa si va a capo dopo il ciclo interno, una volta per riga. In questo ordine si visitano le celle nello stesso ordine in cui stanno in memoria.

Scambiando i due cicli (colonne fuori, righe dentro) si visita la matrice per colonne: serve per le somme per colonna. Quello che non va scambiato sono i limiti: l’indice di riga va fino al numero di righe, quello di colonna fino al numero di colonne. Con una matrice non quadrata, confonderli scrive fuori.

3Metodo

Matrice m con R righe e C colonne (con #define); per le quadrate N.

Leggere (slide 65): due for, scanf("%d", &m[i][j]), controllando il ritorno.

Stampare (slide 66): due for, un printf per elemento con un separatore, printf("\n") dopo il for interno.

Somma per riga e per colonna: due array di accumulatori azzerati, somma_riga[R] e somma_colonna[C], riempiti nella stessa scansione: somma_riga[i] += m[i][j]; somma_colonna[j] += m[i][j];.

Diagonali (solo quadrate): la principale è m[i][i], la secondaria m[i][N - 1 - i]. Basta un ciclo, non due.

Parti della matrice quadrata, per la cella $(i, j)$:

j == i            diagonale principale
i + j == N - 1    diagonale secondaria
j > i             sopra la diagonale (triangolo superiore)
j < i             sotto la diagonale (triangolo inferiore)
i == 0, i == N-1  prima e ultima riga (bordo)

Sono le condizioni dei quadrati a pattern dello scritto.

Trasposta (slide 93-94): $A$ di $R \times C$ diventa $A^T$ di $C \times R$ con at[i][j] = a[j][i], i sulle righe di $A^T$ (da 0 a C) e j sulle sue colonne (da 0 a R). Sul posto, solo per le quadrate, si scambia m[i][j] con m[j][i] solo per j > i.

Verificare una proprietà “per ogni i, j” (simmetria, magia): una variabile flag a 1, la si mette a 0 al primo controllo che fallisce. Mettere && flag nella condizione dei cicli ferma la scansione appena si sa la risposta.

Contare le operazioni: un contatore incrementato accanto all’operazione (slide 71). Utile per confrontare due versioni dello stesso algoritmo, ed è l’idea che tornerà con la complessità.

4Esempi svolti a lezione

4.1Lettura e stampa di una matrice quadrata

(slide 65-68) Le slide 65-66 mostrano i due cicli, la 67 chiede un programma che legge una matrice quadrata da tastiera e la scrive su standard output, la 68 lo risolve.

#include <stdio.h>

#define N 3

int main(void)
{
    int matrice[N][N];
    int i;
    int j;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (scanf("%d", &matrice[i][j]) != 1) {
                printf("input non valido\n");
                return 1;
            }
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d", matrice[i][j]);
            if (j <= N - 2)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

Con input 1 2 3 4 5 6 7 8 9 (anche tutto su una riga) stampa (verificato):

1 2 3
4 5 6
7 8 9

L’if (j <= N - 2) mette lo spazio dopo ogni elemento tranne l’ultimo della riga ($j = N - 1$), così le righe non hanno spazi in fondo. Il programma legge per righe: scanf salta spazi e a capo, quindi il formato dell’input non conta, solo l’ordine.

Errori nelle slide: le 65-66 scrivono main(...) senza int davanti (l’int implicito non esiste più dal C99), usano le virgolette tipografiche e stampano con "%d" senza separatore, quindi i numeri si incollano. La soluzione della slide 68 dichiara int N=3; int matrice[N][N];: con N variabile è un VLA, non un array statico (vedi Array). Qui N è un #define.

4.2Matrice simmetrica, quattro versioni

(slide 69-73) Una matrice quadrata è simmetrica se $a_{ij} = a_{ji}$ per ogni $i, j$: ogni elemento è uguale al suo speculare rispetto alla diagonale principale. Gli esempi della slide 69:

 7  2  1 14        7 12  1 14
 2 13  3 11        2 13  8 11
 1  3 10  5       16  3 10  5
14 11  5  4        9  6 15  4
    sì                 no

Il prof costruisce la soluzione in quattro passi, ogni volta chiedendo “come possiamo fare meno confronti?”:

versione 0     due for completi; flag sim = 1, a 0 se m[i][j] != m[j][i]
versione 0.1   come la 0, più un contatore ContaIf dei confronti eseguiti
versione 1     && (sim == 1) nelle condizioni dei due for: ci si ferma alla prima differenza
versione 2     j parte da i+1: si guarda solo sopra la diagonale

Le tre versioni misurate sulle due matrici della slide:

#include <stdio.h>

#define N 4

int main(void)
{
    int mat[N][N] = {
        {7, 2, 1, 14},
        {2, 13, 3, 11},
        {1, 3, 10, 5},
        {14, 11, 5, 4}
    };
    int sim;
    int conta_if;
    int i;
    int j;

    sim = 1;
    conta_if = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            if (mat[i][j] != mat[j][i])
                sim = 0;
            conta_if++;
        }
    printf("versione 0.1: sim=%d confronti=%d\n", sim, conta_if);

    sim = 1;
    conta_if = 0;
    for (i = 0; i < N && sim == 1; i++)
        for (j = 0; j < N && sim == 1; j++) {
            if (mat[i][j] != mat[j][i])
                sim = 0;
            conta_if++;
        }
    printf("versione 1:   sim=%d confronti=%d\n", sim, conta_if);

    sim = 1;
    conta_if = 0;
    for (i = 0; i < N && sim == 1; i++)
        for (j = i + 1; j < N && sim == 1; j++) {
            if (mat[i][j] != mat[j][i])
                sim = 0;
            conta_if++;
        }
    printf("versione 2:   sim=%d confronti=%d\n", sim, conta_if);
    return 0;
}

Output con la matrice “sì” e con la “no” al posto di mat (verificati):

matrice sì                                matrice no
versione 0.1: sim=1 confronti=16          versione 0.1: sim=0 confronti=16
versione 1:   sim=1 confronti=16          versione 1:   sim=0 confronti=2
versione 2:   sim=1 confronti=6           versione 2:   sim=0 confronti=1

Perché:

• La 0.1 fa sempre $N^2 = 16$ confronti, anche dopo aver trovato la differenza. Ne fa di inutili: confronta m[i][i] con sé stesso, e ogni coppia due volte (m[0][1] con m[1][0] e poi m[1][0] con m[0][1]).
• La 1 si ferma appena sim diventa 0. Sulla “no” trova $7 = 7$ e poi $12 \neq 2$: 2 confronti. Su una simmetrica non guadagna niente, perché deve controllare tutto.
• La 2 toglie la diagonale e i doppioni: con j da i + 1 controlla solo il triangolo superiore, $N (N - 1) / 2 = 6$ confronti per $N = 4$. Sulla “no” il primo confronto è già $12 \neq 2$.

Le slide dichiarano int MatQuadra[5][5]; senza riempirla: il codice va completato con la lettura o con un’inizializzazione, come qui.

4.3Trasposta

(slide 93-94) La trasposta $A^T$ di una matrice $A$ di dimensioni $N \times M$ ha dimensioni $M \times N$ e $a^T_{ij} = a_{ji}$: le righe di $A$ diventano le colonne di $A^T$.

La soluzione della slide è

int m=30;n=20
int A[m][n], AT[n][m];
for(i=0;i<n;i++)
  for(j=0;j<m;j++)
     AT[i][j]=A[j][i];

con due errori di C: int m=30;n=20 dichiara solo m (serve la virgola, e manca il ; finale), e A[m][n] con m e n variabili è un VLA. La logica è giusta: i scorre le righe di $A^T$, che sono n, e j le sue colonne, che sono m. Versione completa su una $2 \times 3$:

#include <stdio.h>

#define N 2
#define M 3

int main(void)
{
    int a[N][M] = {
        {1, 2, 3},
        {4, 5, 6}
    };
    int at[M][N];
    int i;
    int j;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            at[i][j] = a[j][i];

    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++)
            printf("%d ", at[i][j]);
        printf("\n");
    }
    return 0;
}

Output (verificato):

1 4 
2 5 
3 6 

La prima riga di $A$, 1 2 3, è diventata la prima colonna di $A^T$.

4.4Matrici magiche

(slide 95-100) Una matrice quadrata è magica se la somma degli elementi di ogni riga, di ogni colonna e delle due diagonali è la stessa costante. È normale se contiene i numeri $1, 2, \ldots, n^2$ senza ripetizioni. In una magica normale la somma magica vale

perché la somma di tutti gli elementi è $1 + 2 + \ldots + n^2 = n^2 (n^2 + 1) / 2$, divisa in $n$ righe uguali. Per $n = 4$: $4 \cdot 17 / 2 = 34$.

L’esempio della slide 96, con righe, colonne e diagonali che danno 34:

 7 12  1 14
 2 13  8 11
16  3 10  5
 9  6 15  4

Il quadrato della facciata della Passione della Sagrada Familia (slide 95) ha somma 33 e ripete 10 e 14: è magico ma non normale, quindi la formula lì non vale.

L’esercizio della slide 99 chiede (a) un programma che verifichi se una matrice $N \times N$ è magica. La soluzione della slide 100 è uno pseudocodice che fa solo le righe e lascia colonne e diagonali. Completo:

#include <stdio.h>

#define N 4

int main(void)
{
    int m[N][N] = {
        {7, 12, 1, 14},
        {2, 13, 8, 11},
        {16, 3, 10, 5},
        {9, 6, 15, 4}
    };
    int magica = 1;
    int somma_magica = N * (N * N + 1) / 2;
    int somma;
    int i;
    int j;

    for (i = 0; i < N && magica; i++) {
        somma = 0;
        for (j = 0; j < N; j++)
            somma += m[i][j];
        if (somma != somma_magica)
            magica = 0;
    }
    for (j = 0; j < N && magica; j++) {
        somma = 0;
        for (i = 0; i < N; i++)
            somma += m[i][j];
        if (somma != somma_magica)
            magica = 0;
    }
    if (magica) {
        somma = 0;
        for (i = 0; i < N; i++)
            somma += m[i][i];
        if (somma != somma_magica)
            magica = 0;
    }
    if (magica) {
        somma = 0;
        for (i = 0; i < N; i++)
            somma += m[i][N - 1 - i];
        if (somma != somma_magica)
            magica = 0;
    }
    printf("somma magica %d: %s\n", somma_magica, magica ? "magica" : "non magica");
    return 0;
}

Stampa somma magica 34: magica; scambiando 15 e 4 nell’ultima riga stampa somma magica 34: non magica (verificati). La somma si azzera dentro il ciclo esterno, una volta per riga o colonna: azzerarla una volta sola prima dei cicli accumulerebbe tutte le righe. Come nella simmetrica, && magica nelle condizioni ferma il controllo al primo errore.

Lo pseudocodice della slide usa Boolean, che in C non esiste (si usa un int 0/1, oppure bool da <stdbool.h>), scrive if Somma != MagicSum senza parentesi e dichiara M[n][n] con n variabile. Il programma confronta le somme con quella delle magiche normali, $n (n^2 + 1) / 2$. Ogni magica normale passa il test, ma per dire che la matrice è normale bisognerebbe anche controllare che ogni numero da 1 a $n^2$ compaia una volta sola. Il quadrato della Sagrada Familia, magico con somma 33, risulterebbe “non magica”: per le magiche qualsiasi il confronto va fatto con la somma della prima riga.

5Esercizi tipo esame

Esercizio 1. Scrivi l’output esatto.

#include <stdio.h>

#define N 3

int main(void)
{
    int m[N][N];
    int i;
    int j;
    int traccia = 0;
    int sotto = 0;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            m[i][j] = i * N + j;
    for (i = 0; i < N; i++) {
        traccia += m[i][i];
        for (j = 0; j < i; j++)
            sotto += m[i][j];
    }
    printf("m[2][1]=%d traccia=%d sotto=%d\n", m[2][1], traccia, sotto);
    return 0;
}

0 1 2
3 4 5
6 7 8

Esercizio 2. Scrivi l’output esatto.

#include <stdio.h>

int main(void)
{
    int m[2][3] = {{1}, {4, 5}};
    int i;
    int j;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++)
            printf("%d ", m[i][j]);
        printf("\n");
    }
    return 0;
}

1 0 0 
4 5 0 

Esercizio 3. Con int a[6][8], in che posizione lineare (contando da 0) sta a[3][5]? Quanti byte occupa a con int da 4 byte? Quale di queste dichiarazioni è valida: int x[][8] = {...}, int y[6][] = {...}?

Esercizio 4. Scrivi un programma che, data una matrice $3 \times 4$, stampa la somma di ogni riga e di ogni colonna con una sola scansione.

#include <stdio.h>

#define RIGHE 3
#define COLONNE 4

int main(void)
{
    int m[RIGHE][COLONNE] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    int somma_riga[RIGHE] = {0};
    int somma_colonna[COLONNE] = {0};
    int i;
    int j;

    for (i = 0; i < RIGHE; i++)
        for (j = 0; j < COLONNE; j++) {
            somma_riga[i] += m[i][j];
            somma_colonna[j] += m[i][j];
        }
    for (i = 0; i < RIGHE; i++)
        printf("riga %d: %d\n", i, somma_riga[i]);
    for (j = 0; j < COLONNE; j++)
        printf("colonna %d: %d\n", j, somma_colonna[j]);
    return 0;
}

Esercizio 5. Il programma vuole trasporre sul posto una matrice $3 \times 3$ ma la stampa resta identica a quella di partenza. Perché? Correggilo.

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) {
        tmp = m[i][j];
        m[i][j] = m[j][i];
        m[j][i] = tmp;
    }

#include <stdio.h>

#define N 3

int main(void)
{
    int m[N][N] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int i;
    int j;
    int tmp;

    for (i = 0; i < N; i++)
        for (j = i + 1; j < N; j++) {
            tmp = m[i][j];
            m[i][j] = m[j][i];
            m[j][i] = tmp;
        }
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf("%d ", m[i][j]);
        printf("\n");
    }
    return 0;
}

Esercizio 6. Scrivi l’output esatto per $N = 5$.

#include <stdio.h>

#define N 5

int main(void)
{
    char q[N][N];
    int i;
    int j;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (i == j || i + j == N - 1)
                q[i][j] = 'X';
            else if (i == 0 || i == N - 1)
                q[i][j] = '-';
            else
                q[i][j] = '.';
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            putchar(q[i][j]);
        putchar('\n');
    }
    return 0;
}

X---X
.X.X.
..X..
.X.X.
X---X

Esercizio 7. Trova l’errore. int m[2][3]; e poi:

for (i = 0; i < 3; i++)
    for (j = 0; j < 2; j++)
        m[i][j] = 0;

Esercizio 8. (Slide 99, punto b.) Data una matrice magica $M$ di $N \times N$, sapresti calcolarne altre a partire da $M$? Quante?

6Errori tipici

• Scrivere a[i, j] invece di a[i][j]: in C la virgola è l’operatore virgola, a[i, j] vale a[j], cioè una riga intera.
• Scambiare i limiti dei due cicli su una matrice non quadrata: si scrive fuori e si lascia una parte non visitata.
• Omettere il numero di colonne nell’inizializzazione (int E[2][]): si può omettere solo la prima dimensione.
• Credere che {{1}, {4, 5}} e {1, 4, 5} diano la stessa matrice.
• Andare a capo dentro il ciclo interno della stampa (una riga per elemento) o mai (tutto su una riga).
• Azzerare un accumulatore di riga una volta sola, prima dei cicli, invece che a ogni riga.
• Trasporre sul posto con j da 0: ogni scambio viene fatto due volte e la matrice non cambia.
• Controllare una proprietà “per ogni $i, j$” mettendo il flag a 1 anche quando il confronto riesce: un solo confronto riuscito cancellerebbe un fallimento precedente. Il flag si mette solo a 0.
• Dichiarare int N = 3; int m[N][N]; come nella slide 68: è un VLA. Per le dimensioni fisse, #define.

7Domande

• Cosa dichiara int a[10][5]? Quali sono gli indici validi e quanti elementi ci sono?

• Come è disposta in memoria una matrice in C? In che posizione lineare sta a[i][j] se la matrice ha $M$ colonne?

• Perché nell’inizializzazione si può omettere il numero di righe ma non quello di colonne?

• Cosa contiene int B[3][2] = {1,2,3,4,5,6};? E int m[2][3] = {{1}, {4, 5}};?

• Quale elemento viene assegnato da matrice[2][4] = 12;?

• Qual è lo schema di cicli per stampare una matrice riga per riga? Dove si mette il printf("\n")?

• Quando una matrice quadrata è simmetrica? Quanti confronti servono al minimo per verificarlo su una $N \times N$, e perché?

• Cosa cambia fra la versione 1 e la versione 2 della verifica di simmetria?

• Come si calcola la trasposta di una matrice $N \times M$? Come si fa sul posto, e perché solo per $j > i$?

• Quando una matrice è magica? Perché la somma magica di una normale è $n (n^2 + 1) / 2$?

• Come si individuano, con una condizione su $i$ e $j$, la diagonale principale, la secondaria e il triangolo sotto la diagonale?