Tours de Hanoi

Version imprimable

Voir 40 message(s) de cette discussion en une page

Tours de Hanoi

Bonjour

Je me suis acheté des tours de Hanoi en bois
Après trois jours de tatillonnage sur plus de vingt pages de brouillon j'ai enfin réussi à retrouver par moi même un morceau de l'algorithme général de récursion déplaçant les huit disques de la tour 1 à la tour 3, sans aide sur internet aucune.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 T0 = [ 0, 1, 2, 3, 4, 5, 6, 7 ] #Disques de diamêtres 0 à 7, empilés du plus petit sur le plus grand T1 = [ [],[],[],[], [],[],[],[] ] T2 = [ [],[],[],[], [],[],[],[] ] i=0 j=0 k=0 def move(i, j, k): if i == j : if k % 2 == 0: T0[i] = [] T2[i] = i else: T0[i] = [] T1[i] = i else: move(0, j-1, k-1) move(j, j, k) move(0, j-1, k-1) move(0, 7, 2) #Déplace et empile un par un les cylindres 0 à 7 sur la tour 2 # (jamais un plus grand sur un plus petit) # en t'aidant de la tour 1 print(T0) ; print(T1) ; print(T2)
Code:

1 2 3 [[], [], [], [], [], [], [], []] [0, [], 2, [], 4, [], 6, []] [[], 1, [], 3, [], 5, [], 7]
Le résultat imprimé par mon Notebook Jupiter semble indiquer que le travail est encore fait à moitié.
Manuellement je maîtrise maintenant parfaitement les 255 déplacements de disques, ce qui n'est pas encore le cas de mon ordinateur.
Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide :)

Merci !

:salut:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def tour_hanoi(n, i, j):
    """ Déplace n disques du piquet i au piquet j
        Nombre de disques n
        Trois piquets
        6 = 1 + 2 + 3 (somme des numéros des piquets)
        Nombre de déplacements = 2**n - 1
 
        https://www.codingame.com/playgrounds/17176/recueil-dexercices-pour-apprendre-python-au-lycee/tours-de-hanoi
        https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF
        https://deptinfo-ensip.univ-poitiers.fr/ENS/doku/doku.php/tp:python:prog01
    """
    if n > 0:
        tour_hanoi(n - 1, i, 6 - i - j)
        print("Déplacer disque du piquet {} au piquet {}".format(i, j))
        tour_hanoi(n - 1, 6 - i - j, j)
 
 
print('Nb déplacement = {}'.format(2**3 - 1)) # Nb déplacement = 7
 
tour_hanoi(3, 1, 3)
 
"""
Déplacer disque du piquet 1 au piquet 3
Déplacer disque du piquet 1 au piquet 2
Déplacer disque du piquet 3 au piquet 2
Déplacer disque du piquet 1 au piquet 3
Déplacer disque du piquet 2 au piquet 1
Déplacer disque du piquet 2 au piquet 3
Déplacer disque du piquet 1 au piquet 3
"""

23/05/2020, 12h03
wiztricks

Salut,

Citation:

Envoyé par Tudko

Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide :)

C'est peut être à ce moment là qu'il faut chercher un peu sur Internet pour voir comment l'ont codés d'autres (bien) avant vous...

- W

Bonjour

Citation:

Envoyé par Tudko

Je me suis acheté des tours de Hanoi en bois

C'est sympa. J'ai déjà vu ça aussi. Me semble que le truc est à 8 disques.

Citation:

Envoyé par Tudko

Après trois jours de tatillonnage sur plus de vingt pages de brouillon j'ai enfin réussi à retrouver par moi même un morceau de l'algorithme général de récursion déplaçant les huit disques de la tour 1 à la tour 3, sans aide sur internet aucune.

Bel effort. 20 pages ça me parait tout de même exagéré.

Citation:

Envoyé par Tudko

Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide :)

Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut
déplacer n-1 disques de la tour 1 à la tour 2
déplacer le dernier disque de la tour 1 à la tour 3
déplacer n-1 disques de la tour 2 à la tour 3

Un exemple se trouve dans mon tutoriel shell (cf signature). Et je viens de le porter en Python
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #!/usr/bin/env python3 # coding: utf-8 # Programme de tours de Hanoï # Usage: prog nb_pions # Fonction récursive qui déplace n pions d'une tour x vers une tour y def deplace(jeu, dep, arr, nb=1): # S'il n'y a plus qu'un seul pion if nb == 1: # Ici on est en fin de récursivité – Il ne reste plus qu'un seul pion à déplacer jeu["tours"][dep-1]-=1 # La tour de départ perd un pion jeu["tours"][arr-1]+=1 # La tour d'arrivée gagne un pion jeu["cpt"]+=1 # Le compteur de mouvements augmente # On génère le mouvement et on quitte la fonction yield "Mvt: %d - %d => %d: Etat: %s" % ( jeu["cpt"], dep, arr, ", ".join(map(str, jeu["tours"])), ) return # if # Ici, on est dans la partie intermédiaire du jeu – Il y a encore des pions qui gènent # Déplacement récursif des pions restants de la tour de départ vers une tour intermédiaire yield from deplace( jeu, dep, tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0], nb - 1, ) # Déplacement du dernier pion de la tour de départ vers la tour d'arrivée yield next(deplace(jeu, dep, arr)) # Déplacement récursif des pions restants de la tour intermédiaire vers la tour d'arrivée yield from deplace( jeu, tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0], arr, nb - 1, ) # deplace # Programme principal if __name__ == "__main__": import sys import os # Vérification arguments if len(sys.argv) <= 1 or int(sys.argv[1]) < 1: print("Usage: %s nb_pions positifs" % os.path.basename(__file__)) exit(1) # if # Initialisation jeu jeu={ "tours" : [int(sys.argv[1]), 0, 0], "cpt" : 0, } # Affichage position de départ print("Départ: %s" % ", ".join(map(str, jeu["tours"]))) # Lancement mouvement de la tour 1 vers la tour 3 print("\n".join(deplace(jeu, 1, 3, int(sys.argv[1])))) # Affichage position d'arrivée print("Arrivée: %s" % ", ".join(map(str, jeu["tours"]))) # if

23/05/2020, 15h42
Tudko

Merci beaucoup :)
C'est vrai que c'était intéressant de m'entraîner à chercher ma propre version

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 T0 = [ 0, 1, 2, 3, 4, 5, 6, 7 ] T1 = [ [],[],[],[], [],[],[],[] ] T2 = [ [],[],[],[], [],[],[],[] ] i=0 j=0 k=0 def move(i, j, k): if i == j : if k % 2 == 0: T0[i] = [] T2[i] = i else: T0[i] = [] T1[i] = i else: move(0, j-1, k) move(j, j, k) move(0, j-1, k) # et non pas k-1 move(0, 7, 2) print(T0) ; print(T1) ; print(T2)
[[], [], [], [], [], [], [], []]
[[], [], [], [], [], [], [], []]
[0, 1, 2, 3, 4, 5, 6, 7]
BINGO

Mais j'avoue que je n'ai pas saisi mathématiquement pourquoi k [le compteur : déplacer de 1 ou de 2 tours ; déplacer de 3(impair)tours revenant à revenir à la tour 1 et ainsi de suite] au lieu de k-1. En effet, si vous vous êtes renseignés sur le jeu, partir de n=8 disques pour arriver à la tour 2 (k=+2) demande de d'abord faire k-1 =+1 aux n-1=7 premiers tours, afin de laisser au préalable place au disque 8 sur la tour 2 (ici la première tour est la tour 0). Et ainsi de suite. Enfin d'après moi

24/05/2020, 09h27
Sve@r
Citation:
Envoyé par Tudko

Code:

1 2 3 T0 = [ 0, 1, 2, 3, 4, 5, 6, 7 ] T1 = [ [],[],[],[], [],[],[],[] ] T2 = [ [],[],[],[], [],[],[],[] ]
Pourquoi la tour 0 contient des disques (des valeurs) et les autres tours contiennent des listes ???
Citation:
Envoyé par Tudko

[[], [], [], [], [], [], [], []] [[], [], [], [], [], [], [], []] [0, 1, 2, 3, 4, 5, 6, 7]
BINGO
Oui enfin on voit jiste l'état final. Ce qui est bien, c'est de voir chaque mouvement.
Citation:
Envoyé par Tudko

Citation:

Envoyé par Sve@r

Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut
déplacer n-1 disques de la tour 1 à la tour 2
déplacer le dernier disque de la tour 1 à la tour 3
déplacer n-1 disques de la tour 2 à la tour 3

En effet, si vous vous êtes renseignés sur le jeu, partir de n=8 disques pour arriver à la tour 2 (k=+2) demande de d'abord faire k-1 =+1 aux n-1=7 premiers tours, afin de laisser au préalable place au disque 8 sur la tour 2 (ici la première tour est la tour 0). Et ainsi de suite. Enfin d'après moi
Oui, c'est aussi ce que j'avais écrit.

Citation:

Envoyé par Sve@r

Pourquoi la tour 0 contient des disques (des valeurs) et les autres tours contiennent des listes ???

Oui enfin on voit jiste l'état final. Ce qui est bien, c'est de voir chaque mouvement.

Oui, c'est aussi ce que j'avais écrit.

La tour 0 contient la valeur 1 pour disque 1, je pense que ça reste manipulable
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 T0 =[0, 1, 2, 3, 4, 5, 6, 7] T1 =[[],[],[],[], [],[],[],[] ] T2 =[[],[],[],[], [],[],[],[] ] i=0 j=0 k=0 def move(i, j, k): if i == j : if k % 2 == 0: T0[i] = [] T2[i] = i else: T0[i] = [] T1[i] = i else: move(0, j-1, k) move(j, j, k) move(0, j-1, k) print(T0) ; print(T1) ; print(T2) move(0, 7, 2) [[], [], 2, 3, 4, 5, 6, 7] [[], [], [], [], [], [], [], []] [0, 1, [], [], [], [], [], []] [[], [], [], 3, 4, 5, 6, 7] [[], [], [], [], [], [], [], []] [0, 1, 2, [], [], [], [], []] [[], [], [], 3, 4, 5, 6, 7] [[], [], [], [], [], [], [], []] [0, 1, 2, [], [], [], [], []] [[], [], [], [], 4, 5, 6, 7] [[], [], [], [], [], [], [], []] [0, 1, 2, 3, [], [], [], []] [[], [], [], [], 4, 5, 6, 7] [[], [], [], [], [], [], [], []] [0, 1, 2, 3, [], [], [], []] [[], [], [], [], 4, 5, 6, 7] [[], [], [], [], [], [], [], []] …
C'est un peu mieux toujours pas cohérent mathématiquement, franchement les machines..
Est-ce que Python n'est pas le meilleur langage pour faire ça? Il faudrait un langage proprement fonctionnel comme Scheme/Haskell??

Citation:
Envoyé par Sve@r
Bonjour

C'est sympa. J'ai déjà vu ça aussi. Me semble que le truc est à 8 disques.

Bel effort. 20 pages ça me parait tout de même exagéré.

Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut
déplacer n-1 disques de la tour 1 à la tour 2
déplacer le dernier disque de la tour 1 à la tour 3
déplacer n-1 disques de la tour 2 à la tour 3

Un exemple se trouve dans mon tutoriel shell (cf signature). Et je viens de le porter en Python
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #!/usr/bin/env python3 # coding: utf-8 # Programme de tours de Hanoï # Usage: prog nb_pions # Fonction récursive qui déplace n pions d'une tour x vers une tour y def deplace(jeu, dep, arr, nb=1): # S'il n'y a plus qu'un seul pion if nb == 1: # Ici on est en fin de récursivité – Il ne reste plus qu'un seul pion à déplacer jeu["tours"][dep-1]-=1 # La tour de départ perd un pion jeu["tours"][arr-1]+=1 # La tour d'arrivée gagne un pion jeu["cpt"]+=1 # Le compteur de mouvements augmente # On génère le mouvement et on quitte la fonction yield "Mvt: %d - %d => %d: Etat: %s" % ( jeu["cpt"], dep, arr, ", ".join(map(str, jeu["tours"])), ) return # if # Ici, on est dans la partie intermédiaire du jeu – Il y a encore des pions qui gènent # Déplacement récursif des pions restants de la tour de départ vers une tour intermédiaire yield from deplace( jeu, dep, tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0], nb - 1, ) # Déplacement du dernier pion de la tour de départ vers la tour d'arrivée yield next(deplace(jeu, dep, arr)) # Déplacement récursif des pions restants de la tour intermédiaire vers la tour d'arrivée yield from deplace( jeu, tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0], arr, nb - 1, ) # deplace # Programme principal if __name__ == "__main__": import sys import os # Vérification arguments if len(sys.argv) <= 1 or int(sys.argv[1]) < 1: print("Usage: %s nb_pions positifs" % os.path.basename(__file__)) exit(1) # if # Initialisation jeu jeu={ "tours" : [int(sys.argv[1]), 0, 0], "cpt" : 0, } # Affichage position de départ print("Départ: %s" % ", ".join(map(str, jeu["tours"]))) # Lancement mouvement de la tour 1 vers la tour 3 print("\n".join(deplace(jeu, 1, 3, int(sys.argv[1])))) # Affichage position d'arrivée print("Arrivée: %s" % ", ".join(map(str, jeu["tours"]))) # if
ValueError Traceback (most recent call last)
<ipython-input-8-d605c888f81a> in <module>()
50
51 # Vérification arguments
---> 52 if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
53 print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
54 exit(1)

ValueError: invalid literal for int() with base 10: '-f'

24/05/2020, 18h00
Sve@r

Citation:

Envoyé par Tudko

La tour 0 contient la valeur 1 pour disque 1, je pense que ça reste manipulable

Je parlais pas de la tour 0 qui contient les disques (ça j'ai compris), je parlais des autres tours qui contiennent des listes vides ce que je ne comprends pas. Ma question concernait donc ces autres tours, et la partie de ma question qui parle de la tour 0 était juste là pour illustrer le fait que vu qu'elle contient des nombres (les largeurs des disques probablement), c'était pas normal d'avoir les autres tours contenant des listes.

Citation:

Envoyé par Tudko

Est-ce que Python n'est pas le meilleur langage pour faire ça? Il faudrait un langage proprement fonctionnel comme Scheme/Haskell??

Personne ne t'a obligé à utiliser Python. C'est toi qui est venu ici poser la question. Ce forum n'est pas le lieu pour débattre de quel langage est meilleur que lequel (ce qui d'ailleurs est un faux débat => "Aucun langage de programmation n'est parfait. Il n'existe même pas un langage meilleur que d'autre ; il n'y a que des langages en adéquation ou peu conseillés pour des buts particuliers. (Herbert Mayer)").

Citation:

Envoyé par Tudko

ValueError Traceback (most recent call last)
<ipython-input-8-d605c888f81a> in <module>()
50
51 # Vérification arguments
---> 52 if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
53 print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
54 exit(1)

ValueError: invalid literal for int() with base 10: '-f'

Il semble que tu utilises ipython (et probablement basé sur Python2). Mon script est écrit en Python3.
Te faut remplacer les deux yield from deplace(...) (lignes 27 et 39) par for x in deplace(...): yield x (le yield from iterable n'existe pas en P2).

Et j'espère que ce "-f" que je vois c'est pas toi qui l'a invoqué comme option quand tu appelles ce programme.

Salut je reviens vers vous

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
T= [[0, 1, 2, 3, 4, 5, 6, 7],[],[]]
i = 0
j=0
compteur=0
def move(i, j):
  global compteur
  if j == i:
    j=i
    if compteur %2 == 0:
        del T[compteur][j]
        compteur= compteur +2
        T[compteur].append(j)
 
    else:
        del T[compteur][j]
        compteur= compteur +1
        T[compteur].append(j)
 
  else:
    move(i, j-1)
    move(j, j)
    move(i, j-1)
    print(T); print()#sauter une ligne entre deux étapes affichées
    compteur=compteur%3
move(0, 7)
 
IndexError                                Traceback (most recent call last)
<ipython-input-29-4b0d0af17ac1> in <module>()
     23     print(T); print()#sauter une ligne entre deux étapes affichées
     24     compteur=compteur%3
---> 25 move(0, 7)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     19   else:
     20     move(i, j-1)
---> 21     move(j, j)
     22     move(i, j-1)
     23     print(T); print()#sauter une ligne entre deux étapes affichées
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
      8     j=i
      9     if compteur %2 == 0:
---> 10         del T[compteur][j]
     11         compteur= compteur +2
     12         T[compteur].append(j)
 
IndexError: list assignment index out of range (?)

J'ai essayé de faire afficher chaque étape du jeu pour avoir et le résultat attendu et le bon raisonnement, ce qui fut un échec précédemment et l'est toujours

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
T0 =[0, 1,  2,  3,  4,  5,  6,  7]
T1 =[[],[],[],[],  [],[],[],[] ]
T2 =[[],[],[],[],  [],[],[],[] ]
i=0
j=0
k=0
def move(i, j, k):
  if i == j :
    if k % 2 == 0:
      T0[i] = []
      T2[i] = i
    else:
      T0[i] = []
      T1[i] = i
  else:
    move(0, j-1, k)
    move(j, j, k)
    move(0, j-1, k)
    print(T0) ; print(T1) ; print(T2)
move(0, 7, 2)
 
[[], [], 2, 3, 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, [], [], [], [], [], []
…

D'ailleurs pourquoi précédemment l'algo déplace DEUX disques par étape?

04/06/2020, 17h59
Sve@r
Citation:

Envoyé par Tudko

D'ailleurs pourquoi précédemment l'algo déplace DEUX disques par étape?

Je n'en sais absolument rien. Peut-être parce que ton algo n'a pas de commentaire et que j'y pige que dalle (déjà toi est-ce que tu t'en sors ???). Pourquoi par exemple tester si "i" est pair ???. Peut-être parce que les lignes 10 et 13 sont les mêmes bien que l'une soit dans le "if" et l'autre dans le "else" (si j'ai ceci alors faire cela, sinon faire cela !!! :roll:). Ou alors peut-être parce que les lignes 16 et 18 sont là aussi les mêmes (sans compter la ligne 17 où je ne sais pas trop si "j" représente le nb de pions ou les tours de départ et d'arrivée mais où, dans tous les cas, ne peut pas être utilisé 2 fois :roll: :roll: :roll:..)

Bref pour résumer, parce que ton code bien qu'il "ressemble" à un algo de Hanoi, ne reproduit absolument pas l'algo de base qui est (déjà dit)
Déplacer n disques de la tour 1 à la tour , c'est
- déplacer n-1 disques de la tour 1 à la tour 2
- déplacer le dernier disque de la tour 1 à la tour 3
- déplacer n-1 disques de la tour 2 à la tour 3

Bonjour,

Problème ancien et toujours très intéressant. Comme le PO a l'air en panne, je donne un petit coup de pouce.

Je part de l'algorithme cité par Sve@r:

Code:

1
2
3
4
Déplacer n disques de la tour 1 à la tour , c'est
    déplacer n-1 disques de la tour 1 à la tour 2
    déplacer le dernier disque de la tour 1 à la tour 3
    déplacer n-1 disques de la tour 2 à la tour 3

Une version mini en Python pourrait être:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def hanoi(nbdisques, orig=[], dest=[], inter=[]):
 
    if nbdisques>0:
 
        # 1er appel récursif
        hanoi(nbdisques-1, orig, inter, dest)
 
        # déplacement
        dest.append(orig.pop())
 
        # affichage
        print(orig, inter, dest)
 
        # 2ème appel récursif
        hanoi(nbdisques-1, inter, dest, orig)
 
n = 3
orig = [i for i in range(n, 0, -1)]
print(orig, [], [])
hanoi(n, orig)

Ce qui donne pour n=3:

Code:

1
2
3
4
5
6
7
8
[3, 2, 1] [] []
[3, 2] [] [1]
[3] [1] [2]
[] [3] [2, 1]
[] [2, 1] [3]
[2] [3] [1]
[] [1] [3, 2]
[] [] [3, 2, 1]

On voit que ça marche, mais l'affichage a un problème: l'ordre des tours n'est pas toujours la même puisqu'il dépend de l'ordre des arguments de chaque appel. Si on veut bien comprendre, il faut afficher les tours dans le bon ordre: "origine", "intermédiaire" et "destination". On va donc changer la structure de données comme ça:
orig = [1, [i for i in range(nbdisques, 0, -1)]]
inter = [2, []]
dest = [3, []]
ce qui permettra de retrouver lors de l'affichage les 3 tours dans l'ordre: 1=>origine, 2=>intermédiaire et 3=> destination.

Voilà un code plus complet:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#############################################################################
def _hanoi(nbdisques, orig, dest, inter):
    global nbcoups
 
    if nbdisques>0:
 
        # 1er appel récursif
        _hanoi(nbdisques-1, orig, inter, dest)
 
        # procède au déplacement
        dest[1].append(orig[1].pop())
 
        # affichage du déplacement
        nbcoups += 1
        tours = {1:"origine", 2:"intermédiaire", 3:"destination"}
        print("coup", nbcoups, " - déplace disque de ", tours[orig[0]], " à ", tours[dest[0]])
        tours = sorted([orig] + [inter] + [dest], key=lambda v: v[0])
        print(tours[0][1], tours[1][1], tours[2][1])
        print()
 
        # 2ème appel récursif
        _hanoi(nbdisques-1, inter, dest, orig)
 
#============================================================================
def hanoi(nbdisques):
 
    # crée les tours avec les disques demandés sur la tour d'origine
    orig = [1, [i for i in range(nbdisques, 0, -1)]]
    dest = [3, []]
    inter = [2, []]
    nbcoups = 0
 
    # affiche la situation de départ pour les 3 tours
    print("Etat des 3 tours au départ, avec", nbdisques, "disques sur la tour origine:")
    print("origine:", orig[1], "intermédiaire:", inter[1], "destination:", dest[1])
    print()
 
    _hanoi(nbdisques, orig, dest, inter)
 
############################################################################# 
if __name__ == "__main__":
 
    # pour compter le nombre de déplacements nécessaires (var globale)
    nbcoups = 0
 
    n = 3 # nombre de disques à déplacer
    hanoi(n)

Ce qui donne cette fois pour 3 disques à déplacer de la tour "orig" à la tour "dest":

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Etat des 3 tours au départ, avec 3 disques sur la tour origine:
origine: [3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  destination
[3, 2] [] [1]
 
coup 2  - déplace disque de  origine  à  intermédiaire
[3] [2] [1]
 
coup 3  - déplace disque de  destination  à  intermédiaire
[3] [2, 1] []
 
coup 4  - déplace disque de  origine  à  destination
[] [2, 1] [3]
 
coup 5  - déplace disque de  intermédiaire  à  origine
[1] [2] [3]
 
coup 6  - déplace disque de  intermédiaire  à  destination
[1] [] [3, 2]
 
coup 7  - déplace disque de  origine  à  destination
[] [] [3, 2, 1]

Et là, on voit bien tous les mouvements effectués par l'algorithme. Ici, pour n=3 disques, on fait ça en 2**n-1=7 coups.

On peut, bien sûr, utiliser pour n'importe quelle valeur de n, à condition d'être raisonnable à cause des limites de la pile de récursion.

Par exemple, pour n=20 qui demande 2**20-1=1048575 déplacements:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Etat des 3 tours au départ, avec 20 disques sur la tour origine:
origine: [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  intermédiaire
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2] [1] []
 
coup 2  - déplace disque de  origine  à  destination
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3] [1] [2]
 
coup 3  - déplace disque de  intermédiaire  à  destination
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3] [] [2, 1]
 
coup 4  - déplace disque de  origine  à  intermédiaire
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4] [3] [2, 1]
 
coup 5  - déplace disque de  destination  à  origine
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 1] [3] [2]
 
...
 
coup 1048571  - déplace disque de  destination  à  origine
[2, 1] [3] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
 
coup 1048572  - déplace disque de  intermédiaire  à  destination
[2, 1] [] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
 
coup 1048573  - déplace disque de  origine  à  intermédiaire
[2] [1] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
 
coup 1048574  - déplace disque de  origine  à  destination
[] [1] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
 
coup 1048575  - déplace disque de  intermédiaire  à  destination
[] [] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

07/06/2020, 14h11
Sve@r
Citation:

Envoyé par tyrtamos

Problème ancien et toujours très intéressant.

Une légende dit que Dieu a créé 3 aiguilles et 64 disques d'or et chargé ses prêtres de déplacer les 64 disques de l'aiguille 1 à l'aiguille 3. Et quand tout sera fini, ce sera la fin du monde.

Citation:

Envoyé par tyrtamos

Comme le PO a l'air en panne

Ben en fait je pense qu'il a décroché...

Citation:

Envoyé par tyrtamos

à condition d'être raisonnable à cause des limites de la pile de récursion.

Il existe aussi une solution itérative : commencer par établir le premier coup (tour nb impair => commencer par tour d'arrivée, tour nb pair commencer par la tour intermédiaire). Ensuite toujours choisir le disque qui n'a pas bougé au coup précédent (sinon ça veut dire que le même disque bouge 2 fois) et si 2 possibilités pour l'autre disque, alors toujours choisir la tour qui n'est pas celle d'où il est venu (sinon ça signifie qu'on annule son déplacement précédent)

Prenons cet algo avec 3 tours A, B et C sur 3 disques à amener de A vers C. Position de départ: 3 0 0
- Au premier coup, il y a possibilité de partir de A vers B ou C. Toutefois A a 3 disques (nb impair). Le premier disque va donc de A vers C. Ce qui donne 2 0 1
- Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer A. Qui là ne peut aller que sur B => 1 1 1
- Ensuite on peut soit déplacer B (mais il vient d'arriver donc interdit), soit déplacer C qui pourrait aller sur A (mais il vient de A ce qui annulerait alors son coup précédent) donc il va sur B => 1 2 0
- Ensuite on peut soit déplacer B (mais il vient d'arriver donc interdit) soit déplacer A qui ne peut aller que sur C => 0 2 1
- Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer B qui pourrait aller sur C (mais il vient de C) donc il va sur A => 1 1 1
- Ensuite on peut soit déplacer A (mais il vient d'arriver donc interdit) soit déplacer B qui ne peut aller que sur C => 1 0 2
- Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer A qui pourrait aller sur B (mais il vient de B) donc il va sur C => 0 0 3
Ps: j'ai lancé mon code récursif avec 50 avant de commencer à taper ce post. Et j'ai fini de taper que mon truc est toujours en train de calculer ses mouvements (et je crois même que la machine virtuelle sur laquelle il tourne est freezée.. :?)
07/06/2020, 15h05
wiztricks

Salut,

Vieux problème, beaucoup de littérature et des résumés dans Wikipedia.
Pour ce que çà intéresse, l'article anglais fait le tour du sujet et des différentes solutions (car il y en a d'autres que la récursive et l'itérative).

- W

Citation:

Envoyé par wiztricks

Pour ce que çà intéresse, l'article anglais fait le tour du sujet et des différentes solutions

Effectivement, j'en ai trouvé une encore plus simple que celle que j'ai exposée : si on code un mouvement de 1 vers 2 ou de 2 vers 1 par la somme des tours, on obtient 3. Il y a donc 3 valeurs de mouvements possibles (3 pour tour 1 et tour 2, 4 pour tour 1 et tour 3 et 5 pour tour 2 et tour 3).
Et là, on se rend compte que pour un nombre pair de pions, la suite des mouvements est 3, 4, 5, 3, 4, 5, etc (jusqu'à ce que tous les pions aient été déplacés). Et pour un nombre impair, alors la suite est 4, 3, 5, 4, 3, 5, etc. On n'a même pas à se poser de questions. On déroule simplement 3, 4, 5, 3, 4, 5, ... (ou 4, 3, 5, 4, 3, 5, ...) à l'infini. A chaque mouvement (ex 5 qui met en jeu la tour 2 et la tour 3), le sens du mouvement (2 vers 3 ou 3 vers 2) se définit facilement par la seule possibilité (le petit anneau sur le grand).

D'où le code (qui, adapté à l'informatique, utilise le codage 1, 2 et 3 pour les mouvements entre les tours 0, 1 et 2)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #!/usr/bin/env python3 # coding: utf-8 # Programme de tours de Hanoï # Usage: prog nb_pions # Fonction itérative qui déplace nb pions de la tour 0 à la tour 2 def deplace(jeu, nb): # Décomposition du coup joué def decomp(coup): # Calcul des tours affectées (x, y)={ 1 : (0, 1), 2 : (0, 2), 3 : (1, 2), }[coup] # Dans le tuple renvoyé on met déjà le coup évalué (ça ne mange pas de pain) r=(coup,) # Si l'une des deux tours x/y est vide, elle reçoit alors le pion de l'autre if not jeu["tours"][y]: return r + (x, y) if not jeu["tours"][x]: return r + (y, x) # Le sens du coup dépendra du petit pion qui va sur le grand return r + ((x, y) if jeu["tours"][x][-1] < jeu["tours"][y][-1] else (y, x)) # decomp() # Tant que la dernière tour n'a pas tous les pions while len(jeu["tours"][2]) < nb: # Décomposition du coup courant par rapport au chemin des coups move=decomp(jeu["path"][jeu["cpt"] % 3]) # Positionnement des pions : tour d'arrivée récupère dernier pion tour de départ jeu["tours"][move[2]].append( jeu["tours"][move[1]].pop(), ) jeu["cpt"]+=1 # Le compteur de mouvements augmente yield "Mvt %d: %d => %d: Etat: %s" % ( jeu["cpt"], move[1] + 1, move[2] + 1, affich(jeu), ) # while # deplace() # Affichage jeu def affich(jeu, full=False): return "%s%s" % ( ", ".join(map(str, (len(t) for t in jeu["tours"]))), " => %s" % " ".join(str(list(reversed(x))) for x in jeu["tours"]) if full else "", ) # affich() # Programme principal if __name__ == "__main__": import sys import os # Vérification arguments if len(sys.argv) <= 1 or int(sys.argv[1]) < 1: print("Usage: %s nb_pions positifs" % os.path.basename(__file__)) exit(1) # if # Initialisation jeu nb=int(sys.argv[1]) jeu={ "tours" : tuple([] if i else list(range(nb, 0, -1)) for i in range(3)), "cpt" : 0, "path" : ((2, 1) if nb % 2 else (1, 2)) + (3,), } # Affichage position de départ print("Départ: %s" % affich(jeu, True)) # Lancement mouvement for x in deplace(jeu, nb): print(x) # Affichage position d'arrivée print("Arrivée: %s" % affich(jeu, True)) # if
Je l'ai lancé pour 64 (en référence à la légende de la fin du monde) et le petit truc s'est vaillamment lancé dans le mouvement des pions. Et là, pas de souci de récursivité limitée... 8-)

Bonjour,

A noter que l'article de wikipedia cité par wiztricks existe aussi en français: https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

Un grand merci à Sve@r pour la solution itérative (la 2ème de l'article ci-dessus): j'aime beaucoup!

Voilà mon code pour cette solution itérative:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#############################################################################
def deplace(nomA, A, nomB, B):
    """déplace un disque d'une des 2 tours vers l'autre tour
       sur un disque plus grand ou sur une tour vide
    """
    if len(A)>0 and (len(B)==0 or A[-1]<B[-1]):
        print("Déplace {} => {}".format(nomA, nomB))
        B.append(A.pop())
    else:
        print("Déplace {} => {}".format(nomB, nomA))
        A.append(B.pop())
 
#############################################################################
def _hanoi(nbdisques, tour1, tour2, tour3):
    global nbcoups
 
    if nbdisques%2==0:
        # solution nbdisques pair
        while len(tour1)+len(tour2)!=0:
            #----------------------------------------------------------------
            # somme=3: déplacement 1=>2 ou 2=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour2", tour2)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=4: déplacement 1=>3 ou 3=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=5: déplacement 2=>3 ou 3=>2
            nbcoups += 1
            deplace("tour2", tour2, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
    else:
        # solution nbdisques impair
        while len(tour1)+len(tour2)!=1:
            #----------------------------------------------------------------
            # somme=4: déplacement 1=>3 ou 3=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=3: déplacement 1=>2 ou 2=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour2", tour2)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=5: déplacement 2=>3 ou 3=>2
            nbcoups += 1
            deplace("tour2", tour2, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
        #--------------------------------------------------------------------
        # dernier déplacement pour somme impaire
        nbcoups += 1
        print("Déplace tour1 => tour3")
        tour3.append(tour1.pop())
        print(nbcoups, tour1, tour2, tour3, '\n')
 
#============================================================================
def hanoi(nbdisques):
 
    # crée les tours avec les disques demandés sur la tour d'origine
    tour1 = [i for i in range(nbdisques, 0, -1)]
    tour3 = []
    tour2 = []
 
    # affiche la situation de départ pour les 3 tours
    print("Etat des 3 tours au départ, avec", nbdisques, "disques sur la tour origine:")
    print("origine:", tour1, "intermédiaire:", tour2, "destination:", tour3)
    print()
 
    _hanoi(nbdisques, tour1, tour3, tour2)
 
############################################################################# 
if __name__ == "__main__":
    nbcoups = 0 # variable globale
    n = 11 # nombre de disques à déplacer
    hanoi(n)

Ce qui donne par exemple pour n=3:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Etat des 3 tours au départ, avec 3 disques sur la tour 1:
tour 1: [3, 2, 1] tour 2: [] tour 3: []
 
Déplace tour1 => tour3
1 [3, 2] [] [1] 
 
Déplace tour1 => tour2
2 [3] [2] [1] 
 
Déplace tour3 => tour2
3 [3] [2, 1] [] 
 
Déplace tour1 => tour3
4 [] [2, 1] [3] 
 
Déplace tour2 => tour1
5 [1] [2] [3] 
 
Déplace tour2 => tour3
6 [1] [] [3, 2] 
 
Déplace tour1 => tour3
7 [] [] [3, 2, 1]

Et pour n=4:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Etat des 3 tours au départ, avec 4 disques sur la tour 1:
tour 1: [4, 3, 2, 1] tour 2: [] tour 3: []
 
Déplace tour1 => tour2
1 [4, 3, 2] [1] [] 
 
Déplace tour1 => tour3
2 [4, 3] [1] [2] 
 
Déplace tour2 => tour3
3 [4, 3] [] [2, 1] 
 
Déplace tour1 => tour2
4 [4] [3] [2, 1] 
 
Déplace tour3 => tour1
5 [4, 1] [3] [2] 
 
Déplace tour3 => tour2
6 [4, 1] [3, 2] [] 
 
Déplace tour1 => tour2
7 [4] [3, 2, 1] [] 
 
Déplace tour1 => tour3
8 [] [3, 2, 1] [4] 
 
Déplace tour2 => tour3
9 [] [3, 2] [4, 1] 
 
Déplace tour2 => tour1
10 [2] [3] [4, 1] 
 
Déplace tour3 => tour1
11 [2, 1] [3] [4] 
 
Déplace tour2 => tour3
12 [2, 1] [] [4, 3] 
 
Déplace tour1 => tour2
13 [2] [1] [4, 3] 
 
Déplace tour1 => tour3
14 [] [1] [4, 3, 2] 
 
Déplace tour2 => tour3
15 [] [] [4, 3, 2, 1]

On retrouve le même nombre de déplacement à faire: 2**n-1

09/06/2020, 11h01
danielhagnoul

:salut:

Je ne comprends pas ce que vous reprochez à la solution du message n° 2, qui n'est pas de moi et qui hors les commentaires tient en 3 lignes !
09/06/2020, 11h03
wiztricks

Se faire une idée de l'état de l'art est toujours source d'inspiration.

Citation:

Envoyé par tyrtamos

A noter que l'article de wikipedia cité par wiztricks existe aussi en français: https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

Je n'ai pas mentionné cet article car il est bien moins riche dans ses ouvertures.
Et quitte à revisiter les tours de Hanoï une n^ième fois, autant apprendre quelque chose de nouveau.

- W

Voir 40 message(s) de cette discussion en une page