Tour de Hanoï.

[Bidoof]

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.

[tinkymento]

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()

[Bidoof]

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 ?

[JeanN]

tu arrives à quoi ?

[tinkymento]

Salut tinkymento.

Plus précisément j'aimerais savoir si quelqu'un sait développer cette procédure :
pour n = 3.

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]

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.

[Bidoof]

Je suis toujours à l'écoute d'une solution si quelqu'un passe dans les parages.

[left_shift]

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.

[left_shift]

Pour compléter mon message, voici un code Python qui permet de suivre à la trace les appels récursifs de la fonction H :

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)

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

>>> 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)

[Bidoof]

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.

Exactement ! Je vous remercie beaucoup, c'est exactement ce dont j'ai besoin pour avancer.