algoritmi su array

Nel seguito vengono implementate alcune funzioni che risolvono alcuni algoritmi su un array di interi (alcune le abbiamo già utilizzate), da usare nei vari programmi a seconda delle esigenze.

//carica l'array v (di n elementi) con valori inseriti dall'utentevoid carica (int n, int *v) { int i; for (i=0; i<n; i++) { printf ("elemento %d: ",i); scanf("%d",&v[i]); } } //stampa il valore degli n elementi dell'array vvoid visualizza(int n, int *v) { int i; for (i=0; i<n; i++) printf ("elemento %d: %d\n", i, v[i]); } //restituisce la somma degli n elementi dell'array vint somma(int n, int *v) { int i, acc=0; for (i=0; i<n; i++) acc+=v[i]; return acc; } //restituisce il prodotto degli n elementi dell'array vlong int prodotto(int n, int *v) { int i, acc=1; for (i=0; i<n; i++) acc*=v[i]; return acc; }

PROBLEMA DEL MASSIMO/MINIMO

// restituisce la posizione dell'elemento massimo, nell'ipotesi che tutti gli elementi siano diversiint massimo(int n, int *v) { int mass,pos,i; // Prima di cominciare la ricerca, il primo elemento è considerato il massimo mass=v[0]; pos=0; for (i=1; i<n; i++) { if (v[i]>mass) { mass=v[i]; pos=i; } } return pos; } // restituisce la posizione dell'elemento minimo, nell'ipotesi che tutti gli elementi siano diversiint minimo(int n, int *v) { int min,pos,i; // Prima di cominciare la ricerca, il primo elemento è considerato il minimo min=v[0]; pos=0; for (i=1; i<n; i++) { if (v[i]<min) { min=v[i]; pos=i; } } return pos; } main() { ... posmax = massimo(dim,vettore); printf("il massimo e' %f in posizione %d \n", vettore[posmax], posmax); /* oppure, con una sola istruzione e senza variabile di appoggio, posso usare come indice il valore restituito dalla funzione massimo */ printf("il massimo e' %f in posizione %d \n", vettore[massimo(dim,vettore)], posmax); ... }

NOTA: se gli elementi dell’array si ripetono, gli algoritmi precedenti restituirebbero la posizione del 1° elemento (massimo/minimo); in questo caso, per poter individuare tutti i valori massimi/minimi, è necessario effettuare una scansione dell’array confrontando il valore massimo/minimo con gli altri valori e comunicandoli quando sono uguali al massimo/minimo.

La funzione visualizzaMassimi può essere utilizzata sia per visualizzare la posizione di uno o più massimi:

// stampa la posizione degli elementi uguali al massimo in un vettore v di n elementivoid visualizzaMassimi(int n,int *v) { int i, posizioneMax; // cerco la posizione del massimo con la funzione definita nell'esempio precedente posizioneMax=massimo(n,v);

for(i=0; i<n; i++) //v[posizioneMax] è il valore dell'elemento massimo if (v[i]==v[posizioneMax]) printf("Trovato il massimo in posizione %d\n",i); }

La funzione visualizzaUguali può essere utilizzata sia per visualizzare la posizione di uno o più massimi, ma anche i minimi o, in generale, la posizione di elementi uguali ad un parametro:

// stampa la posizione degli elementi uguali a val in un vettore v di n elementivoid visualizzaUguali(int n,int *v,int val) { int i; for(i=0; i<n; i++)

if (v[i]==val) printf("valore trovato in posizione %d\n",i); }

PRECISAZIONE: le funzioni che "stampano" non sono funzioni pure e sono poco riusabili; in generale è bene non farle, a meno che non siano dedicate in modo specifico a fare output a video e non svolgano altri compiti (come in questo caso).

Un'altra soluzione potrebbe prevedere di cercare le posizioni dei valori massimi (o minimi) caricandole in altro altro array; questa alternativa consente di avere a disposizione i dati per eventuali ulteriori elaborazioni (che invece la soluzione precedente, limitandosi alla stampa dei dati, non consente).

Con riferimento alla ricerca dei massimi (o dei minimi) potremmo voler conoscere quante volte il massimo (o il minimo) si presenta nell'array:

// restituisce il numero di elementi uguali al valore val in un vettore v di n elementiint contaUguali(int n,int *v,int val) { int i, c=0; for(i=0; i<n; i++)

if (v[i]==val) c++;

return c; }

PROBLEMA DELLA RICERCA

Esistono diversi tipi di ricerche, in base ciò che si vuole ottenere.

Se non ci sono elementi ripetuti, questo algoritmo cerca la posizione di un elemento noto il suo valore; se lo trova, la scansione viene bloccata e viene ritornata la posizione; se non viene trovato, esce –1, da controllare nel main.

/* Restituisce la posizione di un valore ricevuto come parametro nell'array v di n elementi oppure -1 se il valore non è presente nell'array. Ipotesi: l'array contiene elementi tutti diversi */int cerca (int n, int *v, int valore) { int i; for (i=0; i<n; i++) if (v[i]==valore) // se lo trova, blocca la ricerca return i; return -1; }

Dato che nell'array un valore può ripetersi, possiamo utilizzare una funzione analoga a visualizzaMassimi, passandole il valore dell'elemento da cercare (o della sua posizione).

NOTA: anche gli algoritmi di MASSIMO/MINIMO non sono altro che particolari ricerche; la ricerca dei valori superiori/inferiori al valore medio è un altro esempio di ricerca.

Nell’ipotesi di elementi non ripetuti e di array ordinato, l’algoritmo di ricerca più efficiente è quello DICOTOMICO (v. RICERCADICO).

PROBLEMI DI ORDINAMENTO (SORT)

Dopo un ordinamento l’ordine originario del vettore è perso, quindi conviene, a volte, generare una copia su cui lavorare; esistono diversi tipi di ordinamento.

ORDINAMENTO PER SELEZIONE (O SOSTITUZIONE O SELECTION SORT)

Nell’ordinamento crescente (analoghe considerazione valgono per quello decrescente) si confronta ogni elemento con tutti i suoi successivi e, se l’elemento non è ordinato, lo si scambia con il successivo utilizzando una variabile di appoggio; se ho N elementi, l’elemento in posizione N-1 è l’ultimo e non ha successivo (quindi il ciclo esterno si ferma prima di N-1):

Questo algoritmo è poco efficiente perché esegue comunque tutti i controlli anche se, ad un certo punto, il vettore è già ordinato; inoltre, nell’ipotesi che il vettore sia già in partenza ordinato, vengono eseguiti comunque tutti i cicli; però è un algoritmo semplice da ricordare (è detto anche ORDINAMENTO INGENUO):

void ordinaCrescente (int n, int *v) { int i, j, aux; for (i=0; i<n-1; i++){ for(j=i+1; j<n; j++){ if (v[i]>v[j]){ aux=v[i]; v[i]=v[j]; v[j]=aux; } } } } void ordinaDecrescente (int n, int *v){ int i, j, aux; for (i=0; i<n-1; i++){ for(j=i+1; j<n; j++){ if (v[i]<v[j]) { aux=v[i]; v[i]=v[j]; v[j]=aux; } } } }

Come si può notare le istruzioni per scambiare gli elementi sono sempre uguali; si può costruire una funzione che scambia gli elementi, rendendoli visibili al chiamante; quindi nella chiamata è necessario passare gli indirizzi di memoria e nella funzione si usano i puntatori:

void scambia(int *x,int *y){ int aux ; aux=*x ; *x=*y ; *y=aux ; }

All'interno dell'if chiamerei la funzione scambia passandole l'indirizzo dei due elementi da scambiare:

scambia(&v[i],&v[j]);

ORDINAMENTO A BOLLE (BUBBLESORT)

Per evitare l’inconveniente visto prima (array già ordinato), si può introdurre una variabile che segnala quando l’array è ordinato, per fermare il ciclo di scansione; si fa l’ORDINAMENTO A BOLLE (BUBBLESORT)

Ad ogni scansione (bolla) viene controllato un elemento con il suo successivo e, se non sono in ordine, vengono scambiati (stesso modo di prima); al termine di una scansione, in caso di ordinamento crescente, l’elemento più grande è in ultima posizione (N-1) (al contrario di prima):

(la parte in grigio non viene più considerata nella scansione successiva)

Nell’ipotesi che il vettore sia ordinato sin dall’inizio, viene eseguita una scansione e, poiché non avvengono scambi, si esce dal ciclo e viene interrotta l’esecuzione; quindi risulta più efficiente rispetto all’ordinamento ingenuo.

// Ordina l'array v (di n elementi) in ordine crescente usando l'algoritmo Bubble Sortvoid ordinaBubble(int n, int *v) { int i, scans=n, aux, sw; //sw è un deviatore (o flag) che segnala se avviene uno scambio (1) o no (0) do { scans--; sw=0; for(i=0; i<scans; i++){ if (v[i]>v[i+1]) { sw=1; aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } } }while((scans!=1)&&(sw)); // sw!=0; sw==1 }

Oppure, usando due cicli for:

void ordinaBubble(int n, int *v){ int i, scans, sw=1,aux; for(scans=n-1; scans>1 && sw; scans--){ sw=0; for(i=0; i<scans; i++){ if (v[i]>v[i+1]) { sw=1; aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } } } }

Per approfondimenti sull'ordinamento: http://www.sorting-algorithms.com/

Un altro algoritmo di ricerca: RICERCA DICOTOMICA

Su un array ordinato in senso CRESCENTE (e posto che non vi siano elementi ripetuti) la RICERCA DICOTOMICA è un algoritmo molto potente perché non scandisce l’intero array ma lo divide progressivamente a metà scartando la parte che sicuramente non contiene l’elemento (essendo l’array ordinato); si basa sullo stesso metodo con cui si cerca una parola in un vocabolario…

Quando l’elenco viene diviso a metà, si controlla se l’elemento da cercare corrisponde a quello di metà elenco: se l’elemento si trova lì, viene restituita la posizione e la ricerca viene interrotta; in caso contrario se controlla se l’elemento da cercare è più piccolo di quello che si trova a metà elenco (cioè se si trova nella prima metà) e si scarta la seconda metà (quindi si fa terminare l’elenco a metà). Si controlla di nuovo la metà rimasta con lo stesso procedimento.

NOTA: se l’array è ordinato in ordine crescente (decrescente) in posizione 0 c’è il MINIMO (massimo) e in posizione N-1 c’è il MASSIMO (minimo); è un altro metodo per individuare il massimo in minimo (attenzione: l’ordine originario è perso, a meno che non sia lavorato sulla copia dell’array)

/* Restituisce la posizione di un valore nell'array v di n elementi,

oppure -1 se il valore non presente. Ipotesi: 1) gli elementi sono tutti diversi; 2) il vettore deve essere ordinato */int ricercaDicotomica(int n, int *v, int valore) { int i, inizio=0, fine=n-1;

do { i=(inizio+fine)/2; //divisione intera if (v[i]==valore) return i; // trovato! else if (v[i]>valore) fine=i-1; else inizio=i+1; } while(inizio<=fine);

return -1; //se non trovato }

ALTRI ALGORITMI INTERESSANTI

Raggruppamento (avvicinamento) di elementi uguali

Esempio: dato l’array int v[10]={2,1,5,1,3,4,5,3,8,1}

void raggruppa(int n, int*v) { int i, j, aux; for(i=0; i<n-1; i++){ for(j=i+1; j<n; j++){ if(v[i]==v[j]){ aux=v[j]; v[j]=v[i+1]; v[i+1]=aux; i++; } } } }

Si ottiene: 2,1,1,1,3,3,5,5,8,4.

Quindi non è un ordinamento, ma gli elementi vengono spostati mettendoli vicini, nell’ordine in cui si trovano.