Discussion :

[outlander]

bonjours ,

j'ai implémenter un code qui fonctionne pratiquement comme un solveur de scrabble , mon problème est que lorsqu'il s'agit de 10 lettres l'exécution prendrais 9 (selon mes estimation)

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
 
#include<iostream>
#include<string>
#include<algorithm>
#include<list>
#include<vector>
#include<fstream>
 
using namespace std;
 
 
int dicho_rech(vector<string> vect, string mot)
{
   int centre;
   int bas=0;
   int haut=vect.size()-1 ;
   while(bas <= haut)
   {
      centre = (bas+haut)/2; // élément central de la partie traité
      if(mot.compare(vect[centre])==0) // valeur trouvée
         return centre;
      else if(mot.compare(vect[centre])<0)
         haut = centre-1; // recherche ds la partie inférieure du tableau
      else if(mot.compare(vect[centre])>0)
         bas = centre+1; // recherche ds la partie supérieure du tableau
   }
   return -1; // valeur recherchée non trouvée
}
 
 
string ltos_conversion(list<char> l)
{
     <a href="http://www.freelang.com/download/misc/liste_francais.zip" target="_blank">http://www.freelang.com/download/mis...e_francais.zip</a>
    list<char>::iterator it=l.begin() ;
    string s ="";
    s+=*it ;
    for (int i = 1 ; i<l.size();i++) { advance(it,1) ; s=s+*it; }
    return s ;
 
}
 
 
 
void print( list<char> l){
    for(list<char>::iterator it=l.begin(); it!=l.end() ; ++it)
            cout << *it;
    cout<<endl;
}
 
void subset(char arr[], int size, int left, int index, list<char> &l , vector<string>& words , vector<string> dicovec , int& j ,vector<string>&solval){
 
    if(left==0)
    {
        string s = ltos_conversion(l);
        std::sort(s.begin(),s.end());
        do
        {  
            solval.push_back(s);
            j++ ;
            if(j%1000==0) cout<<"boucle numero "<<j<<endl;
            int ind = dicho_rech(dicovec,s);
            if (ind!=-1) {  words.push_back(s) ; cout<<"une solution"<<endl;}
        }
         while (next_permutation(s.begin(),s.end())) ;
        return ;
    }
    for(int i=index; i<size;i++){
        l.push_back(arr[i]);
        subset(arr,size,left-1,i+1,l,words,dicovec,j,solval);
        l.pop_back();
    }
 
}    
 
int main(int argc,char** argv)
{
        ifstream dico("liste_francais.txt",ios::in);
        vector<string> words ;
        vector<string> dicovec ;
        vector<string> solvalvec;
    char array[10]={'a','g','u','e','r','i','c','f','p','r'};
    list<char> lt;
    int i =8;
    int k=0 ;
    string line ;
    while(getline(dico,line))   {  dicovec.push_back(line) ;}
    sort(dicovec.begin(),dicovec.end());
    while ((words.size()==0)&&(i>=1))
    {
         subset(array,8,i,0,lt,words,dicovec,k,solvalvec);
         i-- ;
 
    }
    for(i=0;i<words.size();i++) cout<<words[i]<<endl;
    dico.close();
    return 0;
}

le lien de dictionnaires utilisé :
http://www.freelang.com/download/mis...e_francais.zip

[dragonjoker59]

Cool!

Il prendrait 9 choux fleurs? Le voleur, faut empêcher ça!!!

EDIT:

Sinon ... Quelle est la question?

[outlander]

hhhhh vous avez raison .. j'ai oublier de mettre 9 heurs d'exécution
bon en effet je viens de résoudre le problème : il s'agit du passage par référence
Merci

[dragonjoker59]

C'est un exercice?
Ou un TP?

Es-tu convaincu qu'un vector soit la structure la plus appropriée sachant que tu vas faire des recherches dedans?

[outlander]

bon je ne suis po douée en matière du choix de structure mais le vector avais l'accès le plus rapide je crois

[dragonjoker59]

Oui, mais il n'est pqs du tout fait pour la recherche d'éléments, surtout des chaines.
Regarde du côté de std::set ou std::unordered_set, ces deux classes t'aideront certainement plus...

[outlander]

je les avais utiliser dans une version antérieure mais j'ai réviser cette utilisation afin d'améliorer le temps d’exécution qui était une priorité pour moi
enfin je viens de réduire le temps d'exécution à 6 sec grâce au passage par référence (je sais que ça a l'air débile le faite de ne pas l'avoir utilisé dés le début)
bon vu que vous êtes un expert en C++ et en programmation je me demande si je pourrais demander votre aide a ce qui concerne un autre code ... je sais que je deviens un peu trop abusive et je suis vraiment désolé pour ça mais j'en trouve plus des solutions

[dragonjoker59]

Pas de problème, mais ouvre un autre post pour ça (et mets celui-ci en résolu, si ton problème est résolu).

[white_tentacle]

Un vecteur trié sera meilleur qu’un set (ici on lit tout, puis on trie, puis lecture seule uniquement donc vector sera meilleur). set peut être meilleur si les insertions sont relativement fréquentes.

Sinon, pour la recherche dichotomique, std::lower_bound sera probablement plus efficace que ton implémentation (cela dit, si c’est un exercice). Néanmoins, si la performance est un but en soi, il faudra alors plutôt utiliser une structure spécifique (généralement, un arbre avec pour chaque nœud/feuilles les lettres possibles formant un mot correct et un éventuel marqueur de terminaison).