algoritmiVettori

algoritmi notevoli di ricerca in un vettore

Avendo un elenco di valori (numeri per semplicità nel nostro caso) usualmente serve di eseguire delle operazioni tipiche come la ricerca del massimo o del minimo valore o la verifica della presenza di un valore. Importante differenza per noi è l'organizzazione dei dati nel vettore: sono ordinati (ad esempio dal più piccolo al più grande) oppure no?

Vettore non ordinato

Questi algoritmi ragionano in un modo molto simile: scorro il vettore utilizzando un ciclo for e guardo un elemento alla volta. In pratica il codice assomiglierà molto a quello qui sotto:

   for(int indice = 0; indice < vettore.length; indice++) {
      // fai qualche operazione sull'elemento vettore[i]
   }

Individuazione del massimo

L'idea è questa: utilizzare la variabile massimo per tener conto del valore massimo trovato fino ad un determinato momento aggiornandola man mano che scorriamo il vettore.

Come valore iniziale diamo a massimo quello della cella di indice 0 del vettore (se io avessi un vettore lungo uno il massimo sarebbe il primo elemento... giusto no?) A partire dalla posizione 1 fino all'ultima si farà poi sempre questa operazione: se il valore trovato nella cella in esame è più grande di quello contenuto in massimo significa che questo è il nuovo massimo, allora copieremo in tale variabile quanto c'è nella cella del vettore alla posizione corrente. La variabile massimo conterrà così mano il massimo della porzione di vettore fino a quel punto analizzata: quando arriveremo all'ultima posizione tale variabile massimo conterrà il massimo di tutto il vettore. Non rimane che fornire l'algoritmo:

public void cercaMassimo() {
   int massimo, indice;
   // considero il primo elemento come il massimo
   massimo = vet[0];
   for(indice = 1; indice < vet.length; indice++) {
      if(massimo < vet[indice]) {
         // se l'emento al posto i è più grande del massimo
         // allora lo registro
         massimo = vet[indice];
      }
   }
   tRisultato.setText(massimo + "");
}

Per esercizio individua il minimo in un vettore disordinato.

Ricerca di un elemento (presente oppure no)

Dato un vettore (che contiene già dei valori) chiamato vet, dire se un certo numero è presente oppure no. Partendo dal presupposto che il vettore in questione non è ordinato l'unico modo per risolvere il problema è quello di analizzare ogni elemento e verificare se questo è uguale a quello cercato, in caso lo sia imposto a true una varibile chiamata trovato. Dopo aver finito la scansione visualizzo il risultato controllando il valore di tale variabile.

public void cercaInSerie() {
   int indice, numeroCercato;
   numeroCercato = Integer.parseInt(tNumeroCercato.getText());
   // visto che non l'ho ancora trovato imposto la varibile a false
   boolean trovato = false;
   for(indice = 0; indice < vet.length ; indice++) {
      if(vet[indice] == numeroCercato) {
         trovato = true;
      }
   }
   if(trovato==true) {
      tRisultato.setText("trovato");
   } else {          
      tRisultato.setText("NON trovato");
   }
}

Funziona... ma possiamo migliorarlo in un paio di modi:

  1. se l'elemento lo trovo smetto di cercare
  2. il confronto trovato==true è inutile, trovato è di per se una espressione booleana
public void cercaInSerie() {
   int indice, numeroCercato;
   numeroCercato = Integer.parseInt(tNumeroCercato.getText());
   boolean trovato = false;
   for(indice = 0; indice < vet.length && !trovato; indice++) {
      if(vet[indice] == numeroCercato) {
         trovato = true;
      }
   }
   if(trovato) {
      tRisultato.setText("trovato");
   } else {          
      tRisultato.setText("NON trovato");
   }
}

In questo modo il programma continua ad eseguire il ciclo se valgono entrambe le seguenti cose:

Ricerca di un elemento (dove si trova)

In questo caso non vogliamo soltanto sapere se un dato elemento è presente ma anche la sua prima posizione, se l'elemento non è presente indicheremo la sua posizione come -1 (in quanto questo valore non può essere l'indice di un vettore).

Questa funzione scrive dapprima -1 nella variabile posizioneElemento dopodiché, solo nel caso in cui si sia trovato il numero cercato, sovrascrive il contenuto di tale variabile col valore di indice che indica appunto la posizione dell'elemento.

public void cercaInSerie() {
   int indice;
   int numeroCercato = Integer.parseInt(tNumeroCercato.getText());
   // visto che non l'ho ancora trovato inizializzo la variabile a -1
   // per indicare che l'elemento non c'è
   int posizioneElemento = -1;
   
   for(indice = 0; indice < vet.length ; indice++) {
      if(vet[indice] == numeroCercato) {
      	 // ho trovato l'elemento, registro la sua posizione
         posizioneElemento = indice;
      }
   }
   tRisultato.setText("" + posizioneElemento);
}

Il programma sopra funziona... ma non trova il primo elemento ma l'ultimo perché una volta trovato continua la ricerca in effetti anche sprecando tempo, possiamo però modificare il ciclo for in modo che continui a cercare soltanto se non ha trovato niente (sarebbe a dire se posizioneElemento==-1):

public void cercaInSerie() {
   int indice;
   int numeroCercato = Integer.parseInt(tNumeroCercato.getText());
   int posizioneElemento = -1;
   
   for(indice = 0; indice < vet.length && posizioneElemento==-1 ; indice++) {
      if(vet[indice] == numeroCercato) {
         posizioneElemento = indice;
      }
   }
   tRisultato.setText("" + posizioneElemento);
}

Possiamo un po' migliorare il codice: mettiamo la condizione della if direttamente all'interno della condizione del for facendo sì che il ciclo vada avanti finche l'indice sta nel vettore e l'elemento attuale non sia quello cercato (detto in altre parole quando l'elemento attuale è quello cercato escxe dal ciclo).

   for(indice = 0; indice < vet.length && vet[indice] != numeroCercato; indice++) {
   	 // nel ciclo non rimane nulla da fare
   }
   if(indice < vet.length) {   //Il for si è fermato prima, quindi l'abbiamo trovato
      tRisultato.setText("" + indice);
   } else {           //Il for si è fermato perché indice == n, quindi l'elemento non c'è
      tRisultato.setText("-1");
   }

Avrai senz'altro osservato che il for ha corpo vuoto. In questo caso anziché mettere le graffe aperte e chiuse possiamo mettere il ;. Nel complesso la funzione nella sua ultima stesura sarà:

public void cercaInSerie() {
   for(indice = 0; indice < vet.length && vet[indice] != numeroCercato; indice++);
   if(indice < vet.length) {   //Il for si è fermato prima, quindi l'abbiamo trovato
      t_risultato.setText("" + indice);
   } else {           //Il for si è fermato perché indice == n, quindi l'elemento non c'è
      t_risultato.setText("-1");
   }
}

Vettore ordinato

Individuazione del massimo

Il problema è di facile soluzione: se il vettore è ordinato in modo crescente il massimo sarà l'ultimo valore del vettore, quello cioè di indice maggiore; se invece il vettore è ordinato in modo decrescente il massimo sarà nella prima posizione.

Per esercizio individua il minimo in un vettore ordinato.

Ricerca di un elemento in un vettore (ordinato)

Poniamo che il vettore sia ordinato in modo crescente. Facciamo un esempio di vettore crescente di 15 elementi:

-33 -28 -19 -2 1 13 14 15 18 21 42 45 50 61 67
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Supponiamo di voler cercare il numero 18. Dato che non ho ancora nessuna informazione sul vettore l'intervallo di ricerca va dalla posizione inferiore 0 alla posizione superiore 14. Questo perché in pratica la ricerca deve avvenire su tutto il vettore. Devo tener memoria di questo quindi utilizzerò 2 variabili e le inzializzo: rispettivamente inf = 0 e sup = 14. Vado a studiare l'elemento in posizione centrale. Come si calcola la posizione centrale: essendo la posizione centrale o posizione media, questa si ottiene con la formula della media fra le posizioni inferiore e superiore. Il risultato lo metto nella variabile metà = (inf + sup) / 2. Valuto se il numero contenuto in questa cella è quello cercato. Nell'esempio metà = (14 + 0) / 2 cioè 7. Il contenuto in 7 è 15. Rispetto al numero cercato (18) il 15 è più piccolo e di conseguenza sicuramente non potrà stare nelle posizioni del vettore da 0 a 7. L'intervallo di ricerca sarà allora da 8 a 14. L'8 si ottiene incrementando di 1 (perché si riferisce al successivo) il valore di metà. Chi è che dovrà valere 8: inf o sup? Dato che è cambiato l'estremo inferiore dell'intervallo di ricerca, sarà inf ad essere aggiornata: inf = metà + 1.
Si ricomincia pari pari tutto l'algoritmo (a meno ovviamente dell'inizializzazione di inf e sup): calcolo di metà = (8 + 14) / 2 che è 11. Anche qui studio cosa c'è in 11 e vedo che è 45. Non è il numero che cerco, è più grande del numero che sto cercando. Posso quindi affermare che se il numero ci fosse sarebbe in una posizione precedente a quella di metà ma superiore o uguale a quella di inf. Devo aggiornare quindi la mia variabile sup a metà - 1 cioè 10.
Si ricomincia ancora una volta come sopra. Calcolo ancora una volta metà = (8 + 10) / 2 e stavolta sarà 9. Qui c'è 21 che risulta più grande. L'intervallo di ricerca si restringe ancora perché sup si riduce a 8. Il valore medio sarà banalmente 8 e osservando il valore di questa posizione ci farà esultare: l'abbiamo trovato quindi l'algoritmo termina con successo.

Se avessimo cercato 19? Riguardando tutti i passaggi precedenti possiamo affermare che nulla cambia fino all'ultimo passaggio escluso. In questo si osserva invece che in posizione 8 il valore trovato risulta più piccolo (è 18) dato che cerchiamo 19. Ne consegue che la variabile inf diviene metà + 1quindi 9. Ci troviamo ad avere a questo punto inf > sup quindi terminiamo la ricerca perché l'elemento non è presente nel vettore.

Tale metodo di ricerca si chiama Ricerca binaria o Ricerca dicotomica. Non rimane che presentare la funzione:

public void ricercaBinaria() {
   int inf, sup, metà, ris = -1;
   numeroCercato = Integer.parseInt(tNumeroCercato.getText());
   for(inf = 0, sup = vet.length-1; inf <= sup; ) {
      metà = (inf + sup) / 2;
      if(numeroCercato == vet[metà]) {
         ris = metà;
         break; // termino la ricerca
      }
      if(numeroCercato < vet[metà]) {
         sup = metà - 1;
      }
      if(numeroCercato > vet[metà]) {
         inf = metà + 1;
      }
   }
   tRisultato.setText(ris + "");
}

Per esercizio prova ad eliminare il primo if contenuto nel for.

Dato un vettore di n elementi, caricarlo in modo disordinato quindi individuare il massimo elemento che non sia però superiore della media.
Dato un vettore di n elementi, caricarlo quindi in modo disordinato. Creare successivamente un altro vettore in cui in ogni elemento inserisci quanto dista il corrispettivo del vettore originario dalla media. Ad esempio, dato il vettore 4, 2, 5, 8, 6 si desume la media 5. Il nuovo vettore avrà componenti 5-4 = 1, 5-2 = 3, 0, -3, -1.
Dato un vettore di n voti, dire se sono più le sufficienze oppure no. Come variante indica anche a quanto ammonta la differenza.
Realizza un programma Java che permetta all'utente di caricare un vettore di n elememti non ordinati. Alla pressione di un pulsante mostrare all'utente (in due distinte caselle di testo) quanti sono i numeri pari superiori alla media dei valori del vettore e quanti sono i numeri inferiori alla media del vettore.
Realizza un programma Java che permetta all'utente di caricare un vettore di n elememti non ordinati. Alla pressione di un pulsante mostrare all'utente la media tra il minimo ed il massimo del vettore, quindi mostrare quanti elementi sono inferiori a tale media.