Ricerca dicotomica aiuto

di il
6 risposte

Ricerca dicotomica aiuto

Salve sto realizzando un programma per la scuola ed il professore non ci ha spiegato come si fa la ricerca dicotomica e vuole che lo implementiamo in un programma già svolto sull'ordinamento dei vettori... Ho cercato un pò su internet (anche in questo forum) e alla fine sono riuscito a stendere un pò di righe ma a volte quando fa la ricerca non mi trova certi valori..
#include <iostream>
using namespace std;
int n,i,v[10],dim=20,m,j,k,cont,app;
//------------------------------------------------------------------------------
void dimensione_N ()
{
  cout<<"Inserire la dimensione n del vettore (max 20)"<<endl;
    do
      cin>>n;
    while (n<=1 || n>dim);
}
//------------------------------------------------------------------------------
void lettura_vettore ()
{
  cout<<"\nLettura del vettore:\n"<<endl;
     for (i=0;i<n-1;i++)
     cin>>v[i];
     
}
//------------------------------------------------------------------------------

void leggi_k ()
{
     cout<<"Leggi k: "<<endl;
     cin>>k;
}
//------------------------------------------------------------------------------
void ricerca_elemento ()
{
   int pos,i,j,sx=0,dx=n-1,md;
   bool trovato=false;
   for (i=0;i<n-2;i++)
   {
   for (j=i+1;i<n-1;i++)
   {
       if (v[i] >v[j])
       {
                app=v[i];
                v[i]=v[j];
                v[j]=app;
       }        
    }  
    }  
    do
    {
                int md=(sx+dx)/2;
                if ((v[sx]==k)||(v[dx]==k)||(v[md]==k))
                trovato=true;
                else
                if (v[md]<k)
                sx=md+1;
                else
                dx=md-1;
                }
                while ((sx<=dx)&&(!trovato));
                if (trovato==true){
                cout<<"TROVATO!"<<endl;
                }
                else
                cout<<"NON TROVATO!"<<endl;
           
}

//------------------------------------------------------------------------------
int main()
{
//lo farò dopo
    system("PAUSE");
    return 0;
}

praticamente ho provato ad usare anche la variabile booleana però il professore non vuole
in sostanza richede di utilizzare la ricerca dicotomica per cercare un elemento k nel vettore letto col ciclo e contare quante volte k è presente e stampare a video anche la posizione..(non ho ancora fatto i parametri)
come si fa? grazie a tutti

6 Risposte

  • Re: Ricerca dicotomica aiuto

    Allora, si presuppone che il vettore sia ordinato (ad esempio crescente), se così non fosse la ricerca dicotomica non ha utilità, quindi potresti anche implementare, così da rendere l'esercizio più completo e far buona impressione anche al prof , una funzione per l'ordinamento (con algoritmo BubbleSort, QuickSort,MergeSort,ecc.). Supponiamo però che il vettore sia ordinato, per la funzione di ricerca dicotomica il mio consiglio è quello di utilizzare la 'ricorsione'.
  • Re: Ricerca dicotomica aiuto

    Non so cosa sia la ricorsione.. però potresti farmi un esempio dell'algoritmo di ricerca dicotomica?
  • Re: Ricerca dicotomica aiuto

    A questo indirizzo trovi gli esempi di ricerca dicotomica con e senza ricorsione, in C, Java e C#.

    Come ti è già stato fatto notare l' array deve essere ordinato.

    Di solito gli algoritmi ti restituiscono la posizione del primo elemento che trovano, che non è detto sia il primo presente nell' array (ve ne può essere più di uno ma dato che l' array è ordinato sono contigui), quindi se li devi contare, devi arretrare fino al primo e poi avanzare fino all' ultimo (ad esempio pensa ad un array con tutti gli elementi uguali, il primo che viene trovato è nel mezzo).

    Spero di essere stato chiaro.
  • Re: Ricerca dicotomica aiuto

    Si lo so che devo ordinarlo prima il vettore e su wikipedia avevo già controllato ma l'esempio è con il c e poi fa la ricerca in un vettore già definito mentre io lo leggo tramite un ciclo for... poi vorrei sapere anche come ottenere la posizione dell'elemento cercato con il metodo dicotomico
  • Re: Ricerca dicotomica aiuto

    La posizione dell'elemento la ottieni in quanto non è nient'altro che il valore degli estremi di ricerca nel punto, ovvero: con la ricerca dicotomica tu parti dall'intero intervallo, e poi lo dimezzi di volta in volta variando uno solo dei due estremi a e b, in modo che il tuo valore sia sempre compreso in [a,b]. Ad un certo punto, a furia di dimezzare, otterrai un intervallo di un solo valore, ovvero a=b (gli estremi dell'intervallo sono uguali). La posizione dell'elemento non è nient'altro che quel valore.
  • Re: Ricerca dicotomica aiuto

    sim0125 ha scritto:


    si lo so che devo ordinarlo prima il vettore e su wikipedia avevo già controllato ma l'esempio è con il c e poi fa la ricerca in un vettore già definito mentre io lo leggo tramite un ciclo for...
    Il C è un sottoinsieme del C++, l' esempio su Vikipedia è perfetto anche in C++. Prova a copiarlo e mettilo nel tuo programma vedrai che si compila.

    Il tuo programma si compone di diverse fasi:

    - Lettura dell' array (questo lo hai gia scritto)

    - Ordinamento dell' array (questo ti manca, magari puoi inserire l' array già ordinato)

    - A questo punto puoi usare la funzione di ricerca dicotomica richiamandola nel seguente modo:

    int pos = RicercaDicotomica(v, n, k); // n=dimensione array; k=elemento da cercare

    - Ti è stata restituita la posizione dell' elemento, ora puoi contare quanti ce ne sono guardando prima e dopo questa posizione.
Devi accedere o registrarti per scrivere nel forum
6 risposte