Discussion :

[galiaker]

dans l'algorithme suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
recherche_dichotomique_récursive(élément, liste_triée):
   m = longueur de liste_triée / 2 ;
   si liste_triée[m] = élément :
       renvoyer m ;
   si liste_triée[m] > élément :
       renvoyer recherche_dichotomique_recursive(element, liste_triee[1:m]) ;
   sinon :
       renvoyer recherche_dichotomique_recursive(element, liste_triee[m:l]) ;

j'aimerai savoir comment on fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 liste_triee[1:m]

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 liste_triee[m:l]

via des vecteur.

Voici mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
/**
 @brief recherche un mot dans le dictionnaire via une recherche dichotomique              
 
 @param dico (vector<string>) Vecteur qui contient le dictionnaire
 @param mot  (string)         Mot à rechercher
  
 @return retourne vrai si le mot a été trouvé autrement faux
 */
bool rechercheDichotomiqueRecursive(vector<string> dico, string mot){
 
    size_t indiceMilieu = dico.size()/2;
    if(dico.at(indiceMilieu) == mot){
        return true;
    }
    if(dico.at(indiceMilieu) > mot){
        rechercheDichotomiqueRecursive(dico,mot);
    }
    else{
        rechercheDichotomiqueRecursive(dico,mot);
    }
    return false;
}

[Bysbobo]

Pour moi, tu as trouvé la solution quand tu as posé la question

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
bool rechercheDichotomiqueRecursive(vector<string> const &dico, string const &mot, int indiceDeb, int indiceFin)
{
    size_t indiceMilieu = (indiceFin + indiceDebut)/2;
    if(dico.at(indiceMilieu) == mot){
        return true;
    }
    if(dico.at(indiceMilieu) > mot){
        rechercheDichotomiqueRecursive(dico, mot, indiceMilieu, indiceFin);
    }
    else{
        rechercheDichotomiqueRecursive(dico, mot, indiceDebut, indiceMilieu);
    }
    return false;
}

Par exemple?

[dalfab]

Bonjour,

Tu as obtenue une solution basée sur le côté C du C++ : ne pas fabriquer d'objets inutiles.
Attention, il faut faire plutôt size_t indiceMilieu = (indiceFin + indiceDebut)/2;.

Si on regarde le côté Python du C++, on peut créer des vector : j'ai du CPU et de la mémoire à revendre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
    if (dico.at(indiceMilieu) > mot){
        rechercheDichotomiqueRecursive( vector<string>(next(dico.begin(), indiceMilieu),dico.end()) , mot );
    }
    else{
        rechercheDichotomiqueRecursive( vector<string>(dico.begin(), next(dico.begin(), indiceMilieu+1)) , mot);
    }

Personnellement j'opte plutôt pour la version économe.

[Bysbobo]

Bonjour,

Tu as obtenue une solution basée sur le côté C du C++ : ne pas fabriquer d'objets inutiles.
Attention, il faut faire plutôt size_t indiceMilieu = (indiceFin + indiceDebut)/2;.

Toutes mes excuses pour cet indice baclé, j édite en conséquence

[galiaker]

Bonjour,

Tu as obtenue une solution basée sur le côté C du C++ : ne pas fabriquer d'objets inutiles.
Attention, il faut faire plutôt size_t indiceMilieu = (indiceFin + indiceDebut)/2;.

Si on regarde le côté Python du C++, on peut créer des vector : j'ai du CPU et de la mémoire à revendre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
    if (dico.at(indiceMilieu) > mot){
        rechercheDichotomiqueRecursive( vector<string>(next(dico.begin(), indiceMilieu),dico.end()) , mot );
    }
    else{
        rechercheDichotomiqueRecursive( vector<string>(dico.begin(), next(dico.begin(), indiceMilieu+1)) , mot);
    }

Personnellement j'opte plutôt pour la version économe.

Je n'ai pas très bien compris se que tu fais dans la parentheses de ma fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

rechercheDichotomiqueRecursive( vector<string>(next(dico.begin(), indiceMilieu),dico.end()) , mot )

idem pour la suivant. si tu arriverai a me faire une petit expliquation ça serait cool.

[dalfab]

idem pour la suivant. si tu arriverai a me faire une petit expliquation ça serait cool.

La ligne fait ce que tu demandes, elle crée une liste allant du milieu à la fin (et du début au milieu).
On peut la décomposer en plusieurs lignes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
   auto debutDeDico = dico.begin();     // itérateur dans dico sur le début
   auto apresFinDeDico = dico.end();    // itérateur dans dico après la fin
   auto milieuDeDico = next( debutDeDico , indiceMilieu ); // next() permet d'ajouter un déplacement à un itérateur
   auto apresMilieuDeDico = next( milieuDeDico , 1 ); // on veut aussi un itérateur après le milieu
   // un nouveau vecteur peut être construit en lui passant 2 itérateurs dans une collection
   // le premier indique le premier élément, le second doit être après le dernier élément à prendre.
   vector<string> vecteurPremiereMoitie( debutDeDico , apresMilieuDeDico );
   vector<string> vecteurSecondeMoitie( milieuDeDico , apresFinDeDico );
   if ( dico.at(indiceMilieu) > mot )
        rechercheDichotomiqueRecursive( vecteurSecondeMoitie , mot );
    else
        rechercheDichotomiqueRecursive( vecteurPremiereMoitie , mot);