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)
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
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 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.
> 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é.
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
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.
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.
@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.
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
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
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 :-)
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.
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
Le Tout est souvent plus grand que la somme de ses parties.
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 > 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> 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).
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.