Srtucture ensemble de mots
Résolu
Bonjour,
je suis étudiant en informatique, et je dois créer une structure de donnée que représente un "langage" au sens d'un ensemble de mots de longueur inférieur à un n donné et obtenue à partir d'un alphabet.
Ex : j'ai un alphabet A={a,b}
=>Langage L2={a, b, ab, ba, aa, bb} si n=2
=>Langage L3={a, b, ab, ba, aa, bb, aaa, aba, aab, abb, baa, bab, bba, bbb} si n=3
Je vois pas bien comment réalisé ça, si quelqu'un aurait une piste, une idée pour m'aider ce serait sympa.
merci
je suis étudiant en informatique, et je dois créer une structure de donnée que représente un "langage" au sens d'un ensemble de mots de longueur inférieur à un n donné et obtenue à partir d'un alphabet.
Ex : j'ai un alphabet A={a,b}
=>Langage L2={a, b, ab, ba, aa, bb} si n=2
=>Langage L3={a, b, ab, ba, aa, bb, aaa, aba, aab, abb, baa, bab, bba, bbb} si n=3
Je vois pas bien comment réalisé ça, si quelqu'un aurait une piste, une idée pour m'aider ce serait sympa.
merci
2 réponses
-
ContributeurBonjour,
Le plus simple est d'utiliser un algorithme récursif.
Pour L1, ça fait {a,b}
Pour L2, ça fait L1+{aa, ab, ba, bb}
Pour L3, ça fait L2+{aaa, aab, ...}
...
Le plus dur est donc de calculer {aaa, aab, ...}
Tu peux utiliser un autre algorithme récursif (autre fonction) que t'appelleras autant de fois que le nombre i (Li).
Et dans cette fonction, tu renvoies en alternance a puis b. Je te laisse réfléchir sur ce point.
Voilà pour la piste ;-) -
Merci fiddy,
Ta solution semble être bonne mais je m'en sort plus dans les calcul quand je prend un alphabet très grand.
le calcul de Li devient super complexe...
