Problème de retour de valeur dans ma fonction de recherche dichotomique

**mouchT8** · 24/05/2008, 15h50

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
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
#include<stdio.h>
#include<string.h>
 
 
//INITIALISATION
//initialisation de la fonction dichotomie
short dichotomie(char **dico,char *mot,short nb_mots){
 
int i,j,k;
 
i=0;
j= nb_mots;
 
for(i=0; i<=nb_mots -1; i++) {		//execution de la boucle tant que (i,j) supérieur à 1
									//puisque j=nb_mots, alors (i,j) sera supérieur à 1 pour
									//i< nb_mots -1
 
int moy;		//moyenne de(i,j)
moy=(i+j)/2;
k=moy;
}
 
if(dico[k] > mot) {
j=k;
}
else {
i = k;
}
 
 
//comparaison de mot avec le i ème et le j ème élément du dico
if (mot==dico[i]){return 0;}
if(mot==dico[j]){return 0;}
else{return 1;}
 
}
 
 
//EXECUTION
//PROGRAMME PRINCIPAL
 
int main(void){
 
char *mot;
short nb_mots;
//exemple d'initialisation de dico pour notre exemple
char *dico[5]={"arbre","voiture","cheval","malade","besoin"};
nb_mots=5;	//initialisation par exemple
 
 
//saisie par l'utilisateur du mot à rechercher
printf("Veuillez saisir un mot pour la recherche dichotomique: \n ");
scanf_s("%c",&mot);
 
//recherche dichotomique
dichotomie(dico, mot, nb_mots);
 
if(dichotomie(dico, mot, nb_mots)==0 ){
	printf("Le mot saisie est bien dans le dictionnaire!\n");
}
else {
	printf("Le mot saisie n'est pas dans le dictionnaire!\n");
}
 
return 0;
}

Mon probleme, c'est que quand, à l'exectution, je note par exemple "arbre",
il me dit que le mot n'appartient pas au dictionnaire...alors que si !!
Je pense qu'il y a un probleme au niveau de mes retours dr valeurs mais je ne vois pas ou ..

Quelqu'un peut m'aider??

**snake264** · 24/05/2008, 15h54

Au lieu de faire de cette manière pourquoi ne créée-tu pas un fichier .txt qui te sert de dictionnaire c'est beaucoup plus facile à faire

**droggo** · 24/05/2008, 16h14

Fai,

Tu n'aurais pas oublié une condition pour l'algorithme de recherche par dichotomie ?

Je te laisse chercher, c'est tellement élémentaire.

**yakamoneye** · 24/05/2008, 16h28

bien vu droggo !

**mouchT8** · 24/05/2008, 17h02

Envoyé par snake264

Au lieu de faire de cette manière pourquoi ne créée-tu pas un fichier .txt qui te sert de dictionnaire c'est beaucoup plus facile à faire

Parce que l'énoncé de mon exercice me dit de faire comme ça

**mouchT8** · 24/05/2008, 17h10

Envoyé par droggo

Fai,

Tu n'aurais pas oublié une condition pour l'algorithme de recherche par dichotomie ?

Je te laisse chercher, c'est tellement élémentaire.

Euuuuuuuh .... oui !

Je vais me creuser la tete, mais je ne vois pas ce que ça peut etre puisque j'ai suivit a la lettre (du moins je pense) l'énoncé de l'exercice !

Le voici, au cas ou:

La fonction aura la déclaration suivante:
short dichotomie (dico, mot, nb_mots)
char**dico;
char *mot;
short nb_mots;

Elle devra retourner la valeur 1 si mot est trouvé dans dico et 0 si non.
L'algorithme est le suivant :

-on utilise 3 variables i, j et k entières
-i initialisé a 0
-j initialis a nb_mots

Executer une boucle tant que l'intervalle (i,j) est supèrieur à 1:
-mettre dans k la moyenne de (i,j)
-si le k eme élément de dico est supèrieur à mot, mettre k dans j sinon mettre k dans i
-fin de la boucle
-comparer mot avec le ième et j ème élément de dico

Por tester la fonction, on pourra écrire un petit programme permettant ... blablabla

Effectivement je vois qu'il y a deux ou trois trucs que je n'ai pas respecté..
je m'en vais les changer mais je ne pense pas que ce soit ça qui ne fonctionne pas?

**souviron34** · 24/05/2008, 17h31

en plus, une grossière erreur :

les chaînes de caractères ne se compare pas avec == mais avec strcmp ...

**mouchT8** · 24/05/2008, 18h02

Envoyé par souviron34

en plus, une grossière erreur :

les chaînes de caractères ne se compare pas avec == mais avec strcmp ...

OH MY GOD !
OooooPS !!!!

Correction =>

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
#include<stdio.h>
#include<string.h>
 
 
//INITIALISATION
//initialisation de la fonction dichotomie
short dichotomie(char **dico,char *mot,short nb_mots){
 
int i,j,k;
int strcmp (const char *s1, const char *s2);
 
i=0;
j= nb_mots;
 
for(i=0; i<=nb_mots -1; i++) {		//execution de la boucle tant que (i,j) supérieur à 1
									//puisque j=nb_mots, alors (i,j) sera supérieur à 1 pour
									//i< nb_mots -1
 
int moy;		//moyenne de(i,j)
moy=(i+j)/2;
k=moy;
 
 
if(strcmp(dico[k],mot)>0) {
j=k;
}
else {
i = k;
}
}
 
 
//comparaison de 'mot' avec le i ème et le j ème élément du dico
 
if(strcmp(mot,dico[i])==0){return 1;}
if(strcmp(mot,dico[j])==0){return 1;}
else{return 0;}
 
 
}
 
//EXECUTION
//PROGRAMME PRINCIPAL
 
int main(void){
 
char *mot;
short nb_mots;
 
//exemple d'initialisation de dico pour notre exemple
char *dico[5]={"arbre","voiture","cheval","malade","besoin"};
nb_mots=5;	//initialisation par exemple
 
 
//saisie par l'utilisateur du mot à rechercher
printf("Veuillez saisir un mot pour la recherche dichotomique: \n ");
scanf_s("%c",&mot);
 
//recherche dichotomique
dichotomie(dico, mot, nb_mots);
 
if(dichotomie(dico, mot, nb_mots)== 1 ){
	printf("Le mot saisie est bien dans le dictionnaire!\n");
}
if (dichotomie(dico,mot,nb_mots)== 0) {
	printf("Le mot saisie n'est pas dans le dictionnaire!\n");
}
 
return 0;
}

Mais toujours le meme probleme...

Si je saisie "arbre" par exemple, il me dit qu'il n'est pas dans le dico..

**yakamoneye** · 24/05/2008, 18h17

extrait du man

SYNOPSIS
#include <string.h>

int strcmp (const char *s1, const char *s2);

DESCRIPTION
La fonction strcmp() compare les deux chaînes s1 et s2. Elle renvoie
un entier négatif, nul, ou positif, si s1 est respectivement
inférieure, égale ou supérieure à s2.

Code :

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

1
2
 
char *dico[5]={"arbre","voiture","cheval","malade","besoin"};

Code :

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

1
2
 
if(strcmp(dico[k],mot)>0)

voiture < cheval ?
malade > voiture ?

**orfix** · 24/05/2008, 18h48

Salut,

Envoyé par mouchT8

Si je saisie "arbre" par exemple, il me dit qu'il n'est pas dans le dico..

Tu ne risques pas de lire un mot avec ceci :

Code :

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

1
2
3
4
 
char *mot;
<...>
scanf_s("%c",&mot);

tu n'alloues pas de l'espace à 'mot'
%c lit un et un seul caractère

...Avant d'aller plus loin je te conseil fortement la lecture de ce TUTO !

**Emmanuel Delahaye** · 25/05/2008, 11h59

Envoyé par mouchT8

Voici mon code:

Code :

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

1
2
3
4
5
6
7
8
#include<stdio.h>
#include<string.h>
 
 
//INITIALISATION
//initialisation de la fonction dichotomie
short dichotomie(char **dico,char *mot,short nb_mots){
<...>

Il faut cesser de réinventer la roue...

1 - mettre les données dans un tableau
2 - trier le tableau avec qsort())
3 - rechercher avec bsearch().

**snake264** · 25/05/2008, 13h00

C'est vrai mais en même temps il n'avait pas vraiment le choix car cela lui étais imposé

**yakamoneye** · 25/05/2008, 14h51

en même temps faire une recherche dichotomique sur un tableau non trié, ...
y'en a qu'on essayé ...
J'suis pas certain qu'ils aient réussi

**snake264** · 25/05/2008, 16h11

On sait jamais avec une chance énorme ça peut éventuellement marché

**yakamoneye** · 25/05/2008, 16h35

Sur ce coup là je préfère misé sur le trie que sur la chance

**mouchT8** · 28/05/2008, 14h09

hum...
tres interessantes ces petites plaisanteries mais ça ne maide pas du tout !!

**yakamoneye** · 28/05/2008, 17h28

Désolé

Le principe d'une recherche dichotomique est de choisir un "centre" appartenant au tableau et de comparer grace à une relation d'ordre ici "strcmp()" l'element recherché
si ton tableau est trié en ordre croissant et que l' element est strictement plus petit que le centre alors l'élément se trouve entre le début du tableau et le "centre" ...
si il est strictement plus grand alors il se trouve entre le "centre" et la fin.
Si il est egal c'est gagné !

Si ton tableau est rangé par ordre décroissant et que l'élément recherché et plus petit que le centre alors il se trouve entre le "centre" et la fin du tableau.
Sinon il se trouve entre le debut et le "centre".
si il est égal c'est gagné !

si on a bien choisi le centre on peut effectuer un appel recursif de notre fonction de recherche en ajustant les indices de debut ou de fin selon le cas,
fin = centre ou debut =centre

Si le tableau n'est pas trié impossible de savoir dans quelle partie effectuer la prochaine recherche !

**mouchT8** · 28/05/2008, 17h33

ah oui merci!!

C'était expliqué sur mon devoir mais pas aussi bien on va dire

Il faut donc que je tri mon tableau dabord... ca n'a pas l'air bien compliqué!!
je vais essayer cela !!!

Sinon j'ai aussi un nouveau probleme !!

eh oui..
j'ai changer mon %c en %s pour lire mon "mot" mais ça bug !!!

Moi pas comprendre

**souviron34** · 28/05/2008, 17h50

si ton code est le meme qu'au dessus, et que tu n'as pas pris en compte la remarque d'Emmanuel, c'est normal..

%s demande une chaine, pas un pointeur non alloue...

**yakamoneye** · 28/05/2008, 17h58

Si tu veux etre tranquille comme tu t'attends à ne pas lire des mots de plus de 255 characteres, declare toi un buffer statique de 256 char

Code :

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

1
2
3
4
 
char buffer[256];
printf("entrez un mot :\n>");
scanf("%s", buffer);

cette méthode est critiquable! mais pour le moment ça ira

Problème de retour de valeur dans ma fonction de recherche dichotomique

C

Discussions similaires

Partager

Partager