Corso di Algoritmi e Strutture Dati
APPUNTI SUL LINGUAGGIO C
Matrici
Matrici
• Sono array bidimensionali
• Una matrice M ha due campi
– Numero di righe: rows[M]
– Numero di colonne: columns[M]
• Ogni elemento nella matrice M[i,j] ha un indice di riga
i e colonna j
Matrici in C
Matrici in C
Allochiamo in modo dinamico una matrice: scriviamo un metodo
“leggi” che allochi in memoria una matrice di interi M di n righe
e m colonne (input) e la riempi facendosi passare gli elementi
da tastiera.
int** M; int i,j;
M = (int**)calloc(n,sizeof(int*));
for (i=0; i<n; i++)
M[i] = (int*)calloc(m,sizeof(int));
Matrici in C
Allochiamo in modo dinamico una matrice: scriviamo un metodo
“leggi” che allochi in memoria una matrice di interi M di n righe
e m colonne (input) e la riempi facendosi passare gli elementi
da tastiera.
int** leggi(int n, int m){
int** M; int i,j;
M = (int**)calloc(n,sizeof(int*));
for (i=0; i<n; i++)
M[i] = (int*)calloc(m,sizeof(int));
for (i=0; i<n; i++)
for (j=0; j<m; j++)
scanf("%d",&M[i][j]);
return M;
}
Trasposta di una matrice
Data una matrice M[n x m], la sua trasposta T[m x n] è
ottenuta scambiando le righe con le colonne di M.
Trasposta(M)
for i <- 1 to columns[M] do
for j <- 1 to rows[M] do
T[i,j] <- M[j,i]
return T
Trasposta di una matrice
Data una matrice M[n x m], la sua trasposta T[m x n] è
ottenuta scambiando le righe con le colonne di M.
int** trasposta(int** M, int n, int m){
int** T; int i,j;
T = (int**)calloc(m,sizeof(int*));
for (i=0; i<m; i++)
T[i] = (int*)calloc(n,sizeof(int));
for (i=0; i<m; i++)
for (j=0; j<n; j++)
T[i][j] = M[j][i];
return T;
}
Somma di due matrici
Date due matrici M1[n x m] e M2[n x m], calcolare la
matrice somma M3[n x m]
Somma(M1,M2)
for i <- 1 to rows[M] do
for j <- 1 to columns[M] do
M3[i,j] <- M1[i,j] + M2[i,j]
return M3
Somma di due matrici
Date due matrici M1[n x m] e M2[n x m], calcolare la
matrice somma M3[n x m]
int** somma(int** M1, int n, int m, int** M2){
int** M3; int i,j;
M3 = (int**)calloc(n,sizeof(int*));
for (i=0; i<n; i++)
M3[i] = (int*)calloc(m,sizeof(int));
for (i=0; i<n; i++)
for (j=0; j<m; j++)
M3[i][j] = M1[i][j] + M2[i][j];
return M3;
}
Triangolare Superiore
Data una matrice M1[n x n], calcolare la matrice S[n x
n], tale per cui la matrice M2=M1-S sia triangolare
superiore
triangolare(M1)
for i <- 1 to rows[M1] do
for j <- 1 to i-1 do
S[i,j] <- - M1[i,j]
for i <- 1 to rows[M1] do
for j <- 1 to columns[M1] do
S[i,j] <- 0
return S
Triangolare Superiore
int** TriangSup(int** M, int n){
int** T; int i,j;
T = (int**)calloc(n,sizeof(int*));
for (i=0; i<n; i++)
T[i] = (int*)calloc(n,sizeof(int));
for (i=1; i<n; i++)
for (j=0; j<=i-1; j++)
T[i][j] = 0 - M[i][j];
for (i=0; i<n; i++)
for (j=i; j<n; j++)
T[i][j] = 0;
return T;
}
Prodotto tra matrici
Date due matrici M1[n x k] e M2[k x m], calcolare la
matrice prodotto M3[n x m]
prodotto(M1,M2)
for i <- 1 to rows[M1] do
for j <- 1 to columns[M2] do
p <- 0
for s <- 1 to rows[M2] do
p <- p + (M1[i,s] + M2[s,j])
M3[i,j] <- p
return M3
Prodotto tra matrici
int** Prodotto(int** M1, int n, int k, int** M2, int m){
int** T; int i,j,s,p;
T = (int**)calloc(n,sizeof(int*));
for (i=0; i<n; i++)
T[i] = (int*)calloc(m,sizeof(int));
for (i=0; i<n; i++)
for (j=0; j<m; j++) {
p = 0;
for (s=0; s<k; s++)
p = p + (M1[i][s] * M2[s][j]);
T[i][j] = p;
}
return T;
}
Matrice rigata crescente
Data una matrice M[n x m], verificare se questa è rigata crescente:
la somma degli elementi di una riga i è minore o uguale della
somma degli elementi della riga i+1, per ogni i
crescente(M,i,somma,n,m)
if (i>n) then return true
else
s <- SUM(M[i],m);
return (s > somma) and crescente(M,i+1,s)
Matrice rigata crescente
Data una matrice M[n x m], verificare se questa è rigata crescente:
la somma degli elementi di una riga i è minore o uguale della
somma degli elementi della riga i+1, per ogni i
SUM(M,m)
s <- 0
for i <- 1 to m do s <- s + M[i]
return s
rigata(M,n,m)
return crescente(M,1,SUM(M[0],m),n,m)
Matrice rigata crescente
Data una matrice M[n x m], verificare se questa è rigata crescente:
la somma degli elementi di una riga i è minore o uguale della
somma degli elementi della riga i+1, per ogni i
int crescente(int** M, int i, int somma, int n, int m){
int s;
if (i >= n) return 1;
else {
s = SUM(M[i],m); i++;
return ((s > somma) && crescente(M,i,s,n,m));
}
}
Matrice rigata crescente
Data una matrice M[n x m], verificare se questa è rigata crescente:
la somma degli elementi di una riga i è minore o uguale della
somma degli elementi della riga i+1, per ogni i
int SUM(int* M, int m){
int j,somma=0;
for (j=0; j<m; j++) somma += M[j];
return somma;
}
int rigata(int** M, int n, int m){
return crescente(M,1,SUM(M[0],m),n,m);
}
Corso di Calcolatori Elettronici
APPUNTI SUL LINGUAGGIO C
Array e puntatori
FINE