Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
ott, giorno?
in corso

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. Dopo: Stringhe.

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 ii e colonna jj è a[i][j]: prima la riga, poi la colonna, come nelle matrici della matematica (aija_{ij}). La dichiarazione int a[N][M] alloca N⋅MN \cdot M variabili intere, e il valore iniziale di ognuna è, al solito, indefinito.

L’intuizione: una tabella, o un foglio a quadretti. Il primo indice dice su quale riga scendere, il secondo di quante caselle spostarsi a destra. Serve ogni volta che i dati hanno due coordinate: una scacchiera, i voti di 30 studenti in 6 esami, i pixel di un’immagine.

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⋅5⋅20=100010 \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 MM colonne, a[i][j] è la cella numero i⋅M+ji \cdot M + j contando da a[0][0]: prima ci sono ii righe complete da MM elementi, poi jj elementi della riga ii. Per questo il compilatore deve conoscere il numero di colonne: senza MM non saprebbe dove comincia la riga ii.

Due esempi della formula, dal più semplice:

Per tre dimensioni la regola si estende: in int c[10][5][20] la cella c[i][j][k] è la numero (i⋅5+j)⋅20+k(i \cdot 5 + j) \cdot 20 + k. Si omette solo la prima dimensione, di nuovo.

Esempio 1, indici calcolati in una matrice 3×43 \times 4:

#include <stdio.h>

#define R 3
#define C 4

int main(void)
{
    int m[R][C];
    int i;
    int j;

    for (i = 0; i < R; i++)
        for (j = 0; j < C; j++)
            m[i][j] = 10 * i + j;
    printf("%d %d %d\n", m[1][2], m[2][0], m[R - 1][C - 1]);
    i = 1;
    j = 3;
    m[i + 1][j - 2] = m[i][j] + m[i - 1][j - 3];
    printf("%d\n", m[2][1]);
    return 0;
}

Con 10 * i + j ogni cella contiene “riga e colonna” lette come un numero di due cifre:

 0  1  2  3
10 11 12 13
20 21 22 23

La riga m[i + 1][j - 2] = m[i][j] + m[i - 1][j - 3]; con i=1i = 1, j=3j = 3:

a sinistra    m[1 + 1][3 - 2]   cioè m[2][1]
a destra      m[1][3] + m[0][0]  cioè 13 + 0 = 13

Output (verificato): 12 20 23, poi 13. Il vecchio valore di m[2][1] (21) è sovrascritto.

Esempio 2, la stessa matrice visitata con un solo indice kk che scorre le celle in ordine di memoria. Riga e colonna si ricavano con la divisione: i=k/Ci = k / C, j=k%Cj = k \% C (è la formula k=i⋅C+jk = i \cdot C + j letta al contrario).

#include <stdio.h>

#define R 3
#define C 4

int main(void)
{
    int m[R][C];
    int k;
    int i;
    int j;

    for (k = 0; k < R * C; k++)
        m[k / C][k % C] = k % 5;
    for (j = 0; j < C; j++) {
        for (i = 0; i < R; i++)
            printf("%d", m[i][j]);
        printf(" ");
    }
    printf("\n%d\n", m[2][1] + m[1][2]);
    return 0;
}
k01234567891011
cella[0][0][0][1][0][2][0][3][1][0][1][1][1][2][1][3][2][0][2][1][2][2][2][3]
k % 5012340123401

La matrice risultante:

0 1 2 3
4 0 1 2
3 4 0 1

La stampa ha le colonne fuori e le righe dentro, quindi stampa una colonna alla volta: 043 104 210 321 . Poi m[2][1] + m[1][2] =4+1=5= 4 + 1 = 5. Output (verificato):

043 104 210 321 
5

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 delle slide 59-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⋅M+ji \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. La lista piatta {1, 4, 5} darebbe invece 1 4 5 e 0 0 0. int z[3][3] = {{0}}; azzera tutto.

#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: il printf("\n") è fuori da tutti e due i cicli, quindi la matrice esce su una riga sola. a[1][0] sta subito dopo a[0][4], 5 celle dopo l’inizio; a[2][3] sta alla cella 2⋅5+3=132 \cdot 5 + 3 = 13. sizeof(a) è 4⋅5⋅4=804 \cdot 5 \cdot 4 = 80 byte, sizeof(a[0]) una riga da 5 int, 20 byte. 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.

for (i = 0; i < R; i++) {          per ogni riga
    for (j = 0; j < C; j++)        per ogni colonna di quella riga
        ...m[i][j]...
    printf("\n");                  fine riga
}

Scambiando i due cicli (colonne fuori, righe dentro) si visita la matrice per colonne, come nell’Esempio 2. 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.

Esempio, somme per riga e per colonna nella stessa scansione. Due array di accumulatori, uno per riga e uno per colonna:

#include <stdio.h>

#define R 3
#define C 4

int main(void)
{
    int m[R][C] = {
        {3, 0, 2, 5},
        {1, 4, 0, 2},
        {6, 1, 3, 0}
    };
    int somma_riga[R] = {0};
    int somma_colonna[C] = {0};
    int i;
    int j;

    for (i = 0; i < R; i++)
        for (j = 0; j < C; j++) {
            somma_riga[i] += m[i][j];
            somma_colonna[j] += m[i][j];
        }
    for (i = 0; i < R; i++)
        printf("%d ", somma_riga[i]);
    printf("| ");
    for (j = 0; j < C; j++)
        printf("%d ", somma_colonna[j]);
    printf("\n");
    return 0;
}

Gli accumulatori dopo ogni riga (giro del ciclo esterno):

dopo la rigasomma_rigasomma_colonna
0 (3 0 2 5)10 0 03 0 2 5
1 (1 4 0 2)10 7 04 4 2 7
2 (6 1 3 0)10 7 1010 5 5 7

Output: 10 7 10 | 10 5 5 7 (verificato). Controllo: 10+7+10=27=10+5+5+710 + 7 + 10 = 27 = 10 + 5 + 5 + 7, la somma di tutta la matrice contata in due modi.

2.3Diagonali, triangoli e bordo

Nelle matrici quadrate (N×NN \times N) la posizione di una cella rispetto alle diagonali si legge da una condizione su ii e jj. Sono le stesse condizioni dei quadrati a pattern della teorica.

j == i                        diagonale principale (da in alto a sinistra)
i + j == N - 1                diagonale secondaria (da in alto a destra)
j > i                         sopra la principale (triangolo superiore)
j < i                         sotto la principale (triangolo inferiore)
i == 0 || i == N - 1          prima e ultima riga
j == 0 || j == N - 1          prima e ultima colonna

Perché la secondaria è i+j=N−1i + j = N - 1: scendendo di una riga ci si sposta di una colonna a sinistra, quindi la somma resta costante; nella prima riga la cella è all’ultima colonna, 0+(N−1)0 + (N - 1).

Le diagonali hanno NN celle, quindi si sommano con un ciclo solo: m[i][i] e m[i][N - 1 - i]. I triangoli invece hanno bisogno di due cicli.

#include <stdio.h>

#define N 4

int main(void)
{
    int m[N][N] = {
        {5, 1, 0, 2},
        {3, 6, 1, 0},
        {0, 2, 7, 4},
        {1, 0, 3, 8}
    };
    int princ = 0;
    int sec = 0;
    int sopra = 0;
    int sotto = 0;
    int i;
    int j;

    for (i = 0; i < N; i++) {
        princ += m[i][i];
        sec += m[i][N - 1 - i];
    }
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (j > i)
                sopra += m[i][j];
            else if (j < i)
                sotto += m[i][j];
    printf("principale=%d secondaria=%d sopra=%d sotto=%d\n", princ, sec, sopra, sotto);
    return 0;
}
im[i][i]N - 1 - im[i][N - 1 - i]sopra (j > i)sotto (j < i)
05321 + 0 + 2 = 3nessuna
16211 + 0 = 13
271240 + 2 = 2
3801nessuna1 + 0 + 3 = 4
totale26689

Output: principale=26 secondaria=6 sopra=8 sotto=9 (verificato). Controllo: 26+8+9=4326 + 8 + 9 = 43, la somma di tutta la matrice (la diagonale principale, più i due triangoli, copre ogni cella una volta sola).

2.4Quadrati a pattern senza matrice

La domanda che esce più spesso con due cicli: stampare un disegno N×NN \times N senza usare una matrice. Non serve memorizzare niente: per ogni cella (i,j)(i, j), nell’ordine di stampa, si decide quale carattere stampare con una condizione su ii e jj. La matrice c’è solo nella testa.

for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++)
        if (condizione su i, j) stampa A
        else stampa B
    a capo
}

Esempio 1, cifre sopra la diagonale e spazi sotto, con N=4N = 4:

#include <stdio.h>

#define N 4

int main(void)
{
    int i;
    int j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            if (j < i)
                printf(" ");
            else
                printf("%d", j - i);
        printf("\n");
    }
    return 0;
}
ij = 0123riga stampata
001230123
1spazio012 012
2spaziospazio01 01
3spaziospaziospazio0 0

Output (verificato):

0123
 012
  01
   0

j - i è la distanza dalla diagonale: 0 sulla diagonale, cresce andando a destra.

Esempio 2, cornice con la diagonale, N=5N = 5. Con più regioni l’ordine degli if decide chi vince sulle celle che stanno in due regioni:

#include <stdio.h>

#define N 5

int main(void)
{
    int i;
    int j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (i == 0 || i == N - 1 || j == 0 || j == N - 1)
                putchar('#');
            else if (i == j)
                putchar('\\');
            else
                putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}

Output (verificato):

#####
#\  #
# \ #
#  \#
#####

Gli angoli (0, 0) e (4, 4) sono sia sul bordo sia sulla diagonale: il bordo è controllato per primo, quindi lì c’è #. Il carattere backslash in C si scrive '\\', perché \ da solo inizia una sequenza di escape.

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];. Se serve una riga alla volta (per confrontarla subito, come nella magica), un solo accumulatore azzerato dentro il ciclo esterno.

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

Quadrato a pattern (teorica): disegna la griglia N×NN \times N con gli indici, scrivi per ogni carattere la condizione su ii e jj (tabella sopra), ordina gli if dal caso più specifico (o da quello che deve vincere sugli incroci) al più generale, \n dopo il ciclo interno. Controlla con NN piccolo (3 o 4) cella per cella.

Trasposta (slide 93-94): AA di R×CR \times C diventa ATA^T di C×RC \times R con at[i][j] = a[j][i], i sulle righe di ATA^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.

Rotazione di 90° in senso orario (quadrate): la riga ii diventa la colonna N−1−iN - 1 - i, quindi r[j][N - 1 - i] = m[i][j] in una seconda matrice.

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à.

Tracciare un programma con matrici: disegna la griglia con gli indici di riga a sinistra e di colonna sopra; per ogni m[espr1][espr2] calcola prima i due indici, controlla che stiano nei limiti (riga < R, colonna < C), poi scrivi nella casella. Per la stampa, guarda quale ciclo è fuori: righe fuori stampa per righe, colonne fuori stampa per colonne.

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 la lettura riempie le celle in quest’ordine:

letto123456789
cella[0][0][0][1][0][2][1][0][1][1][1][2][2][0][2][1][2][2]

e la stampa dà (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=2j = N - 1 = 2), 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 (anche tutto su una riga), 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 aij=ajia_{ij} = a_{ji} per ogni i,ji, 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

Nella “no” basta guardare la prima riga e la prima colonna: m[0][1] vale 12, m[1][0] vale 2.

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

Tracing della versione 1 sulla “no”:

ijsim == 1confrontosimconta_if
00sìm[0][0] = 7 con m[0][0] = 7, uguali11
01sìm[0][1] = 12 con m[1][0] = 2, diversi02
02noil for interno esce02
1noanche l’esterno esce02

Tracing della versione 2 sulla “sì”: j parte da i + 1, quindi si visitano solo le celle sopra la diagonale.

ivalori di jcoppie confrontateconta_if dopo
01, 2, 3(0,1)-(1,0): 2 = 2; (0,2)-(2,0): 1 = 1; (0,3)-(3,0): 14 = 143
12, 3(1,2)-(2,1): 3 = 3; (1,3)-(3,1): 11 = 115
23(2,3)-(3,2): 5 = 56
3nessuno (j parte da 4)6

Perché i numeri cambiano:

Le slide dichiarano int MatQuadra[5][5]; senza riempirla: il codice va completato con la lettura o con un’inizializzazione, come qui. Con N=5N = 5 la versione 2 farebbe 5⋅4/2=105 \cdot 4 / 2 = 10 confronti contro 25.

4.3Trasposta

(slide 93-94) La trasposta ATA^T di una matrice AA di dimensioni N×MN \times M ha dimensioni M×NM \times N e aijT=ajia^T_{ij} = a_{ji}: le righe di AA diventano le colonne di ATA^T. L’intuizione: si ribalta la tabella attorno alla diagonale principale.

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 ATA^T, che sono n, e j le sue colonne, che sono m. Versione completa su una 2×32 \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;
}
ijat[i][j] = a[j][i]
00at[0][0] = a[0][0] = 1
01at[0][1] = a[1][0] = 4
10at[1][0] = a[0][1] = 2
11at[1][1] = a[1][1] = 5
20at[2][0] = a[0][2] = 3
21at[2][1] = a[1][2] = 6

Output (verificato):

1 4 
2 5 
3 6 

La prima riga di AA, 1 2 3, è diventata la prima colonna di ATA^T. Controllo: i limiti dei cicli sono quelli di at (3 righe, 2 colonne), e gli indici di a sono scambiati, quindi a[j][i] ha riga j < 2 e colonna i < 3: sempre dentro.

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,…,n21, 2, \ldots, n^2 senza ripetizioni. In una magica normale la somma magica vale

n(n2+1)2\frac{n (n^2 + 1)}{2}

perché la somma di tutti gli elementi è 1+2+…+n2=n2(n2+1)/21 + 2 + \ldots + n^2 = n^2 (n^2 + 1) / 2, divisa in nn righe uguali. Per n=3n = 3: 3⋅10/2=153 \cdot 10 / 2 = 15. Per n=4n = 4: 4⋅17/2=344 \cdot 17 / 2 = 34.

L’esempio della slide 96, con righe, colonne e diagonali che danno 34 (slide 97-98):

 7 12  1 14
 2 13  8 11
16  3 10  5
 9  6 15  4
somme
righe7+12+1+147 + 12 + 1 + 14, 2+13+8+112 + 13 + 8 + 11, 16+3+10+516 + 3 + 10 + 5, 9+6+15+49 + 6 + 15 + 4: tutte 34
colonne7+2+16+97 + 2 + 16 + 9, 12+13+3+612 + 13 + 3 + 6, 1+8+10+151 + 8 + 10 + 15, 14+11+5+414 + 11 + 5 + 4: tutte 34
principale7+13+10+4=347 + 13 + 10 + 4 = 34
secondaria14+8+3+9=3414 + 8 + 3 + 9 = 34

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×NN \times N è magica, e (b) se da una magica se ne possono ricavare altre, e quante. La (b) è svolta nell’esercizio 13 di Matrici e array multidimensionali (esercizi). La soluzione della slide 100 per la (a) è 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 (verificato): tutte e dieci le somme della tabella sopra valgono 34. Scambiando 15 e 4 nell’ultima riga (9 6 4 15) stampa somma magica 34: non magica (verificato). Tracing di quel caso:

controllosommamagica
righe 0-234, 34, 341
riga 3: 9+6+4+159 + 6 + 4 + 15341 (le righe non se ne accorgono)
colonna 0: 7+2+16+97 + 2 + 16 + 9341
colonna 1: 12+13+3+612 + 13 + 3 + 6341
colonna 2: 1+8+10+41 + 8 + 10 + 4230
colonna 3, diagonalinon calcolate (&& magica e if (magica))0

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(n2+1)/2n (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 n2n^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

In una pagina a parte, dal più facile al livello del 30: Matrici e array multidimensionali (esercizi).

6Errori tipici

7Domande