Esercitazione 6

Array

Arrays

Array (o tabella o vettore):

è una variabile strutturata in cui è possibile memorizzare un numerofissato di valori tutti dello stesso tipo.

Esempio

int a[6]; /* dichiarazione di un array di nome a atto a memorizzare6 elementi di tipo int */

0 21 43 5

Arrays Ogni elemento di un array è individuato da un indice (da 0 a lunghezza dell’array meno 1).

Esempio

int a[6];a[0] = 4;a[1] = 42;a[2] = 34;a[3] = -23;a[4] = 87;a[5] = a[2]; 4 42 34 -23 87 34

0 21 43 5

Esercizio Descrivere l’output generato dal seguente programma.

#include <stdio.h>

main ( ) {

int a, b = 0;int c [10] ;

for (a = 0; a< 10; a++)c [a] = a;

for (a = 0; a < 10; ++a)if ((c [a] % 2) == 0)

b += c[a];printf (“%d”, b);

}

Soluzione

Il programma definisce un array c di 10 interi che contiene i valori 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;

calcola la somma degli elementi dell’array i cui valori sono pari;

quindi stampa il valore di tale somma che vale 20.

Esercizio: Crivello di Eratostene

Costruire una tabella di numeri interi

int tabella [DIM]tale che:

in corrispondenza di ogni indice da 0 a 100 c’è un numero 0 o 1 tale chese i è 0 o 1 allora tabella[i]==1;per ogni i compreso tra 2 e 100,

se i è primo allora tabella[i]=1;se i non è primo allora tabella[i]=0;

Infine si stampino i numeri primi trovati.

Soluzione

0 1 2 3 4 5 6 7 8 9 10 11 12 13 …

1 1 1 1 1 1 1 1 1 1 1 1 1 1 …

0 1 2 3 4 5 6 7 8 9 10 11 12 13 …

1 1 1 1 0 1 0 1 0 1 0 1 0 1 …

0 1 2 3 4 5 6 7 8 9 10 11 12 13 …

1 1 1 1 0 1 0 1 0 0 0 1 0 1 …

cancello i multipli di 2

cancello i multipli di 3

inizializzazione

....

#include <stdio.h>#define DIM 101 /* deve contenere i numeri da 0 a 100 */

main ( ) {int i, j;int tabella [DIM] ;

for (i = 0; i< DIM; i++) /* inizializzo la tabella */tabella [i] = 1;

printf (“%d “, 1);

for (i = 2; i < DIM; i++)if (tabella [i] == 1) {

printf (“%d “, i);for (j = 2; j * i < DIM; j++) /* elimino i multipli di i */

tabella [i * j] =0; }

printf (“\n”);}

scanf

La funzione scanf

legge caratteri dallo standard input (tastiera),

li interpreta,

memorizza il risultato negli argomenti successivi (che sono indirizzi di memoria).

La funzione scanf restituisce un intero che

rappresenta il numero di valori che sono stati letti con successo

scanf di caratteri

La funzione scanf

legge i caratteri dallo standard input (tastiera) esattamente nell’ordine in cui vengono inseriti

i caratteri di “fine linea”, “tab” ecc. non vengono ignorati(è dunque necessario tenere conto di tali caratteri)

è possibile ignorare i carattere di “fine linea”, “tab” e “spazi” mettendo uno spazio prima di %c

Esercizio

Scrivere una funzione che inizializza un array di caratteri.

void inizializza_array (char tabella [ ], int dim) {

int i;for (i=0; i<dim; i++){

printf (“inserisci elemento %d e digita invio: ”, i+1);scanf(“ %c”, &tabella[i]);

} } spazio (ignora tutti gli spazi e i tab che

precedono l’immissione del carattere)

EsercizioScrivere un programma che utilizza la funzione inizializza_array.#include <stdio.h>#define N 5

void inizializza_array (char tabella [ ], int dim){ ...}

main ( ) {char array[N];

inizializza_array (array,N);/* stampa la tabella */printf(“\n la tabella inizializzata è: \n\n\t”);for (i=0; i<N; i++)

printf (“%c “, array[i]);printf(“\n\n”);

}

Output

Esempio di esecuzione del programma precedente.

inserisci elemento 1 e digita invio: linserisci elemento 2 e digita invio: iinserisci elemento 3 e digita invio: binserisci elemento 4 e digita invio: r inserisci elemento 5 e digita invio: o

la tabella inizializzata è:

l i b r o

prompt$

Esercizio: istogrammiScrivere un programma che legge un vettore di interi di dimensione fissata, e stampa il corrispondente istogramma.

Esempio:

Dato il vettore 1 3 2 4 7 9

stampa

1| *3| ***2| **4| ****7| *******9| *********

#include <stdio.h>#define DIM 10

int main(void) {int vett [DIM];int i, j;

/* leggi vettore */printf("Inserire un vettore di interi di dimensione %d\n", DIM);for (i = 0; i < DIM; i++)scanf("%d", &vett[i]);

/* stampa dell'istogramma */for (i = 0; i < DIM; i++) {printf("%d |", vett[i]);for (j = 0; j < vett[i]; j++)printf("*");

printf("\n");}

}

Le funzioni getchar e putchar

Le funzioni

int getchar (void): legge il prossimo carattere dallo standard input e lo restituisce come valore intero.

int putchar(int c): visualizza il carattere memorizzato in c.

si trovano nella libreria stdio.h per l’input/output standard.

Esercizio: MCD

Scrivere un programma che calcola il massimo comune divisore tradue numeri interi positivi, n e m.

Esempi:

MCD (5, 15) = 5

MCD (12, 16) = 4

MCD (100, 75) = 25

Esercizio (continua)

Una soluzione elegante è fornita dal ben noto algoritmo di Euclide.

L’idea si basa sulla seguente osservazione:

Per qualunque coppia di valori interi positivi x e y tali che x > y, l’insieme dei divisori di x e y coincide con l’insieme dei divisori di x - y e y

Esercizio (continua)

Possiamo quindi risolvere il problema del MCD utilizzando ilseguente algoritmo.

ALGORITMO DI EUCLIDE

se m=n allora il MCD(m,n) è m (o n)se m≠n allora

se m>n allora MCD(m,n)=MCD(m-n,n)se m<n allora MCD(m,n)=MCD(m,n-m)

Ripetendo questo procedimento, prima o poi si ottengono due numeri uguali che sono quindi il MCD(m,n) cercato.

Esercizio (continua)

Dimostriamo formalmente che l’algoritmo di Euclide è corretto.Siano x e y due numeri interi positivi tali che x > y.Denotiamo con Div(x,y) l’insieme dei divisori comuni di x e y.Vogliamo mostrare che k ∈ Div(x,y) se e solo se k ∈ Div(x-y,y) per qualunque scelta di k. Proviamo le due implicazioni separatamente.(⇒) Per definizione di divisore, k ∈ Div(x,y) implica che esistono due

interi s e t tali che x = s * k e y = t * k. Ma allorax - y = (s * k) – (t * k) = (s – t) * k e quindi k ∈ Div(x-y,y).

⇐ k ∈ Div(x-y,y) implica che esistono s e t tali che x - y = s * k e y = t * k. Ma allora x = x – y + y = s * k + t * k = (s + t) * k e quindi k ∈ Div(x,y).

Soluzione #include <stdio.h>

int MCD(int x, int y) {while (x!=y)

if (x>y) x = x - y;else y = y - x;

return x; }

Invariante del ciclo:Siano m e n i parametri attuali, quindi l’invariante è:{ x > 0, y > 0, Div(x,y) = Div(m,n) }

Terminazione: la funzione d(x,y)=x+y per valori x > 0 e y > 0decresce ad ogni iterazione del ciclo

Soluzione (continua)

int main ( ) {int m, n, mcd;printf(“Inserisci il numero intero positivo m: \n”);scanf (“%d”, &m);printf(“Inserisci il numero intero positivo n: \n”);scanf (“%d”, &n);mcd = MCD(m,n);printf(“Il MCD di %d e %d è: %d\n”, m, n, mcd);

}