Enigmo 176 : Des petits tours pour une tour

Posté par 1emeu 1emeu

Bonjour,

voici une description de l'algorithme utilisé:
on cherche les mots constitué de b,h,g, et d vérifiant les conditions suivantes (où #g dénote le nombre de g dans le mot):

- (C1) #b-#h=2  et  #g-#d=0
- (C2) pour tout sous-mot, #b-#h différent de 0 ou #d-#g différent de 0   (pour éviter les boucles).
- (C3) pour tout sous-mot,   0 <= #b-#h <= 2 et 0 <= #d-#g <= 4 (pour éviter de sortir du cadran)

Voici à présent l'algorithme (m|g dénote la concaténation du mot m avec le symbole g). Pour afficher l'ensemble des chemins, il suffit de l'exécuter avec le mot vide en entrée.

AfficheChemins(m)
Entrée: un mot m sur l'alphabet {g,d,h,b}

si m ne vérifie pas les conditions C2 et C3 alors
   arreter;
fin si;

si m vérifie les conditions C1, C2 et C3
   afficher (m);
   arreter;
fin si;

si m vérifie les conditions C2, C3 mais pas C1
   AfficheChemins(m|g);
   AfficheChemins(m|d);
   AfficheChemins(m|h);
   AfficheChemins(m|b);
   arreter;
fin si;



1emeu

Posté par manpower manpower

Merci à caylus pour la version basic _{(qu'effectivement je comprends bien mieux)} et à 1emeu pour l'algorithme limpide.