Des lettres, arbre lexicographique,recherche mot le plus long...
hippo27
Messages postés8Date d'inscriptionjeudi 9 décembre 2004StatutMembreDernière intervention 6 mai 2006
-
11 avril 2006 à 16:46
Guillemouze
Messages postés991Date d'inscriptionsamedi 25 octobre 2003StatutMembreDernière intervention29 août 2013
-
20 avril 2006 à 23:28
alors voila:
Tout d'abord bonjour.
J'ai un projet a effectuer:des chiffres et des lettres, en pascal, sous delphi6.
Je n'ai qu'un seul truc imposé:utiliser un arbre lexicographique( un arbre regroupant tous les mots avec un prefixe commun, la fin d'un mot etant reperee par un caractere special).
Et la, je bute, sur un probleme. j'arrive bien a trouver un mot dans cet arbre a partir d'un liste de lettres desordonnées(et encore pas a tous les coups...), mais je n'arrive pas a etudier toutes les possibilités offertes par ces lettres pour trouver le mot le plus long existant dans mon dictionnaire. Vous voyez? Et c'est la, que je fais appel a votre aide. Donc si vous avez des idees, ce serait sympa à vous de m'en faire part...ou si meme vous voulez plus de precisions.
Merci et a tres vite.
A voir également:
Ca peut servir mots le plus long
Ca peut servir mot le plus long - Meilleures réponses
Ca peut servir le mot le plus long - Meilleures réponses
Guillemouze
Messages postés991Date d'inscriptionsamedi 25 octobre 2003StatutMembreDernière intervention29 août 20136 14 avril 2006 à 13:39
ca aurai ete cool de rajouter ta structure.
moi je ferai un truc dans le genre
var
lettres : array[0..8] of char;
utilises : array[0..8] of boolean;
nbPlusLong : integer;
procedure recherche(noeudCourant : Noeud, profondeur : integer);
var
i: integer;
begin
if (profondeur > nbPlusLong) and (NoeudCourant.isFinDeMot) then
begin
nbPlusLong := profondeur;
end;
for i:= 0 to 8 do
begin
if (not utilise[i]) and (noeudCourant.fils[lettres[i]] <> nil) then
begin
utilise[i] := true;
recherche(noeudCourant.fils[i], profondeu+1);
utilise[i] := false;
end;
end;
end;
//main
nbPlusLong := 0;
randomizeLettres(); //rempli ton tableau de lettres
recherche(racine,0); //racine est la racine de ton arbre
voila en gros ce que j'aurai fai. bien sur c pas complet mais ca sapproche de la solution.
hippo27
Messages postés8Date d'inscriptionjeudi 9 décembre 2004StatutMembreDernière intervention 6 mai 2006 15 avril 2006 à 14:10
Desole, j'ai mis un pêu de temps a repondre...
merci beaucoup, je vais essyaer, j'avais pense a un truc dans ce genre, mais j'avais l'impression de e pas essayer toutes les posibilités...
Je donne ma structure au cas ou quelqu un pourrait encore me conseiller:
dollar= '$', c'est une fauille ajoutée pour indiquer la fin d'un mot, on l'ajoute a chaque mot que l'on met dans l'arbre
T_ptr_ABL=^T_elt_ABL; //type d'un poointeur de l'arbre
T_elt_ABL=record //Element de l'arbre, contenant
lettre:char; //une lettre du mot, ou le caractere de fin de mot
frere:T_ptr_ABL; //un pointeur sur le frere: il pointe sur un aautre suffixe
fils: T_ptr_ABL; //un pointeur sur le fils, il pointe sur la fin de mot
end;
Pour que vous puuissiez vous faire une idee, je vous donne l'ajout:
Procedure AJOUT_MOT_ABL (var pcour:T_ptr_ABL;mot:T_mot;rang:integer)
//pcour =adresse du noeud courant
//mot:le mot a ajouter dans l'arbre
//rang: rang du mot a partir duquel on chaine les lettres
begin
//test d'arret de la recursivite
if rang "inferieur ou egal" à length(mot)
then//point d'insertion trouve
begin
if (pcour=NIL) or (pcour^.lettre "superieur à" mot[rang])
then //Point d insertion trouve
begin
CREATION_VD(mot[rang],pnouv)
pnouv^.frere:=pcour;
pcour:=pnouv;
//appel recursif avec le pointeur fils
AJOUT_MOT_ABL(pcour^.fils,mot,rang+1);
end
else
if pcour^.lettre=mot[rang]
then //le noeud existe deja, descente dnas ma recursivite
AJOUT_MOT_ABL(pcour^.fils,mot,rang+1);
else
AJOUT_MOT_ABL(pcour^.frere,mot,rang);
end;
end;
j'espere que la structure est clair maintenant. Si quelqu'un peut m'aider pour tester toutes les n! possibilités de mot, je l'en remercie d'avance.
Guillemouze
Messages postés991Date d'inscriptionsamedi 25 octobre 2003StatutMembreDernière intervention29 août 20136 18 avril 2006 à 13:55
heu je serais toi, je ferai un tableau a la place de ta liste chainée de freres. ca prend un peu plus de place, mais je pense pas que ce soit un gros pb, et c surtout bcp plus simple:
T_elt_ABL=record //Element de l'arbre, contenant
lettre:char; //une lettre du mot, ou le caractere de fin de mot
fils: array [1..26] of T_ptr_ABL; //un pointeur sur le fils, il pointe sur la fin de mot
end;
comme ca tu peu acceder directement a une lettre, tester son existance, ...
Guillemouze
Messages postés991Date d'inscriptionsamedi 25 octobre 2003StatutMembreDernière intervention29 août 20136 18 avril 2006 à 13:58
heuuu [0..26] si tu rajoute le caractere de fin de mot, ou alors tu met
T_elt_ABL=record //Element de l'arbre, contenant
lettre:char; //une lettre du mot, ou le caractere de fin de mot
fils: array [1..26] of T_ptr_ABL; //un pointeur sur le fils, il pointe sur la fin de mot
fin_de_mot : boolean; // vrai si cette lettre est la derniere d'un mot.
end;
Vous n’avez pas trouvé la réponse que vous recherchez ?
hippo27
Messages postés8Date d'inscriptionjeudi 9 décembre 2004StatutMembreDernière intervention 6 mai 2006 18 avril 2006 à 18:34
sympa pour le conseil, mais le problem, c'est que la structure de donnée est imposée...c'est sur que ce n'est pas le plus simple...merci pour tes conseils, je continue ma recherche de mot.
Si tu as un peu de temps a me consacrer, tu es le bienvenu.
A+
Merci
Guillemouze
Messages postés991Date d'inscriptionsamedi 25 octobre 2003StatutMembreDernière intervention29 août 20136 18 avril 2006 à 21:31
ok, ten est rendu ou?
je te conseille deja de faire une fonction
function getFils(noeudCourant: T_ptr_ABL; lettre: Char):T_ptr_ABL;
qui retourne le noeud fils du noeudCourant correspondant a la lettre (ou nil si il nexiste pas)
et une fonction
function isFinDeMot(noeud: T_ptr_ABL):Boolean;
qui te dis si le noeud est la derniere lettre d'un mot.
hippo27
Messages postés8Date d'inscriptionjeudi 9 décembre 2004StatutMembreDernière intervention 6 mai 2006 20 avril 2006 à 21:17
oui, j'avais justement debuté par ca, mais c toujour pareil, j'arrive a tester quelques possibilité, et encore ca marche pas toujours.en general, ca n''en fait qu'une. Je crois que je vais tout recommencer. J'arrivais a trouver un mot composé des lettres données (pas forcement dans l'ordre) mais pas plus, et en plus pas le plus long, seulement le premier dans l'alphabet.
J'attends toujours un pu d'aide.
Merci pour ce que tu fais
ä+