Esempio: una classe di 32 studenti ha sostenuto durante l’anno 5 compiti in classe. Supponiamo di voler scrivere un programma che stampi per ogni studente la somma e la media dei voti
ottenuti
int const R=40;
int const C=8;
int A[R][C];
int n=32;
int m=5;
Compito Studente
0 1 2 3 4 5 6 7
0 9 6 0 7 7 N
O N
U S A T A
1 5 6 6 0 6
2 8 6 7 0 0
3 4 6 5 4 4
... … … … … …
... … … … … …
32 2 4 4 5 4
... NON USATA
39
R
C
Algoritmi su Matrici
Allorché occorre ricavare dell’informazione da una matrice A occorre sempre ricordare cosa rappresenta una riga, cosa rappresenta un array e che cosa rappresenta un generico elemento a[i][j].
In genere il problema da risolvere cade in uno dei quattro schemi seguenti:
Elaborazione riga per colonna.
Il loop più esterno agisce sulle righe quello più interno sulle colonne.
Supponendo che A sia una matrice avente m righe ed n colonne:
Algoritmo riga per colonna:
for(i=0,i<m,i++) {
for(j=0,j<m,j++) elabora A[i,j]
}
Algoritmi su Matrici
j
i
A[i][j]
Elaborazione colonna per riga.
Qui il loop più esterno agisce sulle colonne quello più interno sulle righe.
Algoritmo colonna per riga:
for(j=0,j<n,j++) {
for(i=0,i<m,i++)
elabora A[i,j]
}
In alcuni casi i due algoritmi sono equivalenti .
Ritornando alla matrice contenente i voti riportati ai compiti dai singoli studenti, se si volesse calcolare la media dei voti su tutti i compiti svolti dagli studenti si potrebbe adoperare uno qualsiasi dei due.
Se invece, come nel nostro esempio, si vuole conoscere il voto medio riportato da ogni singolo studente è indispensabile adoperare il primo.
Una elaborazione colonna per riga ci fornirebbe il voto medio riportato dalla classe per ogni compito.
j i
A[i][j]
Algoritmi su Matrici
Esempio: riprendiamo l’esercizio del voti dei compiti di una classe di studenti
– Calcolare la media dei voti per ogni studente (elaboraz. riga per colonna) – Calcolare la il voto medio della classe
su ogni compito (elaboraz. colonna per riga)
Compito Studente
0 1 2 3 4
0 9 6 0 7 7
1 5 6 6 0 6
2 8 6 7 0 0
3 4 6 5 4 4
... … … … … …
... … … … … …
32 2 4 4 5 4
n
m
per i da 0 a n-1 passo 1:
somma ß 0
per j da 0 a m-1 passo 1:
somma ß somma + A[i][j]
stampa(somma/(m))
per j da 0 a m-1 passo 1:
somma ß 0
per i da 0 a n-1 passo 1:
somma ß somma + A[i][j]
stampa(somma/n)
Algoritmi su Matrici
Esempio: riprendiamo l’esercizio del voti dei compiti di una classe di studenti
– Calcolare la media dei voti di tutta la classe su tutti i compiti (elaboraz. riga per colonna oppure colonna per riga)
Compito Studente
0 1 2 3 4
0 9 6 0 7 7
1 5 6 6 0 6
2 8 6 7 0 0
3 4 6 5 4 4
... … … … … …
... … … … … …
32 2 4 4 5 4
n
m
somma ß 0
per i da 0 a n-1 passo 1:
per j da 0 a m-1 passo 1:
somma ß somma + A[i][j]
stampa(somma/(n ´ m))
somma ß 0
per j da 0 a m-1 passo 1:
per i da 0 a n-1 passo 1:
somma ß somma + A[i][j]
stampa(somma/(n ´ m))
oppur e
Algoritmi su Matrici
Elaborazione di una riga di una matrice Procurarsi l’indice i della riga
for(j=0,j<n,j++) elabora A[i,j]
Elaborazione di una colonna di una matrice Procurarsi l’indice j della colonna
for(i=0,i<m,i++) elabora A[i,j]
Ritornando al nostro esempio, trovare le insufficienze riportate dallo studente numero k comporta una elaborazione sulla riga k, mentre trovare lo studente col voto migliore nel compito r, comporta una elaborazione sulla colonna r.
j
i
A[i][j]
i j
A[i][j]
Algoritmi su Matrici
Esempio: riprendiamo l’esercizio del voti dei compiti di una classe di studenti
– Calcolare la media dei voti dello studente “k”
(elaborazione di una riga)
– Calcolare la media della classe sul compito “c”
(elaborazione di una colonna) Studente Compito 0 1 2 3 4
0 9 6 0 7 7
1 5 6 6 0 6
2 8 6 7 0 0
3 4 6 5 4 4
... … … … … …
... … … … … …
32 2 4 4 5 4
n
m
cß …ottieni indice colonna…
somma ß 0
per j da 0 a m-1 passo 1:
somma ß somma + A[i][c]
stampa(somma/n)
kß …ottieni indice riga … somma ß 0
per j da 0 a m-1 passo 1:
somma ß somma + A[k][j]
stampa(somma/m)
Algoritmi su Matrici
Sono dati i numeri di pezzi prodotti ogni giorno (dal lunedì al venerdì) da una ditta in n settimane lavorative. Scrivere una funzione per ottenere:
a) La somma settimana per settimana della produzione visualizzata in forma di diagramma di asterischi (un asterisco corrisponde a 10 pezzi prodotti);
b) il numero medio di pezzi prodotti giornalmente;
c) l’elenco dei giorni suddivisi nelle varie settimane, in cui la produzione è stata inferiore alla media con il relativo valore.
• Esempio: n=4, disponiamo i dati in modo che le righe siano le settimane e le colonne i giorni lavorativi della settimana.
Esercizi
Sia dato una matrice A di interi positivi di dimensione n ´ n.
Scrivere una funzione che restituisca true se e solo se nella matrice A:
• c’è almeno un numero pari in ogni riga
• c’è almeno un numero dispari in ogni riga
• ci sono almeno “i” numeri pari nella riga i-esima
• ci sono esattamente “i” numeri dispari nella riga i-esima
• ci sono almeno “i” numeri pari consecutivi nella riga i- esima
• ci sono esattamente “i” numeri dispari nella colonna i- esima
Esercizi
Scrivere un programma che, assegnata una matrice
quadrata di ordine n di reali, risolva i seguenti problemi con una funzione o procedura:
• restituisce la somma di tutti i suoi elementi;
• restituisce la somma di tutti gli elementi per cui è pari la somma degli indici;
• calcola la somma ed il prodotto degli elementi della diagonale principale e secondaria;
• restituisce true se la matrice è triangolare superiore od inferiore, false altrimenti;
• restituisce true se la matrice è unitaria, false altrimenti;
• restituisce true se la matrice è simmetrica, false altrimenti
Il programma deve essere strutturato con procedure e funzioni e con un menù che le richiami.
Esercizi
Scrivere un programma che, dopo aver letto tutti i dati del file studenti.txt (riportato nella pagina seguente) ed averli inseriti in una matrice, risolva i seguenti passi:
• stampi la media di ogni esame;
• stampi i numeri di matricola degli studenti che hanno ottenuto il voto più alto per ogni esame;
• stampi il numero di studenti che, per ogni esame, hanno superato la media già calcolata;
• conservi in un file, uno per riga, il numero di
matricola degli studenti che in almeno un esame, hanno ottenuto un voto maggiore di un valore prefissato
Esercizi
Supponiamo di avere sul un file di testo studenti.txt, i seguenti dati:
Numero
progressivo Numero
matricola Esame 1 Esame 2 Esame 3 Esame 4 Esame 5 Esame 6 Esame 7 Esame 8
1 1024 18 25 28 0 26 25 28 0
2 1038 0 30 28 26 24 28 27 25
3 1045 24 30 27 28 26 28 0 0
4 1087 23 25 24 20 24 23 0 0
5 1102 22 25 24 26 24 25 28 0
6 1120 23 28 27 26 30 25 28 0
7 1125 24 27 30 22 0 0 28 23
8 1142 22 25 26 23 24 25 0 24
9 1157 21 24 26 27 28 30 30 24
10 1164 22 25 0 0 25 0 0 24
11 1177 23 24 25 22 23 0 20 0
12 1185 19 22 20 21 22 20 0 0
Esercizio
Rappresentiamo una palude con un array bidimensionale di 0 e 1, in cui 1 rappresenta un punto attraversabile della
palude, mentre 0 rappresenta un punto inaccessibile.
Scriviamo una programma che, data la mappa di una palude, ne cerca un attraversamento e, se esiste, lo visualizza.
Matrici e while - Esercizio
1 0 0 1 0 0
1 0 0 0 0 0
0 1 0 0 0 1
0 0 1 1 1 0
0 1 0 0 0 0
INIZIO
FINE
Consideriamo una matrice int palude[R][C] riempita di 0 o 1
Cerchiamo un cammino ‘da sinistra a destra’ cioè dalla colonna 0 alla colonna C-1
Assumiamo che siano possibili solo movimenti in avanti, cioè partendo dalla posizione <riga, colonna> ci si può spostare in
– <riga-1, colonna+1> (solo se la riga non è la prima) – <riga, colonna+1>
– <riga+1, colonna+1> (solo se la riga non è l’ultima)
Memorizziamo il cammino costruito in un array int cammino[C] che contiene gli indici delle righe corrispondenti ad ogni pezzo del
percorso.
Es, nel caso in figura il cammino sarà 1 2 3 3 3 2
Matrici e while - Esercizio
const int righe =5; /* num righe, cioè larghezza della palude */
const int colonne=6;/* num colonne, cioè lunghezza della palude e (del cammino) */
/* Cerca un cammino a partire dalla posizione <i,j> della palude.
Ritorna 1 se l'attraversamento è stato trovato, 0 altrimenti. Il cammino trovato è memorizzato nell’array passato come parametro*/
bool cercaCammino (int palude[][colonne], int i, int j, int cammino[]);
/* Cerca un cammino che porti dalla prima all'ultima colonna della palude. Ritorna 1 se l'attraversamento è stato trovato, 0
altrimenti. */
bool esploraPalude (int palude [][colonne], int cammino[]);
/* Visualizza una palude evidenziando un cammino attraverso asterischi.*/
void stampaCammino (int palude [][colonne], int cammino[]);
Matrici e while - Esercizio
int main(){
int palude[righe][colonne] = {{1,0,0,1,0,0}, {1,0,0,0,0,0},
{0,1,0,0,0,1}, {0,0,1,1,1,0}, {0,1,0,0,0,0}};
int cammino[colonne]; /* vettore dove memorizzare il cammino trovato
*/
/* ricerca del cammino */
if (esploraPalude(palude, cammino)) stampaCammino(palude, cammino);
else
printf("Non ci sono cammini che attraversano la palude\n");
return 0;
}
Matrici e while - Esercizio
bool esploraPalude (int palude[][colonne], int cammino[]) { int i=0;
bool trovato = false; /* variabile booleana controlla se il cammino è stato trovato */
/* un cammino inizia con il primo elemento di una qualsiasi riga */
while(i < righe && !trovato){
trovato = cercaCammino(palude, i, 0, cammino);
i++;
}
return trovato;
}
void stampaCammino (int palude[][colonne], int cammino[]){
int i, j;
for (i=0; i < colonne; i++) printf(“%d”,cammino[i]);
printf(“\n”);
printf("Cammino che attraversa la palude:\n”);
for (i = 0; i < righe; i++) {
for (j = 0; j < colonne; j++) {
if (i == cammino[j]) /* se il punto fa parte del cammino */
printf("* ”); /* stampa '*' */
else /* altrimenti */
printf("- ”); /* stampa ‘-’ */
}
printf(“\n”);
} }
Matrici e while - Esercizio
bool cercaCammino (int palude[][colonne], int i, int j, int cammino[]) { bool trovato = true; /* controlla se il cammino è stato trovato */
if (palude[i][j] == 1) { /* sono sulla terraferma */
cammino[j] = i; /* aggiungo la pos. corrente nel cammino finale */
j++;
while(trovato && (j<colonne)){
/* cerco un passaggio nella colonna j */
if ((i > 0) && (palude[i-1][j]==1)){
i=i-1;
}
else if ((i<(righe-1)) && (palude[i+1][j]==1)){
i=i+1;
}
else if(palude[i][j]==1);
else trovato=false;
cammino[j]=i; /*aggiorno il vettore cammino*/
j++;
} }
return trovato;
}
