Des lettres, arbre lexicographique,recherche mot le plus long...

Question

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&#233;: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&#233;es(et encore pas a tous les coups...), mais je n'arrive pas a etudier toutes les possibilit&#233;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 &#224; vous de m'en faire part...ou si meme vous voulez plus de precisions.
Merci et a tres vite.

Guillemouze · Answer

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 · Answer

Desole, j'ai mis un p&#234;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&#233;s...
Je donne ma structure au cas ou quelqu un pourrait encore me conseiller:

dollar= '$', c'est une fauille ajout&#233;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" &#224; length(mot)
   then//point d'insertion trouve
         begin
               if (pcour=NIL) or (pcour^.lettre "superieur &#224;" 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&#233;s de mot, je l'en remercie d'avance.

Merci GUILLEMOUZE.
A+

Guillemouze · Answer

heu je serais toi, je ferai un tableau a la place de ta liste chain&#233;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 · Answer

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;

hippo27 · Answer

sympa pour le conseil, mais le problem, c'est que la structure de donn&#233;e est impos&#233;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 · Answer

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 · Answer

oui, j'avais justement debut&#233; par ca, mais c toujour pareil, j'arrive a tester quelques possibilit&#233;, 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&#233; des lettres donn&#233;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
&#228;+

Guillemouze · Answer

si tu veu tupeu menvoyer ton code, je peu essayer de jeter un oeil vite fait

Des lettres, arbre lexicographique,recherche mot le plus long...

8 réponses

Votre réponse

Discussions similaires