algoritmiVettori

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[indice]
   }

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:

• indice è ancora all'interno del vettore
• non ha trovato l'elemento

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);
}

   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");
   }

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:

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.