Discussion :

[stallaf]

Bonjour à tous,

Ma fonction de recherche dichotomique ne fonctionne pas et je ne trouve pas l'origine du mal. Le dico est trié correctement avec qsort() au préalable (merci E.D.). Pourriez-vous m'éclairer ? Merci d'avance.

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
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
/*  
    Fonction de recherche dichotomique.
*/
 
int dichotomie(char dico[][LONG_MOT], char mot[], int nbMots)
{
    int i = 0;   /* Indice de debut.  */
    int j = nbMots;   /* Indice de fin.  */
    int k = 0;   /*  Indice de milieu.  */
    int trouve = 0;   /*  Boleenne (faux si pas trouve.)  */  
 
    while (!trouve && ((j - i) > 1) )
    {				
         k = (i + j) / 2;
         if (strcmp (dico[k], mot) == 0) 
             trouve = 1;
 
         if (strcmp (dico[k], mot) > 0)
	         j = k ;
         else
	         i = k ;
    }
 
    if (dico[i] == mot)
        return (i);  
    else
        return (-1);  
}
 
int main (int argc, char *argv[])
{
    FILE *fiDico = fopen ("dico.dat", "r");
    ret = EXIT_SUCCESS ;
    int nbMots = 0;   /*  Valeur pour le nombre de mots.  */ 
    int resultat;   /*  Retour de la fonction.  */
    char ligne[LONG_MOT] = " ";   /*  Stockage des lignes des fichiers.  */
    char dico[MAX_MOTS][LONG_MOT] = { " " }; /* Dico.  */
    char mot[26] = " " ;   /*  Mot a rechercher.  */
 
    if (fiDico != NULL)
    {
        /*  Lecture du fichier et stokage dans le tableau "dico".  */
        while (nbMots < MAX_MOTS && fgets (ligne, LONG_MOT, fiDico) != NULL)
            {
                strcpy (dico[nbMots], ligne);
                nbMots++;
            }
        fclose (fiDico);
        fiDico = NULL;
 
        fputs ("\nTapez  le mot a rechercher dans le dictionnaire : ", stdout);
        fflush (stdout);
        fgets (mot, sizeof mot, stdin);    
        if (mot[strlen(mot) - 1]  == '\n')
            mot[strlen(mot) - 1] = '\0';  
 
        /* Recherche  dans dico.  */   
        resultat = dichotomie (dico, mot, nbMots); 
        if (resultat != -1)
        {
	    fprintf (stdout, "Ce mot se trouve déjà en position %d du dico.\n", resultat);
        }
        else
        {
            fprintf (stdout, "Ce mot n'est pas dans le dictionnaire!\n");    
        }
    }
    else
    {
        printf ("Clash de \"dico.dat\".");
        ret = EXIT_FAILURE;
    }
 
    fprintf (stdout, "Appuyez sur une touche...");
    getch ();
    return ret;
}

[Médinoc]

Code :

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

1
2
3
4
    if (dico[i] == mot)
        return (i);  
    else
        return (-1);

Là, aussi, tu dois utiliser strcmp().

[stallaf]

Affhh...Merci Médinoc .
C'est incroyablement difficile de perdre des habitudes du genre "égal à "
Mais corrigé c'est pareil, il ne me trouve aucun mot.

Code :

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

1
2
3
4
    if (strcmp (dico[i], mot) == 0 )
        return (i);  
    else
        return (-1);

J'enrage de pas voir.

[Climoo]

Je pense que ton erreur vient de ta condition d'arrêt de ta boucle while.
As-tu essayé par exemple, de mettre un ">=" plutôt qu'un ">" ?

Sinon, la meilleure chose à faire, et qui te sera plus profitable que si on te donne la solution comme cela, c'est de faire des affichages (printf..). Utilise un petit fichier source qui pose problème et affiche les numeros de tes indices de début et fin i et j systématiquement. Essaie de faire l'algorithme aussi à la main, et cherche les différences. Tu devrais rapidement trouvé la solution sur une petite fonction comme celle-ci... Bon courage

[stallaf]

Merci Climoo mais hélas ce n'est pas cela.
La comparaison est peut-être fausse en raison d'un '\n' ou autre chose du même genre. Mais là non plus, je séche.

[stallaf]

En vérifiant cette histoire de retour chariot j'ai oté la condition suivante après le fgets () :

Code :

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

1
2
if (mot[strlen(mot) - 1]  == '\n')
    mot[strlen(mot) - 1] = '\0';

Maintenant il trouve le premier mot de mon dico mais seulement celui-là.
Il faut maintenant trouver la logique de l'histoire et corriger pour l'ensemble.

[orfix]

Salut,

En vérifiant cette histoire de retour chariot j'ai oté la condition suivante après le fgets () :

Code :

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

1
2
if (mot[strlen(mot) - 1]  == '\n')
    mot[strlen(mot) - 1] = '\0';

Maintenant il trouve le premier mot de mon dico mais seulement celui-là.
Il faut maintenant trouver la logique de l'histoire et corriger pour l'ensemble.

Bon il faut se mettre d'accord soit tu enlèves les retours chariots mais, partout soit tu les laisses tranquille et les comparaisons se feront tout aussi bien ...parce que la tu n'enlevais que le '\n' des mots saisies par l'utilisateur pas ceux lus à partir du fichier ...

Pour ce qui est de ta fonction de recherche je pense que c'est clair tu utilises une booléenne dont le nom est assez explicite 'trouve' il est logique que le test pour savoir si le mot a été trouvé ou pas soit fait sur cette variable non ? sinon le 'k' n'est pas l'indice du mot mais, celui de la borne supérieure

[Djedje49]

Voici un exemple de recherche dicotomique :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int rechDichIt(int valRech, int tabEnt[], int taille)
{
     int deb = 0, fin = taille -1, mil;
 
     while (deb <= fin)
     {
    mil = (deb+fin)/2;
    if (valRech ==  tabEnt[mil]) return mil;
    if (valRech < tabEnt[mil]) fin = mil-1;
    else                       deb = mil+1;
     }
     return(-1);
}

Quand tu met à jour la position de début et de fin , il faut faire fin = mil-1 et deb = mil+1. Pour ton code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
     while (!trouve && ((j - i) > 1) )
    {                
         k = (i + j) / 2;
         if (strcmp (dico[k], mot) == 0) 
             trouve = 1;
 
         if (strcmp (dico[k], mot) > 0)
             j = k-1 ;
         else
             i = k+1 ;
    }

[stallaf]

Je ne pense pas qu'ajouter ou retrancher 1 aux bornes soit la source de mes problèmes; On gagne en effet en efficacité puisque la nouvelle borne devient le milieu plus ou moins 1. Ok je l'adopte.
J'ai encore un problème de compréhension globale : manque-t-il une boucle ...

[stallaf]

Résolu :

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
int dichotomie(char dico[][LONG_MOT], char mot[], int nbMots)
{
    int i = 0;              /* Indice de debut.  */
    int j = nbMots;         /* Indice de fin.  */
    int k = 0;              /*  Indice de milieu.  */
    int trouve = 1 ;		/*  Boleenne valant 1 (faux) tant que mot n'est pas trouve.  */  
 
    while ( (trouve == 1) && (i <= j) )
    {				
         k = (i + j) / 2;
         if (strcmp (dico[k], mot) == 0) 
             trouve = 0;
         if (strcmp (dico[k], mot) > 0)
             j = k - 1;
         else
	     i = k + 1; 
    }
    if (trouve == 0)
        return (i );
    else
        return (-1);  
}

Les conditions du while se portent bien mieux comme cela.
Merci pour votre aide.

[droggo]

Gao,

Résolu :

Code :

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

1
2
3
...
    int trouve = 1 ;		/*  Boleenne valant 1 (faux) tant que mot n'est pas trouve.*/
...

Normalement, 0 ==> false, et toute valeur <> 0 ==> true.

[stallaf]

Certes, mais l'énoncé est comme cela.
Le prof doit être un vicieux