Tour de Hanoï.
Tour de Hanoï.
Salut à tous !
(Explication du jeu : (par exemple) https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF) (Les matheux sont partout !)
(Entrainement : (par exemple) http://jeux.prise2tete.fr/tour-de-hanoi ... -hanoi.php)
Je cherche un algorithme pour réussir une partie à n palettes.
En notant H donnant le déplacement (nombre de palettes, tour de départ (noté D), tour d'arrivé (noté A), tour non utilisé (noté I)), pour 3 palettes on trouve :
H(3,D,I,A) *En tête de la fonction*
H(2,D,I,A) *Depuis la tour de départ on met tout, sauf la plus grande plaquette, au milieu* *puis en jouant on voit qu'on fait : *
H(1,D,A,I)
H(1,D,I,A)
H(1,A,I,D)
H(1,D,A,I) *On met la plus grand plaquette restante sur la tour d'arrivé*
H(2,I,A,D) *Depuis le tour du milieu on met tout sur la tour d'arrivé* *puis en jouant on voit qu'on fait : *
H(1,I,D,A)
H(1,I,A,D)
H(1,D,A,I)
On remarque une symétrie entre les deux appels récursifs en gras, c'est la même fonction mais pas les mêmes arguments ! Et la fonction du milieu H(1,D,A,I) se retrouve au début des deux autres.
Bref, on essayant tout et n'importe quoi j'ai trouvée la réponse (car elle apparaît ci dessus) : H(n,D,I,A) est
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
Mais je ne suis pas satisfait car en testant la réponse pour n = 3 je n'arrive pas à retrouver mon résultat empirique, je trouve des parcours incohérent qui montre que je dois me tromper quand je développe la fonction récursive.
Pouvez-vous m'aidez à la développer pour n = 3 afin que je conclue s'il vous plait.
(Explication du jeu : (par exemple) https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF) (Les matheux sont partout !)
(Entrainement : (par exemple) http://jeux.prise2tete.fr/tour-de-hanoi ... -hanoi.php)
Je cherche un algorithme pour réussir une partie à n palettes.
En notant H donnant le déplacement (nombre de palettes, tour de départ (noté D), tour d'arrivé (noté A), tour non utilisé (noté I)), pour 3 palettes on trouve :
H(3,D,I,A) *En tête de la fonction*
H(2,D,I,A) *Depuis la tour de départ on met tout, sauf la plus grande plaquette, au milieu* *puis en jouant on voit qu'on fait : *
H(1,D,A,I)
H(1,D,I,A)
H(1,A,I,D)
H(1,D,A,I) *On met la plus grand plaquette restante sur la tour d'arrivé*
H(2,I,A,D) *Depuis le tour du milieu on met tout sur la tour d'arrivé* *puis en jouant on voit qu'on fait : *
H(1,I,D,A)
H(1,I,A,D)
H(1,D,A,I)
On remarque une symétrie entre les deux appels récursifs en gras, c'est la même fonction mais pas les mêmes arguments ! Et la fonction du milieu H(1,D,A,I) se retrouve au début des deux autres.
Bref, on essayant tout et n'importe quoi j'ai trouvée la réponse (car elle apparaît ci dessus) : H(n,D,I,A) est
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
Mais je ne suis pas satisfait car en testant la réponse pour n = 3 je n'arrive pas à retrouver mon résultat empirique, je trouve des parcours incohérent qui montre que je dois me tromper quand je développe la fonction récursive.
Pouvez-vous m'aidez à la développer pour n = 3 afin que je conclue s'il vous plait.
Re: Tour de Hanoï.
Code : Tout sélectionner
def deplacer(nbrePalets=7,origine='A',destination='C',via='B') :
"""Deplace 'nbrePalets' palets de 'origine' à 'destination' en passant par 'via'. """
global tours, nbreCoups
if nbrePalets==1 :
# On déplace un palet de la tour 'origine' vers la tour 'destination'
piece=tours[origine].pop()
tours[destination].append(piece)
# Incrémentation du nombre de coup
nbreCoups+=1
# Affichage du message
print('Coup',str(nbreCoups).rjust(3),':',piece.ljust(6),'de',origine,'à',destination)
else :
# On déplace 'nbrePalets-1' palets de la tour 'origine'vers la tour 'via'
deplacer(nbrePalets-1,origine,via,destination)
# On déplace le dernier palet de la tour 'origine' vers la tour 'destination'
deplacer(1,origine,destination,via)
# On déplace 'nbrePalets-1' palets de la tour 'via' vers la tour 'destination'
deplacer(nbrePalets-1,via,destination,origine)
# Définition de la situation de départ
tours={'A':['Violet','Indigo','Bleu','Vert','Jaune','Orange','Rouge'],'B':[],'C':[]}
nbreCoups=0
deplacer()
J'enseigne la vie en PCSI/MPSI.
Re: Tour de Hanoï.
Salut tinkymento.
Plus précisément j'aimerais savoir si quelqu'un sait développer cette procédure :
H(n,D,I,A) est
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
pour n = 3.
Je sais que cette formule est juste, je l'ai trouvée pendant que je cherchait mais je ne l'est pas validée car je n'ai pas réussi à la développer pour n=3. Normalement elle devrait me donner :
H(1,D,A,I)
H(1,D,I,A)
H(1,A,I,D)
H(1,D,A,I)
H(1,I,D,A)
H(1,I,A,D)
H(1,D,A,I)
Mais je n'arrive pas à ça. Je pense qu'on j'ai du mal à suivre les appels récursifs pouvez vous m'aider ?
Plus précisément j'aimerais savoir si quelqu'un sait développer cette procédure :
H(n,D,I,A) est
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
pour n = 3.
Je sais que cette formule est juste, je l'ai trouvée pendant que je cherchait mais je ne l'est pas validée car je n'ai pas réussi à la développer pour n=3. Normalement elle devrait me donner :
H(1,D,A,I)
H(1,D,I,A)
H(1,A,I,D)
H(1,D,A,I)
H(1,I,D,A)
H(1,I,A,D)
H(1,D,A,I)
Mais je n'arrive pas à ça. Je pense qu'on j'ai du mal à suivre les appels récursifs pouvez vous m'aider ?
Re: Tour de Hanoï.
J'ai mis le code que j'utilise pour la tour de Hanoi, je pense que tu peux le déchiffrer en remplaçant deplacer() par H()Bidoof a écrit :Salut tinkymento.
Plus précisément j'aimerais savoir si quelqu'un sait développer cette procédure :
pour n = 3.
J'enseigne la vie en PCSI/MPSI.
Re: Tour de Hanoï.
Salut JeanN.
Si je dis que la procédure H(n,D,I,A) est
Si n différent de 0 alors :
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
Si n est 0 on ne fait rien.
Mon interprétation (erronée) de H(3,D,I,A) est :
*Lecture de la procédure*
H(2,D,I,A)
H(1,D,A,I)
H(2,I,A,D)
puis
*Première appel récursif*
H(1,D,I,A)
H(1,D,A,I)
H(1,IA,D)
*Lecture de la procédure*
H(1,D,A,I)
*Deuxième appel récursif*
H(1,D,A,I)
H(1,I,A,D)
H(1,I,D,A)
Mon idée est d'appliquer la fonction de départ plusieurs fois puis j'assemble tout. Comme pour faire x^n = x*x^(n-1) = x*...*x.
Si je dis que la procédure H(n,D,I,A) est
Si n différent de 0 alors :
H(n-1,D,I,A)
H(1,D,A,I)
H(n-1,I,A,D)
Si n est 0 on ne fait rien.
Mon interprétation (erronée) de H(3,D,I,A) est :
*Lecture de la procédure*
H(2,D,I,A)
H(1,D,A,I)
H(2,I,A,D)
puis
*Première appel récursif*
H(1,D,I,A)
H(1,D,A,I)
H(1,IA,D)
*Lecture de la procédure*
H(1,D,A,I)
*Deuxième appel récursif*
H(1,D,A,I)
H(1,I,A,D)
H(1,I,D,A)
Mon idée est d'appliquer la fonction de départ plusieurs fois puis j'assemble tout. Comme pour faire x^n = x*x^(n-1) = x*...*x.
Re: Tour de Hanoï.
Je suis toujours à l'écoute d'une solution si quelqu'un passe dans les parages.
Re: Tour de Hanoï.
C'est juste que tu t'emmêles les pinceaux entre les lettres D, A et I.
La procédure récursive : H(n-1, D, I, A), H(1, D, A, I), H(n-1, I, A, D) décrit H(n, D, A, I) alors que tu as écrit H(n, D, I, A).
Par exemple, H(3, D, A, I) se développe en :
H(2, D, I, A)
H(1, D, A, I)
H(2, I, A, D)
Ensuite, H(2, D, I, A) se développe en :
H(1, D, A, I)
H(1, D, I, A)
H(1, A, I, D)
et H(2, I, A, D) se développe en :
H(1, I, D, A)
H(1, I, A, D)
H(1, D, A, I)
On retrouve bien la solution itérative à trois disques.
La procédure récursive : H(n-1, D, I, A), H(1, D, A, I), H(n-1, I, A, D) décrit H(n, D, A, I) alors que tu as écrit H(n, D, I, A).
Par exemple, H(3, D, A, I) se développe en :
H(2, D, I, A)
H(1, D, A, I)
H(2, I, A, D)
Ensuite, H(2, D, I, A) se développe en :
H(1, D, A, I)
H(1, D, I, A)
H(1, A, I, D)
et H(2, I, A, D) se développe en :
H(1, I, D, A)
H(1, I, A, D)
H(1, D, A, I)
On retrouve bien la solution itérative à trois disques.
Re: Tour de Hanoï.
Pour compléter mon message, voici un code Python qui permet de suivre à la trace les appels récursifs de la fonction H :
La fonction trace est un décorateur ; elle permet d'appliquer du code (ici un affichage des arguments) avant chaque appel à la fonction tracée. Ce décorateur va nous permettre de voir avec quels arguments la fonction hanoi est appelée lors des différents appels récursifs.
Exemple :
Code : Tout sélectionner
def trace(func):
def wrapper(*args):
print(' ' * wrapper.space, end='')
print("--> appel de H({}, {}, {}, {})".format(*args))
wrapper.space += 1
func(*args)
wrapper.space -= 1
wrapper.space = 0
return wrapper
@trace
def hanoi(n, D, A, I):
if n > 1:
hanoi(n-1, D, I, A)
hanoi(1, D, A, I)
hanoi(n-1, I, A, D)
Exemple :
Code : Tout sélectionner
>>> hanoi(3, 'D', 'A', 'I')
--> appel de H(3, D, A, I)
--> appel de H(2, D, I, A)
--> appel de H(1, D, A, I)
--> appel de H(1, D, I, A)
--> appel de H(1, A, I, D)
--> appel de H(1, D, A, I)
--> appel de H(2, I, A, D)
--> appel de H(1, I, D, A)
--> appel de H(1, I, A, D)
--> appel de H(1, D, A, I)
Re: Tour de Hanoï.
Exactement ! Je vous remercie beaucoup, c'est exactement ce dont j'ai besoin pour avancer.left_shift a écrit :C'est juste que tu t'emmêles les pinceaux entre les lettres D, A et I.
[...]
On retrouve bien la solution itérative à trois disques.