View Single Post

Dici's Avatar


Dici
10.13.2012 , 04:49 PM | #7
J'ai trouvé que ne faire que parler de l'alphabet sans l'expliciter était un peu léger alors le voici :

Problème élémentaire 1 :

Cette notation signifie qu'on veut changer l'état uniquement du pylône noté 1. Les pylônes rouges sont ceux reliés au centre, sauf le centre lui-même. (Les _ ont été utilisés uniquement pour gruger l'éditeur de texte du forum qui ne comprenait pas quand je mettais seulement des espaces entres les caractères.)

___________________0
_________________0___0
_______________1___0___0
_________________0___0
___________________0

Solution élémentaire 1 :


Cette notation signifie qu'on va modifier uniquement les pylônes notés 1 pour atteindre l'état final.

___________________1
_________________0___1
_______________1___0___0
_________________0___1
___________________1

Problème élémentaire 2 :

___________________0
_________________1___0
_______________0___0___0
_________________0___0
___________________0

Solution élémentaire 2 :

___________________0
_________________0___0
_______________0___1___1
_________________0___1
___________________1

Problème élémentaire 3 :

___________________0
_________________0___0
_______________0___1___0
_________________0___0
___________________0

Solution élémentaire 3 :

___________________0
_________________1___1
_______________0___1___0
_________________1___1
___________________0

Vous pouvez vérifier si ça vous chante, ça marche ! Notez que ces 3 problèmes élémentaires permettent de déduire les 6 autres problèmes élémentaires car il n'y a que 3 types de pylônes :
- les pylônes non reliés au centre
- les pylônes reliés au centre sauf le centre
- le centre

L'algorithme de résolution devient alors trivial :

Pour i de 1 à 9 faire
Si pylône(i) = 0 (*c'est-à-dire s'il est éteint, cela est à rentrer par l'utilisateur pour décrire la situation initiale*) alors résoudre_problème_élémentaire(type(pylône(i)) (*on suppose écrites ces fonctions c'est du scribouillage*)
Sinon rien
FIn pour

La fonction type sert à typer le pylône, c'est-à-dire à savoir s'il est le centre, s'il est relié au centre ou s'il n'y est pas relié.

La fonction résoudre_problème_élémentaire va modifier un tableau T (paramètre global) de telle sorte que si le problème élémentaire rencontré exige d'appuyer sur le pylône k, alors T(k) <- (T(k) + 1) mod 2. Cela signifie qu'on compte les changements modulo 2 effectués sur chaque pylône. Pourquoi modulo 2 ? Parce que changer un pylône 2n fois c'est comme ne pas le changer, le changer 2n+1 fois c'est comme le changer une fois.

Au final, le programme renvoit le tableau T rempli de 0 et de 1 qui indiquent à l'utilisateur sur quels pylônes il doit cliquer ou non. J'ai testé ig, et ça marche parfaitement. S'il y a une erreur ici, ça ne serait que de la recopie.

Le plus beau, c'est que j'ai remarqué que cet alphabet était généralisable à n'importe quel nombre impair de pylônes (dont un centre). Comme je l'ai déjà dit, le problème de taille 2n+1 est résolu en complexité O(n) par cet algorithme, il est clair que c'est optimal. Ca n'est probablement pas le seul aglorithme optimal, mais tout de même !