Page 601 - Informatica dalla A a Z

}

Esempio:

/* trovare il maggiore di tre interi */

#include <stdio.h>
int maximum(int, int, int);
int main() {
int a, b, c;
printf(“digita tre interi: ”);
scanf(“%d%d%d”,&a,&b,&c);

printf(“il massimo è: %d”,maximum(a,b,c));
}
int maximum(int x, int y, int z)

{

int max = x;
if (y > max) max = y;
if (z > max) max = z;
return max;
}

Tra gli algoritmi di ricerca più famosi, troviamo quello della “Ricerca binaria”.

Se dovessimo cercare una parola su un dizionario, sapendo che questo è ordinato alfabe-
ticamente, si potrebbe pensare di iniziare la ricerca non dal primo elemento, ma da quello

centrale, cioè a metà del dizionario. A questo punto il valore ricercato viene confrontato
con il valore dell’elemento preso in esame e se sono uguali la ricerca termina con successo,
altrimenti si sceglie la metà del dizionario su cui continuare la ricerca (la prima metà se la

parola cercata è minore di quella centrale, la seconda metà altrimenti) e si riapplica il pro-
cedimento descritto. Quando la parte del dizionario da scegliere per proseguire coincide
con una singola parola, l’algoritmo termina perché l’elemento cercato non è presente.

Nel caso in cui si abbia il vettore ordinato in maniera crescente, è possibile utilizzare un
algoritmo di ricerca simile a quello utilizzabile per il dizionario.

Si calcola la posizione dell’elemento centrale M del vettore partizionando i rimanenti ele-
menti in due sottoinsiemi ordinati A (con elementi tutti minori di M) e B (con elementi tutti
maggiori di M). Se l’elemento cercato K è uguale a M, l’algoritmo termina con successo; in

caso contrario, se K < M si riapplica il procedimento al sottoinsieme A, altrimenti al sot-
toinsieme B. Se non è possibile determinare un elemento centrale l’algoritmo termina con
insuccesso, senza che K sia stato trovato.

597