Erreur de recherche dichotomique

**stallaf** · 09/06/2008, 10h47

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** · 09/06/2008, 11h14

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** · 09/06/2008, 11h38

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** · 09/06/2008, 11h56

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** · 09/06/2008, 13h27

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** · 09/06/2008, 13h37

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.

**Djedje49** · 09/06/2008, 15h09

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** · 09/06/2008, 15h56

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** · 09/06/2008, 16h19

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** · 09/06/2008, 16h57

Gao,

Envoyé par stallaf

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** · 09/06/2008, 17h04

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

Erreur de recherche dichotomique

C

Vue hybride

Discussions similaires

Partager

Partager