Informatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nuova pagina: {{Informatica 2 Liceo Scientifico Scienze Applicate}} == Ricerca Dicotomica o Ricerca Binaria o Ricerca per Bisezione == La ricerca dicotomica e' la tecnica piu' veloce per ric... |
Nessun oggetto della modifica |
||
Riga 10:
Si prende la cella centrale del vettore che ha indice centro=(inf+sup)/2, la divisione e' fra interi e restituisce l'indice della cella centrale o quella della cella che la precede. Se siamo fortunati troviamo nella cella centrale il valore ricercato, altrimenti bisogna proseguire la ricerca , determinando un nuovo intervallo di ricerca<br />
* se valorericercato e' minore del valore della cella centrale pari a vett[centro]
il nuovo intervallo di ricerca e' compreso fra inf e centro-1 ,
cioe' si mantiene lo stesso valore inf e si aggiorna sup al valore centro-1 * se valorericercato e' maggiore del valore della cella centrale pari a vett[centro]
il nuovo intervallo di ricerca e' compreso fra centro+1 e sup ,
cioe' si aggiorna inf al valore centro+1 e si mantiene lo stesso valore per sup e poi si ripete il procedimento applicandolo al nuovo intervallo di ricerca.<br />
Line 84 ⟶ 86:
spostiamo sup al valore centro-1 ora sup=6 e manteniamo inf (che era 7) l'algoritmo termina non avendo piu' un intervallo di ricerca valido, infatti l'estremo inferiore e' diventato piu' grande di quello superiore, questo significa che non siamo riusciti a trovare il numero cercato (22) nel vettore<br />
L'algoritmo in C per fare una ricerca dicotomica su un vettore e' allora<br />
<source lang="c">
int sup,inf,centro;
string parolaricercata;
int posparolaricercata;
bool trovato;
cout<<"inserisci il nome da ricercare ";
cin>> parolaricercata;
trovato = false;
inf=0;
sup=n-1;
while ((!trovato)&&(inf<=sup))
{ centro=(inf+sup)/2;
if (vett[centro]==parolaricercata)
{trovato = true;
posparolaricercata = centro;
}
else
if ( parolaricercata > vett[centro])
inf=centro+1;
else
sup=centro-1;
}
if (trovato) cout<<"il nome si trova nella pos "<< posparolaricercata<<endl;
else cout<<" il nome non e' presente nel vettore"<<endl;
</source>
E un programma complessivo con l'inserimento dei dati , ordinamento e ricerca dicotomica e' il seguente<br />
<source lang="c">
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std ;
/* dato un vettore inserire i dati nel vettore, stampare il vettore disordinato,
ordinarlo con bubblesort e poi stampare il vettore ordinato, ricercare un
elemento all'interno del vettore disordinato visualizzando la posizione
tramite ricerca dicotomica
obiettivo: inserimento dati all'interno di un vettore
stampa vettore
ordinamento tramite bubblesort
concetto algoritmo
complessità stampa O(n)
complessita inserimento O(n)
complessita ordinamento O( n*n/2 )
complessità ricerca dicotomica O(log in base 2 di n)
algoritmo ricerca dicotomica
*/
int main(int argc, char *argv[])
{
int n = 4;
string vett[n];
int i,j;
string temp;
for (i=0;i<n;i++)
{ cout<<"inserisci il "<< i << " elemento ";
cin>>vett[i];
}
cout <<"il vettore disordinato e' "<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<endl;
}
cout <<endl;
for (i=1;i<n;i++)
for (j=n-1;j>=i;j--)
if (vett[j]<vett[j-1])
{ temp = vett[j];
vett[j]=vett[j-1];
vett[j-1]=temp;
}
cout <<"il vettore ordinato e' "<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<endl;
}
cout <<endl;
int sup,inf,centro;
string parolaricercata;
int posparolaricercata;
bool trovato;
cout<<"inserisci il nome da ricercare ";
cin>> parolaricercata;
trovato = false;
inf=0;
sup=n-1;
while ((!trovato)&&(inf<=sup))
{ centro=(inf+sup)/2;
if (vett[centro]==parolaricercata)
{trovato = true;
posparolaricercata = centro;
}
else
if ( parolaricercata > vett[centro])
inf=centro+1;
else
sup=centro-1;
}
if (trovato) cout<<"il nome si trova nella pos "<< posparolaricercata<<endl;
else cout<<" il nome non e' presente nel vettore"<<endl;
system("PAUSE");
return 0;
}
</source>
{{Avanzamento|75%|9 dicembre 2014}}
| |||