Partage
  • Partager sur Facebook
  • Partager sur Twitter

Tours de Hanoi

    23 mai 2020 à 4:33:37

    Bonjour
    Je me suis acheté des tours de Hanoi
    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 tout 3, sans aide sur internet aucune.

    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)
    [[], [], [], [], [], [], [], []]
    [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 !
    • Partager sur Facebook
    • Partager sur Twitter
      Staff 23 mai 2020 à 7:17:38

      Bonjour,

      Le message qui suit est une réponse automatique activée par un membre de l'équipe. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose, ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention.
      Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé.

      Pour plus d'informations, nous vous invitons à lire les règles générales du forum

      Merci de colorer votre code à l'aide du bouton Code

      Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton Code de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: python;">Votre code ici</pre>.

      Merci de modifier votre message d'origine en fonction.

      Liens conseillés

      • Partager sur Facebook
      • Partager sur Twitter
        23 mai 2020 à 8:31:33

        J'ai trouvé un algorithme récursif sur Wikipedia en pseudo-code.
        J'en ai programmé l'affichage en Python. Voici ce que ça donne:
        -
        # D = départ, A = arrivée, I = intermédiaire.
        def Hanoii(n, D, A, I):
            if n > 0:
                Hanoii(n-1, D, I, A)
                print("Déplacer un disque de {}  vers {}".format(D, A))
                Hanoii(n-1, I, A, D)
        # Déplacer 5 disques de 1 vers 3 en passant par 2.
        Hanoii(5, 1, 3, 2)
        -
        Pour le faire "en vrai", chaque tour D, A, I serait une liste.
        On place les nombres de 8 à 1 dans la liste D. Les listes A et I sont vides.
        nombre = 8
        D = [ nombre - i for i in range(nombre) ]
        On remplace le print par un pop de la liste de départ et un append sur la liste d'arrivée.
                A.append(D.pop())   ?
        Tes éléments t1 et t2 sont des listes de listes. Tu n'as pas besoin de ça.

        -
        Edité par PierrotLeFou 23 mai 2020 à 8:50:04

        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          23 mai 2020 à 15:19:33

          Tu pourras des explications détaillées sur l'algo récursif ainsi que le codage d'une animation sous Tkinter ICI.
          • Partager sur Facebook
          • Partager sur Twitter
            23 mai 2020 à 21:58:06 - Message modéré pour le motif suivant : Merci d'utiliser le bouton code du forum pour insérer votre code


              24 mai 2020 à 1:26:58

              @Rambert111:
              Je t'encourage à colorer ton code, même si moi-même je ne le fais pas.
              Le modérateur AbcAbc6 sait pourquoi (voir mon profile).
              Voici la solution telle que je l'ai proposée. Tu pourras constater que les disques ont bien été transférés de la liste D vers la liste A.
              Note que les disques les plus grands sont au début dans mon cas.
              -
              # D = départ, A = arrivée, I = intermédiaire.
              def Hanoii(n, D, A, I):
                  if n > 0:
                      Hanoii(n-1, D, I, A)
                      A.append(D.pop())
                      # print("Déplacer un disque de {}  vers {}".format(D, A))
                      Hanoii(n-1, I, A, D)
              # Déplacer 5 disques de la tour D vers la tour A en passant par la tour I
              nb=5
              D = [nb-i for i in range(nb)]
              A =[]
              I = []
              # Tu pourras afficher les listes avant si tu veux.
              Hanoii(nb, D, A, I)
              print("D=",D)
              print("I=",I)
              print("A=",A)
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                24 mai 2020 à 23:21: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
                
                
                

                -
                Edité par Rambert111 24 mai 2020 à 23:22:56

                • Partager sur Facebook
                • Partager sur Twitter
                  25 mai 2020 à 1:03:55

                  @Rambert111:
                  De toute évidence ton code fonctionne.
                  Petite question: programmes-tu en C ou C++?
                  Je code en C mais j'essaie de coder en Python d'une autre façon.
                  Si tu t'es donné la peine de le faire sur papier et de trouver une méthode récursive par toi-même, Bravo!
                  Tu es peut-être un débutant en Python. Les experts sont fainéants et codent le plus simple possible. :)
                  • Partager sur Facebook
                  • Partager sur Twitter

                  Le Tout est souvent plus grand que la somme de ses parties.

                    25 mai 2020 à 14:27:00

                    Rambert111 a écrit:

                    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
                    
                    
                    

                    -
                    Edité par Rambert111 il y a environ 14 heures


                    C'est pas très clair. Quel est ton but, à quoi servent les Ti ?
                    • Partager sur Facebook
                    • Partager sur Twitter
                      25 mai 2020 à 17:49:26

                      PascalOrtiz a écrit:
                      > C'est pas très clair. Quel est ton but, à quoi servent les Ti ?
                      Je pense que c'est très clair, Rambert111 veut faire un jeu des tours de Hanoï de façon récursive.
                      J'ai testé son dernier code, et il fonctionne effectivement.
                      Maintenant, est-ce qu'il le fait de façon vraiment récursive, c'est à voir.
                      Et il n'utilise pas les listes de la bonne façon. Les lisrtes de listes, c'est vraiment trop compliqué pour rien.
                      Même si mon code est douteux, il est beaucoup plus simple et vraiment récursif. Il fonctionne également.
                      Est-ce qu'on peut faire mieux? C'est à toi de le dire.
                      • Partager sur Facebook
                      • Partager sur Twitter

                      Le Tout est souvent plus grand que la somme de ses parties.

                        25 mai 2020 à 17:58:03

                        PierrotLeFou a écrit:

                        PascalOrtiz a écrit:
                        > C'est pas très clair. Quel est ton but, à quoi servent les Ti ?
                        Je pense que c'est très clair, Rambert111 veut faire un jeu des tours de Hanoï de façon récursive.
                        J'ai testé son dernier code, et il fonctionne effectivement.
                        Maintenant, est-ce qu'il le fait de façon vraiment récursive, c'est à voir.
                        Et il n'utilise pas les listes de la bonne façon. Les lisrtes de listes, c'est vraiment trop compliqué pour rien.
                        Même si mon code est douteux, il est beaucoup plus simple et vraiment récursif. Il fonctionne également.
                        Est-ce qu'on peut faire mieux? C'est à toi de le dire.


                        Non mais j'ai bien compris qu'il codait récursivement les Tours de Hanoï, c'est écrit dans son premier message, et les appels récursifs de sa fonction sont bien lisibles.

                        Ce que je ne comprends pas c'est son objectif précis par rapport à l'enigme : en principe, cela devrait être de générer une suite de déplacements (i, j) ; au lieu de cela, il remplit une liste avec les entiers 0 à 7, et dit BINGO, ben effectivement, je vois pas le rapport.

                        En outre, il y a trois listes (j'imagine une par tige) et je ne vois pas leur rôle dans le problème posé.

                        • Partager sur Facebook
                        • Partager sur Twitter
                          25 mai 2020 à 19:10:59

                          OK, c'est la liste des déplacements que tu veux? Par exemple:
                          tour 1 à tour 2, tour 1 à tour 3, etc.
                          Je l'avais presque dans mon premier code. Je l'affichais au lieu de le placer dans une liste.
                          • Partager sur Facebook
                          • Partager sur Twitter

                          Le Tout est souvent plus grand que la somme de ses parties.

                            26 mai 2020 à 8:00:15

                            PierrotLeFou a écrit:

                            @Rambert111:
                            De toute évidence ton code fonctionne.
                            Petite question: programmes-tu en C ou C++?
                            Je code en C mais j'essaie de coder en Python d'une autre façon.
                            Si tu t'es donné la peine de le faire sur papier et de trouver une méthode récursive par toi-même, Bravo!
                            Tu es peut-être un débutant en Python. Les experts sont fainéants et codent le plus simple possible. :)


                            du python :)

                            C'est pas très clair. Quel est ton but, à quoi servent les Ti ?


                            en effet

                            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 

                            T[i] pour dire que je mets le disque i=1, 2 ou ... 7 dans la "place" représentée par une liste vide "[]" sur le piquet 

                            [Aie c'est chaud pourquoi le forum OCR limite la fréquence des messages à 24h?]

                             J'avais pas réussi à faire des piquets des listes vides T1=[], T2=[] pour faire append(chaque disque) et je pense que c'aurait été moins fiable car les disques n'auraient pas été dans le bon ordre. N'oubliez pas la règle du jeu : jamais un disque plus large sur un plus petit

                            -
                            Edité par Rambert111 26 mai 2020 à 8:16:47

                            • Partager sur Facebook
                            • Partager sur Twitter
                              26 mai 2020 à 8:13:57

                              Le truc à voir, pour le raisonnement récursif : 

                              Quand on veut déplacer la pile de disques du point A au point B, il y a un moment où il va falloir déplacer le plus gros disque de A à B (Ça serait idiot de le déplacer de A à  C, pour devoir le trimballer de B à C ensuite)

                              Pour faire ça, il faut que la piste soit dégagée, c'est à dire que tous autres disques soient sur C. Donc on se débrouille pour les mettre là, on bouge le gros, et on les amène à la position finale.

                              Dans la programmation, les listes sont là pour pouvoir dessiner la situation à chaque étape. Inutile si on veut juste connaître la liste des mouvements.

                              -
                              Edité par michelbillaud 26 mai 2020 à 8:16:43

                              • Partager sur Facebook
                              • Partager sur Twitter
                                26 mai 2020 à 8:43:22

                                Oui sur le net il existe des codes extraordinairement simples au final dont je n'ai pas eu l'intuition en trois jours

                                def hanoi(n,a=1,b=2,c=3):
                                    if (n > 0):
                                        hanoi(n-1,a,c,b)
                                        print "Déplace ",a,"sur",c
                                        hanoi(n-1,b,a,c)  #Mais on ne "voit" pas les disques ni les tours

                                https://codes-sources.commentcamarche.net/source/40685-tours-de-hanoi-simple-et-rapide

                                Cependant je n'ai pour ma part trouvé aucun programme qui permettait de manipuler les disques comme des objets (élements d'une liste) afin de vérifier que la machine elle même produit bien le résultat final, à savoir les huit disques sur la tour opposée.

                                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]
                                [[], [], [], [], [], [], [], []]
                                # Dans cette version là j'aimerais voir chaque étape mais c'est mathématiquement incohérent au final;
                                il y a moins de 255 étapes à la fin
                                Bref c'est savoureux de découvrir les mystères de la programmation
                                Et pour info dans la légende originale des tours d'Edouard Lucas il y a 64 disques à déplacer
                                par les prêtres du temple. Je suis encore loin du compte ^^'

                                -
                                Edité par Rambert111 26 mai 2020 à 8:47:43

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  26 mai 2020 à 8:55:42

                                   move(0, j-1, k)
                                   move(j, j, k)
                                   move(0, j-1, k)

                                  et tu ne trouves pas bizarre de ne pas voir i là dedans ?

                                   ---------

                                  Sinon, en partant sur la base de

                                  hanoi(n-1,a,c,b)
                                  print "Déplace ",a,"sur",c
                                  hanoi(n-1,b,a,c)  

                                  on peut y arriver, en manipulant un objet qui représente l'état des tours.

                                  Par exemple, un tableau de 3 tableaux représentant chacun une tour (sommet à droite).

                                  On partirait par exemple de

                                  [ [4,3,2,1], [], [] ]

                                  pour arriver à

                                  [ [], [], [4, 3, 2, 1] ]

                                  -- c'est l'occasion de réviser mon python

                                  Le mouvement d'un disque se fait par

                                  def mouvement(tours, origine, destination):
                                      disque = tours[origine].pop()
                                      tours[destination].append(disque)
                                      print(origine, "->", destination, ":", tours)
                                  

                                  l'algorithme récursif par

                                  EDIT : il y a un bug, saurez-vous le trouver ?

                                  def hanoi(n, tours, origine, destination):
                                      if (n > 0):
                                          autre = 2 - (origine + destination)   # parce que 0+1+2 = 2
                                          hanoi(n-1, tours, origine, autre,)
                                          mouvement(tours, origine, destination);
                                          hanoi(n-1, tours, autre, destination)
                                  

                                  et le lancement par

                                  def game(n):
                                      hanoi(n, [ [n-i for i in range(n)], [], []], 0, 2)

                                  Si on essaie avec game(4) :

                                  0 -> 0 : [[4, 3, 2, 1], [], []]
                                  0 -> 2 : [[4, 3, 2], [], [1]]
                                  0 -> 2 : [[4, 3], [], [1, 2]]
                                  0 -> 0 : [[4, 3], [], [1, 2]]
                                  2 -> 0 : [[4, 3, 2], [], [1]]
                                  2 -> 0 : [[4, 3, 2, 1], [], []]
                                  0 -> 0 : [[4, 3, 2, 1], [], []]
                                  0 -> 2 : [[4, 3, 2], [], [1]]
                                  0 -> 2 : [[4, 3], [], [1, 2]]
                                  0 -> 0 : [[4, 3], [], [1, 2]]
                                  2 -> 0 : [[4, 3, 2], [], [1]]
                                  0 -> 2 : [[4, 3], [], [1, 2]]
                                  0 -> 0 : [[4, 3], [], [1, 2]]
                                  0 -> 2 : [[4], [], [1, 2, 3]]
                                  0 -> 2 : [[], [], [1, 2, 3, 4]]

                                  EDIT CE QUI EST HORRIBLEMENT FAUX :-)




                                  -
                                  Edité par michelbillaud 26 mai 2020 à 13:11:45

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    26 mai 2020 à 12:41:44

                                    Salut,

                                    @michelbillaud, le calcul autre = 2 - (origine + destination) ne fonctionne pas (pour aller de 0 à 1, tu obtiendras autre qui vaut 1, or il faut passer par 2). Même si c'est intéressant de chercher une formule qui marche, autant garder autre dans les arguments.

                                    def hanoi(n, tours, origine, destination, autre):
                                        if (n &gt; 0):
                                            hanoi(n-1, tours, origine, autre, destination)
                                            mouvement(tours, origine, destination)
                                            hanoi(n-1, tours, autre, destination, origine)
                                    

                                    -
                                    Edité par yo@n97one 26 mai 2020 à 12:45:47

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                    Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
                                      26 mai 2020 à 12:55:25

                                      Ah oui  0+1+2 ça fait 3, c'est vrai. J'avais pourtant pas bu, si tot le matin.

                                      Correction :

                                              autre = 3 - (origine + destination)   # parce que 0+1+2 = 3


                                      ça change un peu le résultat

                                      0 -> 1 : [[4, 3, 2], [1], []]
                                      0 -> 2 : [[4, 3], [1], [2]]
                                      1 -> 2 : [[4, 3], [], [2, 1]]
                                      0 -> 1 : [[4], [3], [2, 1]]
                                      2 -> 0 : [[4, 1], [3], [2]]
                                      2 -> 1 : [[4, 1], [3, 2], []]
                                      0 -> 1 : [[4], [3, 2, 1], []]
                                      0 -> 2 : [[], [3, 2, 1], [4]]
                                      1 -> 2 : [[], [3, 2], [4, 1]]
                                      1 -> 0 : [[2], [3], [4, 1]]
                                      2 -> 0 : [[2, 1], [3], [4]]
                                      1 -> 2 : [[2, 1], [], [4, 3]]
                                      0 -> 1 : [[2], [1], [4, 3]]
                                      0 -> 2 : [[], [1], [4, 3, 2]]
                                      1 -> 2 : [[], [], [4, 3, 2, 1]]


                                      A part ça, passer le 3ieme larron en paramètre ou le recalculer, vu qu'ils sont liés par une relation inversible : ça se discute, en effet.

                                      -
                                      Edité par michelbillaud 26 mai 2020 à 12:58:32

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        26 mai 2020 à 12:56:37

                                        michelbillaud a écrit:

                                         move(0, j-1, k)
                                         move(j, j, k)
                                         move(0, j-1, k)

                                        et tu ne trouves pas bizarre de ne pas voir i là dedans ?

                                         ---------En effet je me suis focalisé juste sur le fait que le résultat imprimé est les huit disques sur le piquet final mais c'est comme en math: deux erreurs peuvent donner le bon résultat mais le raisonnement n'est pas généralisable

                                        Sinon, en partant sur la base de

                                        hanoi(n-1,a,c,b)
                                        print "Déplace ",a,"sur",c
                                        hanoi(n-1,b,a,c)  

                                        on peut y arriver, en manipulant un objet qui représente l'état des tours.

                                        Par exemple, un tableau de 3 tableaux représentant chacun une tour (sommet à droite).

                                        On partirait par exemple de

                                        [ [4,3,2,1], [], [] ]

                                        pour arriver à

                                        [ [], [], [4, 3, 2, 1] ]

                                        -- c'est l'occasion de réviser mon python

                                        Le mouvement d'un disque se fait par

                                        def mouvement(tours, origine, destination):
                                            disque = tours[origine].pop()
                                            tours[destination].append(disque)
                                            print(origine, "->", destination, ":", tours)
                                        

                                        l'algorithme récursif par

                                        def hanoi(n, tours, origine, destination):
                                            if (n > 0):
                                                autre = 2 - (origine + destination)   # parce que 0+1+2 = 2
                                                hanoi(n-1, tours, origine, autre,)
                                                mouvement(tours, origine, destination);
                                                hanoi(n-1, tours, autre, destination)
                                        

                                        et le lancement par

                                        def game(n):
                                            hanoi(n, [ [n-i for i in range(n)], [], []], 0, 2)

                                        Si on essaie avec game(4) :

                                        0 -> 0 : [[4, 3, 2, 1], [], []]
                                        0 -> 2 : [[4, 3, 2], [], [1]]
                                        0 -> 2 : [[4, 3], [], [1, 2]]
                                        0 -> 0 : [[4, 3], [], [1, 2]]
                                        2 -> 0 : [[4, 3, 2], [], [1]]
                                        2 -> 0 : [[4, 3, 2, 1], [], []]
                                        0 -> 0 : [[4, 3, 2, 1], [], []]
                                        0 -> 2 : [[4, 3, 2], [], [1]]
                                        0 -> 2 : [[4, 3], [], [1, 2]]
                                        0 -> 0 : [[4, 3], [], [1, 2]]
                                        2 -> 0 : [[4, 3, 2], [], [1]]
                                        0 -> 2 : [[4, 3], [], [1, 2]]
                                        0 -> 0 : [[4, 3], [], [1, 2]]
                                        0 -> 2 : [[4], [], [1, 2, 3]]
                                        0 -> 2 : [[], [], [1, 2, 3, 4]]






                                        -
                                        Edité par michelbillaud il y a environ 1 heure


                                        Sympa la fonction pop que je dois apprendre

                                        Je me permets de partager le lien de mon autre post

                                        https://www.developpez.net/forums/d2078293/autres-langages/python/general-python/tours-hanoi/

                                        Beaucoup de remarques similaires, notamment la notion de départ, intermédiaire, arrivée c'est vrai

                                        -
                                        Edité par Rambert111 26 mai 2020 à 13:06:26

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          26 mai 2020 à 13:10:32

                                          C'est un élément de folklore qui est loin d'être une nouveauté !

                                          -
                                          Edité par michelbillaud 26 mai 2020 à 13:12:44

                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            26 mai 2020 à 14:52:24

                                            Ma solution était trop simple? Et j'avais déjà mentionné le pop()
                                            Les listes de listes, c'est un peu trop lourd ici.
                                            Comme j'ai déjà dit: pourquoi faire simple quand on peut faire compliqué?
                                            • Partager sur Facebook
                                            • Partager sur Twitter

                                            Le Tout est souvent plus grand que la somme de ses parties.

                                              26 mai 2020 à 18:11:45

                                              Trop lourd toi même :-)

                                              1. Si on veut représenter l'état à chaque étape, raisonnablement il faut 3 listes, chacune représentant une pile

                                              2. Argument de simplicité : c'est *beaucoup* plus léger d'avoir un tableau de trois listes (l'indice est le numéro de pile) que trois variables distinctes, avec des tests pour savoir laquelle on manipule.

                                              Mais bon, si tu as du code plus léger, montre-le code, et on admirera.

                                              ---

                                              Après il y a aussi une version itérative.

                                              On peut la trouver après avoir fait une petite observation, concernant la pile qui n'EST PAS utilisée lors d'un transfert de disque

                                              On remplace l'instruction print par

                                              print(3-origine-destination, ":", origine, "->", destination, ":", tours)
                                              

                                              et on s'apercoit que ce numéro suit une séquence cyclique

                                              Exemple avec 3

                                              1 : 0 -> 2 : [[3, 2], [], [1]]
                                              2 : 0 -> 1 : [[3], [2], [1]]
                                              0 : 2 -> 1 : [[3], [2, 1], []]
                                              1 : 0 -> 2 : [[], [2, 1], [3]]
                                              2 : 1 -> 0 : [[1], [2], [3]]
                                              0 : 1 -> 2 : [[1], [], [3, 2]]
                                              1 : 0 -> 2 : [[], [], [3, 2, 1]]

                                              Exemple avec 4



                                              2 : 0 -> 1 : [[4, 3, 2], [1], []]
                                              1 : 0 -> 2 : [[4, 3], [1], [2]]
                                              0 : 1 -> 2 : [[4, 3], [], [2, 1]]
                                              2 : 0 -> 1 : [[4], [3], [2, 1]]
                                              1 : 2 -> 0 : [[4, 1], [3], [2]]
                                              0 : 2 -> 1 : [[4, 1], [3, 2], []]
                                              2 : 0 -> 1 : [[4], [3, 2, 1], []]
                                              1 : 0 -> 2 : [[], [3, 2, 1], [4]]
                                              0 : 1 -> 2 : [[], [3, 2], [4, 1]]
                                              2 : 1 -> 0 : [[2], [3], [4, 1]]
                                              1 : 2 -> 0 : [[2, 1], [3], [4]]
                                              0 : 1 -> 2 : [[2, 1], [], [4, 3]]
                                              2 : 0 -> 1 : [[2], [1], [4, 3]]
                                              1 : 0 -> 2 : [[], [1], [4, 3, 2]]
                                              0 : 1 -> 2 : [[], [], [4, 3, 2, 1]]

                                              exemple avec 5

                                              1 : 0 -> 2 : [[5, 4, 3, 2], [], [1]]
                                              2 : 0 -> 1 : [[5, 4, 3], [2], [1]]
                                              0 : 2 -> 1 : [[5, 4, 3], [2, 1], []]
                                              1 : 0 -> 2 : [[5, 4], [2, 1], [3]]
                                              2 : 1 -> 0 : [[5, 4, 1], [2], [3]]
                                              0 : 1 -> 2 : [[5, 4, 1], [], [3, 2]]
                                              ...

                                              Bref il suffit de suivre un cycle 1,2,0,1,2,0 .... ou 2,1,0,2,1,0... pour savoir quel est le pilier intermédiaire à chaque étape. 

                                              - quel cycle ? Ca dépend de la parité

                                              - et qu'est ce qu'on fait avec ce numéro de pilier ? Un mouvement entre les deux autres piliers

                                              - quel mouvement ?  Pas le choix : le plus petit disque va sur l'autre.

                                              Evidemment, le fait que ça soit cyclique, ce n'est pas intuitif. C'est en faisant l'expérience qu'on le remarque. Ensuite, si on y tient, ça se démontre par récurrence :

                                              - pour transporter un nombre pair de disque de la pile x à la pile y, c'est la séquence (yzx),

                                              - quand n est impair : (zyx)

                                              Faut un peu de courage : il y a 6 permutations, et 2 parités : on n'a jamais que 12 cas à étudier :-)

                                              -
                                              Edité par michelbillaud 26 mai 2020 à 18:35:21

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                26 mai 2020 à 18:49:50

                                                michelbillaud a écrit:
                                                Trop lourd toi même :-)
                                                Merci pour le compliment. :)
                                                Ce que je trouve trop lourd, ce n'est pas l'utilisation de "listes", mais l'utilisation de "listes de listes".
                                                Mon code, je l'ai déjà posté. Tu n'a qu'à faire un copier-coller.
                                                Il y a même deux variantes, une qui se contente d'afficher les déplacements, l'autre qui les fait effectivement.
                                                Et dans mon second exemple, j'utilise bien mes listes comme une pile avec les pop et les append.

                                                -
                                                Edité par PierrotLeFou 26 mai 2020 à 18:54:01

                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                Le Tout est souvent plus grand que la somme de ses parties.

                                                  26 mai 2020 à 18:57:24

                                                  Dans ton exemple, tu n'affiches pas les listes dans l'ordre !

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    26 mai 2020 à 19:05:40

                                                    michelbillaud a écrit:

                                                    Dans ton exemple, tu n'affiches pas les listes dans l'ordre !

                                                    Quel ordre? Fais-tu allusion que les listes Départ, Arrivée et Intermédiaire ne sont pas affichées dans l'ordre que tu souhaites?

                                                    Ou bien c'est parce que le plus grand disque est à l'indice 0?.

                                                    N'y a-t-il pas une fonction reverse() pour changer l'ordre?



                                                    -
                                                    Edité par PierrotLeFou 26 mai 2020 à 19:07:45

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter

                                                    Le Tout est souvent plus grand que la somme de ses parties.

                                                      26 mai 2020 à 23:51:40

                                                      Pour moi l'intérêt du code de Michel est qu'il donne à chaque étape l'état complet du jeu. Sa liste de listes est parfaitement naturelle, chaque liste étant une tige, chaque élément d'une liste étant un disque donné par son diamètre. L'autre intérêt de son code est qu'il modifie à peine la fonction «classique» de déplacement pour obtenir cette mémorisation de l'état du jeu, ce qui n'était pas si évident, ai-je trouvé en tous les cas.
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        27 mai 2020 à 10:32:37

                                                        et puis bon, quand on dit "c'est plus lourd", faut dire

                                                        • plus lourd que quoi, à fonctionnalités équivalentes
                                                        • quelle est la métrique utilisée.

                                                        -
                                                        Edité par michelbillaud 27 mai 2020 à 10:34:06

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          27 mai 2020 à 15:02:49

                                                          PascalOrtiz a écrit:

                                                          Pour moi l'intérêt du code de Michel est qu'il donne à chaque étape l'état complet du jeu. Sa liste de listes est parfaitement naturelle, chaque liste étant une tige, chaque élément d'une liste étant un disque donné par son diamètre. L'autre intérêt de son code est qu'il modifie à peine la fonction «classique» de déplacement pour obtenir cette mémorisation de l'état du jeu, ce qui n'était pas si évident, ai-je trouvé en tous les cas.

                                                          Bien sûr, je n'imprime pas tout à chaque étape. J'ai une liste par tour (ou tige). Les éléments sont placés dans un ordre tel qu'on peut retirer le disque le plus petit (le plus petit numéro) en premier.

                                                          Le disque le plus grand a le plus grand numéro.

                                                          Et je le fais sans liste de liste, ce qui serait totalement inutile ici.
                                                          Est-ce à ce point compliqué que de comprendre qu'une liste de liste est plus "lourde" qu'une liste.

                                                          Si le mot "lourd" ne vous plait pas, je pourrais utiliser le mot "complexe".

                                                          -
                                                          Edité par PierrotLeFou 27 mai 2020 à 15:09:18

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter

                                                          Le Tout est souvent plus grand que la somme de ses parties.

                                                            27 mai 2020 à 15:25:27

                                                            > Est-ce à ce point compliqué que de comprendre qu'une liste de liste est plus "lourde" qu'une liste.

                                                            Serait-ce à ce point compliqué de le démontrer, que tu ne t'y risques pas, et que tu tentes la pseudo-évidence ? :-)


                                                            L'utilisation d'une liste de nombres pour représenter une tige portant des disques prouve que

                                                            • on sait utiliser une liste Python.
                                                            • on a assez de capacité d'abstraction : 1) on représente un disque par un nombre - son diamètre - , et 2) une tige par une liste de nombres)

                                                            On a 3 tiges : une liste de 3 (représentations de) tiges. Rien de compliqué.

                                                            ---

                                                            > Bien sûr, je n'imprime pas tout à chaque étape.

                                                            Voila. On comparera quand ton code fera **la même chose** (c'est a dire afficher les 3 tiges à chaque étape, dans l'ordre d'origine des tiges)

                                                            Sinon, j'ai plus simple

                                                            def hanoi(n):
                                                                print("et voila")
                                                            



                                                            -
                                                            Edité par michelbillaud 27 mai 2020 à 15:29:17

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              27 mai 2020 à 15:27:05

                                                              Le PO veut justement voir chaque étape. Que proposes-tu donc comme solution pour voir chaque étape (dans ton code tu utilises trois listes, en quoi est-ce moins lourd qu'une liste de trois listes) ? On est d'accord que c'est plus lourd d'utiliser une liste de listes qu'une liste (par contre trois listes contre une liste de trois listes bof), mais dans ce cas c'est plus lourd d'utiliser une liste que rien du tout.

                                                              def hanoi(origine, dest, inter, n):
                                                                  if n &gt; 0:
                                                                      hanoi(origine, inter, dest, n - 1)
                                                                      print(f'Déplacer un disque de {origine} vers {dest}.')
                                                                      hanoi(inter, dest, origine, n - 1)
                                                                      
                                                              hanoi('A', 'C', 'B', 4)
                                                              

                                                              C'est moins lourd, mais ça ne fait pas ce que le PO veut.

                                                              PS : avec le&gt; du code à remplacer par >.

                                                              PS 2 : @michelbillaud en fait j'ai l'impression qu'il préfère une solution avec trois listes et hanoi qui prend en paramètre ces trois listes (qu'on peut donc afficher).

                                                              -
                                                              Edité par yo@n97one 27 mai 2020 à 15:48:41

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter
                                                              Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs

                                                              Tours de Hanoi

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown