Recherche dichotomique

Fermé
Turinois - 26 déc. 2005 à 13:09
migalo Messages postés 1 Date d'inscription mardi 19 février 2008 Statut Membre Dernière intervention 20 février 2008 - 20 févr. 2008 à 20:39
Bonjour,

je dois coder ceci en C mais je n'arrive pas.
Si vous pouviez s'il vous plait à écrire un algo ou pseudo code qui puisse facilement se coder en C.

Merci d'avance de votre aide

On considère une liste de n chaines de caractères mémorisée dans une table T.
La longueur maximale des chaines T[0],T[1],...,T[n-1] est notée M.
On note <= l'ordre lexicographique et on suppose que :
T[0]<=T[1]<=...<=T[n-1]

On considère un chaine x de longueur m (|x| = m)
Ecrire un algo qui fait la recherche dichotomique de x dans T en utilisant la comparaison de caractère

2 réponses

Z3uS-Su3Z Messages postés 94 Date d'inscription lundi 30 mai 2005 Statut Membre Dernière intervention 11 juin 2007 12
27 déc. 2005 à 17:37
Salut,

100 balles et un mars avec ?

On va pas te faire ton boulot quand même...

Juste un petit coup de pouce comme :


Si je me trompe pas (mes cours d'algo sont loins) la recherche dicotomique dans le principe c'est de couper en deux récursivement les données jusqu'a avoir trouvé ou pas...

Je sais c'est un peu obscure, un petit exemple :

Cela suppose un tableau de données trié comme :
[cool][dificille][excellent][pathétique][terrible]

On recherche mettons [dur], le tableau est de taille 5 on commence a se positionner donc à 5/2 = 2 (division entiere), ce qui fait kon a [excellent], [dur] étant "inférieur" si il existe il se situe entre 0 et 1 compris soit un nouveau tableau :

[cool][difficile] de taille 2, 2/2=1 on se positionne sur [difficlle], [dur] étant inférieur à 2 et supérieur à 1, il n'existe donc pas....

Voilà le principe...
1
migalo Messages postés 1 Date d'inscription mardi 19 février 2008 Statut Membre Dernière intervention 20 février 2008
20 févr. 2008 à 20:39
salut cé migalo j veu avoir dé ami contactez moi a duncun@hotmail.fr
0