par Ben314 » 27 Fév 2017, 06:16
A tout moment, dans la mémoire de l'ordi. j'ai deux variables entières n et m ainsi qu'un tableau de chaines de caractère qui décrit les disposition et un tableau d'entier "couplé" au premier qui dit pour chaque disposition combien de façon de l'obtenir il y a.
Le seul truc à comprendre, c'est comment les chaines de caractères "codent" les dispositions et je pensait que c'était clair avec les exemples donnés par les posts. précédents.
Les chaines sont formés des caractères 0, X , a , b ,c ,d et chaque caractère correspond à un point sur la grille, les ponts étant alignés sur une diagonale de longueur n lorsque l'on a m=n et, si m<n, les m premiers points sont ceux du début le la diagonale de longueur n et les suivants sont sur la diagonale d'au dessus.
Aprés, le codage est simple : un 0 signifie que le point n'a pas d'arête partant ni vers le haut, ni vers la gauche, un X qu'il a les deux et une lettre a,b,c,d signifie qu'il a un seul des deux (gauche ou haut) et que si on suit le parcours correspondant, le chemin "ressort" du triangle sur l'autre point (unique) ayant comme code la même lettre.
Par exemple, l'avant dernier post. te dit que, lorsqu'on en est à n=m=4, après "compactage", le tableau de chaine de caractères c'est :
[ "aabb" , "a0Xa" , "0aXa" , "aaX0" , "abba" , "0Xaa" , "aXa0" , "aX0a" ]
et que le tableau de décompte c'est
[2 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ]
i.e. que seule la premiére disposition a deux façon d'être obtenue.
Arrivé à ce point, le programme va créer deux nouveau tableaux (dispo + Nb) correspondant à n=5 , m=2 en partant de ces deux là. Le passage de n=m=4 à n=5 , m=2 consiste à mettre deux points suplémentaire sur la diagonale suivante, ce qui "isole" le premier point de la diagonale précédente à l'intérieur du triangle et il faut absolument compléter le nombre d'arêtes partant de ce point pour qu'il en ait 2 :
Dans la dispo. "aabb" , il y a déjà une arrête partant du premier point. Pour passer à 2, on peut soit en mettre une vers le bas ce qui "produit" la dispo. "a0abb", soit en mettre une vers la droite ce qui produit "0aabb". Dans les deux cas, on met évidement 2 comme "nombre des possibilités" vu qu'il y avait 2 possibilités pour "aabb".
De même, la dispo. "a0Xa" va produire "a00Xa" et "0a0Xa" avec 1 comme "nombre des poss." pour les deux.
La dispo. "0aXa" va produire "bbaXa" uniquement avec 1 comme "nombre des poss" pour les deux.
etc...
Et ça te donne le nouveau tableau correspondant à n=5 , m=2 (et tu peut jeter à la poubelle le précédent qui ne servira plus).
Idem, partant de ce tableau, tu va créer celui correspondant à n=5 , m=3 :
La dispo. "a0abb" va produire "aa0bb" et "a0abb" avec 2 comme "nombre des cas". (fait un dessin)
La dispo. "bbaXa" va produire "bX0Xb" et "bbaXa" avec 1 comme "nombre des cas". (fait un dessin)
etc...
A chaque fois, le but est de compléter le nombre d'arêtes partant du point qui va se retrouver à l'intérieur du triangle de façon à ce qu'il en ait exactement 2.
S'il en a 0, faut en ajouter 2 et y'a pas le choix. S'il en a 2, faut rien rajouter et y'a pas le choix. Et s'il en a 1, il faut en rajouter 1 et y'a deux possibilité : vers le bas ou vers la droite.
Après, vu que c'est ni très long (en temps), ni compliqué, ça peut se programmer avec n'importe quel langage de programmation, aussi basique soit il. Et ça serait pas con qu'il y ait au moins une autre personne qui le fasse pour confirmer le résultat...
Modifié en dernier par
Ben314 le 28 Fév 2017, 22:25, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius