Discussion :

[phil23]

bonjour,
voici un programme de recherche dicothomique,mon probléme est que se programme ne retrouve que 2 mots rentrés sur 3.
pourriez-vous m'aider?
merci[QUOTE]

Description:
Recherche dichotomique d'un mot dans le dictionnaire*/

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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
#define MAXMOTS 100
#define LONGMOT 20
 
short dichotomie(char**dico,char*mot,short nb_mots);
int main(void)
{
	/*déclaration et initialisation des variables*/
	short nb_mots=1;
	char*mot;
	char**dico;
	int termine;
	short motrouve;
	termine=0;
	mot=malloc(LONGMOT *sizeof(char));
	dico=malloc(MAXMOTS *sizeof(char*));
	/*Saisi des mots du dictionnaire*/ 
	while((termine!=1)&&(nb_mots<MAXMOTS))
	{
		printf("Entrez un mot (fin pour terminer): ");
		scanf("%s",mot);
		if (strcmp(mot,"fin")==0)
		{
			termine=1;
		}
		else
		{
			*(dico+nb_mots)=malloc(strlen(mot)+1);
			strcpy(*(dico+nb_mots),mot);
			nb_mots++;
		}
	}
	motrouve=dichotomie(dico,mot,nb_mots);
	if (motrouve==1)
	{
		printf("Le mot %s a ete trouve.\n",mot);
		scanf("%s",mot);
	}
	else 
	{
		printf("Le mot %s est introuvable.\n",mot);
		scanf("%s",mot);
	}
	/*libération d'espace mémoire*/
	free(mot);
	free(dico);
}
short dichotomie(char**dico,char*mot,short nb_mots)
{
	/*initialisation des variables*/
	int i,j,k,trouve,inter;
	i=0;
	j=nb_mots;
	k=(nb_mots/2);
	/*Saisi du mot à trouver*/
	printf("Entrez le mot a trouver: ");
	scanf("%s",mot);
	/*recherche du mot saisi dans le dictionnaire*/
	do
	{
		inter=i-j;
		k=(j+i)/2;
		trouve=strcmp(*(dico+k),mot);
		if (trouve>0) j=k;
		if (trouve<0) i=k;
		if (trouve==0) inter=1;
	}
	while(inter>1);
	/*renvoi resultat de la recherche*/
	if (trouve==1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

[Médinoc]

1. C'est code (), pas quote.
2. Tu devrais mettre l'ajout dans une fonction séparée.
3. Comment peux-tu faire une recherche dichotomique, tes mots ne m'ont pas l'air triés lorsque tu les ajoutes ?
4. Tu peux remplacer *(dico+nb_mots) par dico[nb_mots], tout simplement.
5. scanf("%s", mot) est l'une des deux pires utilisations possibles de scanf(). Utiliser fgets() et se débarrasser du \n.
6. Pourquoi passes-tu char* mot en paramètre alors que tu l'affectes dans ta fonction dichotomie() ?

[kromartien]

comme médinoc, il faut que tu remplaces scanf("%s",mot); par fgets(stdin,LONGMOT,mot); ou utiliser cette référence pour la saisie : http://emmanuel-delahaye.developpez.com/inputs.htm.

Si tu ne touve que deux mots sur trois c'est ton algorithme qui est probablement faux. Essaie de retracer son fonctionnement et tu verras qu'il est possible que des mots soient ignorés lors de la recherche.

Une dichotomie a pour objectif de trouver un point par approximation successives. Comme l'a dit Médinoc, ça implique que tu recherches sur une gamme de valeur déjà triée, sinon ça n'a pas de sens.

[phil23]

merci à vous,je vois ce que je peut faire, mais si vous avez d'autre sugestions, n'esitez pas.

[Emmanuel Delahaye]

merci à vous,je vois ce que je peut faire, mais si vous avez d'autre sugestions, n'esitez pas.

qsort() + bsearch(), c'est fait pour...