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 e colonna è a[i][j]: prima la riga, poi la colonna, come nelle matrici della matematica (). La dichiarazione int a[N][M] alloca 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 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 colonne, a[i][j] è la cella numero contando da a[0][0]: prima ci sono righe complete da elementi, poi elementi della riga . Per questo il compilatore deve conoscere il numero di colonne: senza non saprebbe dove comincia la riga .
Due esempi della formula, dal più semplice:
int a[4][5], cellaa[2][3]: . Il numero di righe (4) non entra nel conto.int b[6][8], cellab[5][7], l’ultima: , come deve essere per l’ultima di 48 celle. Controesempio:b[3][9]darebbe , la stessa cella dib[4][1]. Il C non controlla che la colonna sia minore di 8: con una colonna fuori range si finisce nella riga successiva (formalmente è comportamento indefinito).
Per tre dimensioni la regola si estende: in int c[10][5][20] la cella c[i][j][k] è la numero . Si omette solo la prima dimensione, di nuovo.
Esempio 1, indici calcolati in una matrice :
#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 , :
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 che scorre le celle in ordine di memoria. Riga e colonna si ricavano con la divisione: , (è la formula 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;
}
k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 % 5 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
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] . 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 .
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 . sizeof(a) è 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 riga | somma_riga | somma_colonna |
|---|---|---|
0 (3 0 2 5) | 10 0 0 | 3 0 2 5 |
1 (1 4 0 2) | 10 7 0 | 4 4 2 7 |
2 (6 1 3 0) | 10 7 10 | 10 5 5 7 |
Output: 10 7 10 | 10 5 5 7 (verificato). Controllo: , la somma di tutta la matrice contata in due modi.
2.3Diagonali, triangoli e bordo
Nelle matrici quadrate () la posizione di una cella rispetto alle diagonali si legge da una condizione su e . 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 è : 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, .
Le diagonali hanno 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;
}
i | m[i][i] | N - 1 - i | m[i][N - 1 - i] | sopra (j > i) | sotto (j < i) |
|---|---|---|---|---|---|
| 0 | 5 | 3 | 2 | 1 + 0 + 2 = 3 | nessuna |
| 1 | 6 | 2 | 1 | 1 + 0 = 1 | 3 |
| 2 | 7 | 1 | 2 | 4 | 0 + 2 = 2 |
| 3 | 8 | 0 | 1 | nessuna | 1 + 0 + 3 = 4 |
| totale | 26 | 6 | 8 | 9 |
Output: principale=26 secondaria=6 sopra=8 sotto=9 (verificato). Controllo: , 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 senza usare una matrice. Non serve memorizzare niente: per ogni cella , nell’ordine di stampa, si decide quale carattere stampare con una condizione su e . 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 :
#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;
}
i | j = 0 | 1 | 2 | 3 | riga stampata |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 0123 |
| 1 | spazio | 0 | 1 | 2 | 012 |
| 2 | spazio | spazio | 0 | 1 | 01 |
| 3 | spazio | spazio | spazio | 0 | 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, . 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 con gli indici, scrivi per ogni carattere la condizione su e (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 piccolo (3 o 4) cella per cella.
Trasposta (slide 93-94): di diventa di con at[i][j] = a[j][i], i sulle righe di (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 diventa la colonna , 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:
| letto | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 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 (), 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 per ogni : 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”:
i | j | sim == 1 | confronto | sim | conta_if |
|---|---|---|---|---|---|
| 0 | 0 | sì | m[0][0] = 7 con m[0][0] = 7, uguali | 1 | 1 |
| 0 | 1 | sì | m[0][1] = 12 con m[1][0] = 2, diversi | 0 | 2 |
| 0 | 2 | no | il for interno esce | 0 | 2 |
| 1 | no | anche l’esterno esce | 0 | 2 |
Tracing della versione 2 sulla “sì”: j parte da i + 1, quindi si visitano solo le celle sopra la diagonale.
i | valori di j | coppie confrontate | conta_if dopo |
|---|---|---|---|
| 0 | 1, 2, 3 | (0,1)-(1,0): 2 = 2; (0,2)-(2,0): 1 = 1; (0,3)-(3,0): 14 = 14 | 3 |
| 1 | 2, 3 | (1,2)-(2,1): 3 = 3; (1,3)-(3,1): 11 = 11 | 5 |
| 2 | 3 | (2,3)-(3,2): 5 = 5 | 6 |
| 3 | nessuno (j parte da 4) | 6 |
Perché i numeri cambiano:
- La 0.1 fa sempre 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]conm[1][0]e poim[1][0]conm[0][1]). - La 1 si ferma appena
simdiventa 0. Sulla “no” trova e poi : 2 confronti. Su una simmetrica non guadagna niente, perché deve controllare tutto. - La 2 toglie la diagonale e i doppioni: con
jdai + 1controlla solo il triangolo superiore, confronti per (). Sulla “no” il primo confronto è già .
Le slide dichiarano int MatQuadra[5][5]; senza riempirla: il codice va completato con la lettura o con un’inizializzazione, come qui. Con la versione 2 farebbe confronti contro 25.
4.3Trasposta
(slide 93-94) La trasposta di una matrice di dimensioni ha dimensioni e : le righe di diventano le colonne di . 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 , che sono n, e j le sue colonne, che sono m. Versione completa su una :
#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;
}
i | j | at[i][j] = a[j][i] |
|---|---|---|
| 0 | 0 | at[0][0] = a[0][0] = 1 |
| 0 | 1 | at[0][1] = a[1][0] = 4 |
| 1 | 0 | at[1][0] = a[0][1] = 2 |
| 1 | 1 | at[1][1] = a[1][1] = 5 |
| 2 | 0 | at[2][0] = a[0][2] = 3 |
| 2 | 1 | at[2][1] = a[1][2] = 6 |
Output (verificato):
1 4
2 5
3 6
La prima riga di , 1 2 3, è diventata la prima colonna di . 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 senza ripetizioni. In una magica normale la somma magica vale
perché la somma di tutti gli elementi è , divisa in righe uguali. Per : . Per : .
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 | |
|---|---|
| righe | , , , : tutte 34 |
| colonne | , , , : tutte 34 |
| principale | |
| secondaria |
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 è 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:
| controllo | somma | magica |
|---|---|---|
| righe 0-2 | 34, 34, 34 | 1 |
| riga 3: | 34 | 1 (le righe non se ne accorgono) |
| colonna 0: | 34 | 1 |
| colonna 1: | 34 | 1 |
| colonna 2: | 23 | 0 |
| colonna 3, diagonali | non 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, . Ogni magica normale passa il test, ma per dire che la matrice è normale bisognerebbe anche controllare che ogni numero da 1 a 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
- Scrivere
a[i, j]invece dia[i][j]: in C la virgola è l’operatore virgola,a[i, j]valea[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.
- Usare una colonna fuori range credendo di avere un errore:
b[3][9]in una matrice da 8 colonne finisce in silenzio inb[4][1]. - 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.
- Sommare una diagonale con due cicli annidati e un
if (i == j): funziona, ma fa giri invece di . - Scrivere la diagonale secondaria come
i <mark> N - jinvece dii + j </mark> N - 1: è spostata di una colonna e alla prima riga cercaj == N, fuori. - Nei quadrati a pattern, ordinare gli
ifsenza pensare agli incroci (angoli, centro): vince il primo controllo vero. - Trasporre sul posto con
jda 0: ogni scambio viene fatto due volte e la matrice non cambia. - Controllare una proprietà “per ogni ” 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 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};? Eint 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 , e perché?
-
Cosa cambia fra la versione 1 e la versione 2 della verifica di simmetria?
-
Come si calcola la trasposta di una matrice ? Come si fa sul posto, e perché solo per ?
-
Quando una matrice è magica? Perché la somma magica di una normale è ?
-
Come si individuano, con una condizione su e , la diagonale principale, la secondaria e il triangolo sotto la diagonale?
-
Cosa vuol dire
a[1]seaèint a[4][5]? Quanto valesizeof(a[1])? -
Dato l’indice lineare di una cella in una matrice con colonne, come si ricavano riga e colonna?
-
Come si stampa un quadrato a pattern senza usare una matrice?
-
Perché per sommare una diagonale basta un ciclo solo?