Politecnico di Milano Esercizi C su array e matrici Massimo, media e varianza, ordinamento, ricerca...
33
Politecnico Politecnico di Milano di Milano Esercizi C su array e matrici Esercizi C su array e matrici Massimo, media e varianza, ordinamento, Massimo, media e varianza, ordinamento, ricerca e merge, matrice simmetrica, ricerca e merge, matrice simmetrica, puntatori puntatori
-
Upload
giorgino-nanni -
Category
Documents
-
view
220 -
download
2
Transcript of Politecnico di Milano Esercizi C su array e matrici Massimo, media e varianza, ordinamento, ricerca...
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]); }}.
