PolitecnicoPolitecnicodi Milanodi Milano

Esercizi C su array e matriciEsercizi C su array e matrici

Massimo, media e varianza, ordinamento, ricerca e Massimo, media e varianza, ordinamento, ricerca e merge, matrice simmetrica, puntatorimerge, matrice simmetrica, puntatori

- - 22 - -

ArrayArray

Array o vettoreComposto da una serie di celleint vett[4] = {3, 5, -6, 10};

vett

0 1 2 3

Stesso tipo per tutte le celleAlloca tutte le celle“lunghezza” dell’array

Tipicamente serve un contatore.

3 5 -6 10

- - 33 - -

Media e varianzaMedia e varianza

Leggere un insieme di numeri, inserirlo in un array e calcolare la media e la varianza. L’utente dovrà esplicitamente indicare quanti numeri vuole inserire nell’array.Ricordiamo che la media e la varianza di n dati ai si ottengono:

n

ax

n

ii

1

1

)()( 1

2

n

xaxVar

n

ii

Utilizziamo la funzione predefinita pow(base,esp) che calcola baseesp.

- - 44 - -

#include <stdio.h>#include <math.h>void main(){

const unsigned int MAX = 1000;float arrayNumeri[MAX];unsigned int i, num;float totale = 0, media, varianza;printf ("quanti numeri (max %u): ", MAX);scanf ("%u", &num); /* assumo num < MAX */for (i = 0; i < num; i++){

printf ("Dato (%u): ", i);scanf ("%f", &arrayNumeri[i]);totale = totale + arrayNumeri[i];

} .

Media e varianzaMedia e varianza

- - 55 - -

media = totale / num;totale = 0;for (i = 0; i < num; i++){

totale = totale + pow(arrayNumeri[i]-media, 2);}varianza = totale / (num – 1);printf ("Media:%f, varianza:%f", media, varianza);

}

Media e varianzaMedia e varianza

Se l’utente inserisce un solo numero?Verificare l’input dell’utente…

- - 66 - -

Trova il massimoTrova il massimo

Leggere un insieme di numeri interi e inserirlo in un array. L’insieme sarà terminato dal numero zeroTrovare quindi:

Il numero massimoLa posizione della cella nella quale il numero massimo è stato inserito.

- - 77 - -

Trova il massimoTrova il massimo#include <stdio.h>void main(){

const unsigned int MAX = 1000;int arrayNumeri[MAX], dato, max;unsigned int i, num = 0, posizMax;arrayNumeri[0] = 0; /* se non immetto niente… */scanf ("%d", &dato);while (dato != 0 && num < MAX){

arrayNumeri[num] = dato;num = num + 1;if (num < MAX) /* Non leggo il dato seguente */{ /* se l’array è finito */

scanf ("%d", &dato);}

} .

- - 88 - -

Trova il massimoTrova il massimo

max = arrayNumeri[0];posizMax = 0;for (i = 1; i < num; i++){

if (arrayNumeri[i] > max){

max = arrayNumeri[i];posizMax = i;

}}printf ("Max:%d, posizione:%u", max, posizMax);

}

- - 99 - -

Ricerca lineareRicerca lineare

L’utente inserisce in un array un certo numero di interiL’utente inserisce un numero e l’elaboratore controlla se è presente nell’arraySe il numero è presente, si visualizza la posizione in cui è stato trovato

- - 1010 - -

Ricerca lineareRicerca lineare

#include <stdio.h>void main(){ unsigned int i, n, trovato = 0; int numeri [100], num;

printf ("Quanti numeri: "); scanf ("%u", &n); for (i = 0; i < n; i++) { printf ("Numero %u: ", i); scanf ("%d", &numeri[i]); }

printf ("Numero da cercare: "); scanf ("%d", &num); .

- - 1111 - -

Ricerca lineareRicerca lineare i = 0;

do { if (numeri[i] == num) { trovato = 1; } else { i++; } } while (trovato == 0 && i < n); if (trovato) { printf ("Numero: %d ", numeri[i]); printf ("Posizione: %u\n", i); }} .

- - 1212 - -

Merge di due array ordinatiMerge di due array ordinati

L’utente inserisce due array composti da numeri interi ed ordinati in senso crescente. Le lunghezze dei due array possono essere differentiL’elaboratore crea un terzo array ordinato, utilizzando i due array inseriti dall’utenteInfine, quest’ultimo array viene visualizzato

10

20

30

40

50

10

30

20

40

50

i1 i2im

- - 1313 - -

Merge di due array ordinatiMerge di due array ordinati

#include <stdio.h>void main(){

const int MAX = 100;int array1[MAX], array2[MAX], merge[2 * MAX];unsigned int n1, n2, i1, i2, im;printf ("Lungh array 1: ");scanf ("%u", &n1);printf ("Lungh array 2: ");scanf ("%u", &n2);for (i1 = 0; i1 < n1; i1++){

printf ("Array1, numero: ");scanf ("%d", &array1[i1]);

} .

- - 1414 - -

Merge di due array ordinatiMerge di due array ordinati

for (i2 = 0; i2 < n2; i2++){

printf ("Array2, numero: ");scanf ("%d", &array2[i2]);

}i1 = 0;i2 = 0; .

- - 1515 - -

Merge di due array ordinatiMerge di due array ordinati

for (im = 0; im < n1 + n2; im++){

if (i1 < n1 && array1[i1] < array2[i2] || i2 >= n2){

merge[im] = array1[i1];i1++;

}else{

merge[im] = array2[i2];i2++;

}} .

- - 1616 - -

Merge di due array ordinatiMerge di due array ordinati

for (im = 0; im < n1 + n2; im++){

printf ("%d\n", merge[im]);}

} .

- - 1717 - -

L’utente inserisce in un array un certo numero di interiL’elaboratore ordina l’array in senso crescente e lo visualizza

Ordinamento per inserzioneOrdinamento per inserzione

0

1

2

3

4

0

1

2

3

4

20

30

0

1

2

3

4

20

20

30

0

1

2

3

4

10

20

25

30

0

1

2

3

4

10

20

25

30

40

0

1

2

3

4

10

L’algoritmo viene applicato mentre l’utente inserisce i dati

- - 1818 - -

#include <stdio.h>void main(){

unsigned int tot;int ultima, i, candidata, sposta;int n, numeri[100];printf ("Quanti numeri: ");scanf ("%u", &tot);for (ultima = 0; ultima < tot; ultima++){

printf ("Numero: ");scanf ("%d", &n);candidata = 0; .

Ordinamento per inserzioneOrdinamento per inserzione

- - 1919 - -

while (n >= numeri[candidata] && candidata <= ultima){

candidata++;}/* Sposto a partire dal fondo, altrimenti sovrascrivo. La variabile ultima indica l'ultima casella occupata */for (sposta=ultima; sposta>=candidata; sposta--){

numeri[sposta + 1] = numeri[sposta];}numeri[candidata] = n;

} .

Ordinamento per inserzioneOrdinamento per inserzione

- - 2020 - -

for (i = 0; i < tot; i++){

printf ("%d\n", numeri[i]);}

} .

Ordinamento per inserzioneOrdinamento per inserzione

- - 2121 - -

Ordinamento con Bubble SortOrdinamento con Bubble Sort

Lo stesso testo dell’esercizio precedenteUsiamo l’algoritmo di ordinamento noto con il nome di “bubble sort” (ordinamento a bolle)

20

10

30

40

0

1

2

3

4

25

25

10

30

40

0

1

2

3

4

20

10

25

30

40

0

1

2

3

4

20

20

25

30

40

0

1

2

3

4

10

L’utente inserisce i dati in modo disordinatoL’algoritmo viene applicato alla fine della fase di inserimento

- - 2222 - -

Ordinamento con Bubble SortOrdinamento con Bubble Sort

Come si effettua lo scambio del contenuto di due variabili?Serve una variabile temporanea:

10 20a tempb

10 20a 10tempb

20 20a 10tempb

20 10a 10tempb

- - 2323 - -

#include <stdio.h>void main(){

unsigned int tot, i, scambio;int numeri [100], temporanea;printf ("Quanti numeri: ");scanf ("%u", &tot);for (i = 0; i < tot; i++){

printf ("Numero: ");scanf ("%d", &numeri[i]);

} .

Ordinamento con Bubble SortOrdinamento con Bubble Sort

- - 2424 - -

do{

scambio = 0;for (i = 0; i < tot - 1; i++){

if (numeri[i] > numeri[i + 1]){

/* inizio scambio di due variabili */temporanea = numeri[i];numeri[i] = numeri[i + 1];numeri[i + 1] = temporanea;/* fine scambio di due variabili */scambio = 1;

}}

} while (scambio == 1); .

Ordinamento con Bubble SortOrdinamento con Bubble Sort

- - 2525 - -

for (i = 0; i < tot; i++){

printf ("%d\n", numeri[i]);}

} .

Ordinamento con Bubble SortOrdinamento con Bubble Sort

- - 2626 - -

MatriceMatrice

Composta da una matrice di celleint mat[2][4] = {{3,5,7,2},{-4,6,1,1}};

Stesso tipo per tutte le celleAlloca tutte le celle“lunghezze” della matrice

Tipicamente servono due contatori.

mat

0 1 2 3

0

1

3 5 7 2

-4 6 1 1

- - 2727 - -

Matrice simmetricaMatrice simmetrica

L’utente inserisce una matrice quadrata, composta di numeri reali, ed il programma verifica (e visualizza) se è simmetricaLa dimensione della matrice inserita dall’utente è fissata all’interno del programmaRicordiamo che una matrice quadrata è simmetrica sse per ogni i,j vale ai,j = aj,i

1 7 3 8

7 5 4 11

3 4 0 13

8 11 13 6

0

1

2

3

0 1 2 3

- - 2828 - -

#include <stdio.h>void main(){

const unsigned int DIM = 3;unsigned int riga, colonna;unsigned int simmetrica;float matrice [DIM][DIM];for (riga = 0; riga < DIM; riga++){

for (colonna = 0; colonna < DIM; colonna++){

printf ("numero (%u,%u): ", riga, colonna);scanf ("%f", &matrice[riga][colonna]);

}} .

Matrice simmetricaMatrice simmetrica

- - 2929 - -

simmetrica = 1;riga = 0;do /* righe */{

colonna = riga + 1;do /* colonne */{

if (matrice[riga][colonna]!= matrice[colonna][riga]){

simmetrica = 0;}colonna++; .

Matrice simmetricaMatrice simmetrica

- - 3030 - -

Matrice simmetricaMatrice simmetrica

} while (colonna < DIM && simmetrica == 1);riga++;

} while (riga < DIM - 1 && simmetrica == 1);if (simmetrica == 1){

printf ("Matrice simmetrica\n");}else{

printf ("Matrice non simmetrica\n");}

} .

- - 3131 - -

PuntatoriPuntatori

Un puntatore contiene un riferimento ad un’altra variabile

125a

(1000)

…

int a = 125, *p;p = &a;*p = 128;printf (“%d”, *p);

…

1000 p

(2000)

- - 3232 - -

Array e puntatoriArray e puntatori

Il nome dell’array, usato senza le parentesi, rappresenta l’indirizzo in memoria della prima cella(ovvero, un puntatore ad essa)L’indirizzo non può essere modificato (ovvero, il nome rappresenta un puntatore costante)

int vettA[4], vettB[4];int *pIntero;…pIntero = vettA; /* Corretto: pIntero punta a vettA */vettB = vettA; /* Errore di compilazione! */vettA = pIntero; /* Errore di compilazione! */

- - 3333 - -

Array e puntatoriArray e puntatori

#include <stdio.h>

void main(){ int numeri[5] = {6, 8, -3, 4, 10}; int *pInt; unsigned int i;

pInt = numeri; /* pInt diventa un alias */ for (i = 0; i < 5; i++) {

printf ("%d\n", numeri[i]); printf ("%d\n", *(pInt + i));

printf ("%d\n", pInt[i]); }}.