Projet Tour d'Hanoï python pile/file/liste niveau terminale

Bonjour,

Comme la mécanique est répétitive (déplacer un disque à la fois d'une tige à l'autre, recommencer avec

un autre, etc...), on peut faire ça avec une fonction récursive

Et donc, le code est considérablement raccourci (8 lignes pour la fonction et une ligne pour l'appeler

ca fait 9 lignes en tout, avec un print pour l'affichage)

Après, l'affichage en art Ascii, c'est autre chose, mais déjà, pour la mécanique, c'est ça

Au fait, tu es au niveau terminale, le niveau terminal, c'est autre chose hi,hi,hi..

Bonjour,

Plutôt que de prendre le problème dans son ensemble, je te recommande de le décomposer par étape et de ne passer à la suivante que quand tu penseras que les précédentes sont faites. Ci-dessous je te propose une manière dont décomposer ton problème.

Concernant le problème des tours de Hanoï

Assure-toi d'avoir bien compris quel était le jeu des tours de HanoÏ.

Vue la manière dont l'exercice est formulé, je suppose qu'au début du programme, tous les disques sont empilés sur la même pile (la pile de départ), et on est donc dans le cas décrit dans ce lien. Note qu'il existe des variantes généralisées où l'on part d'un état arbitraire (voir ce lien).

En admettant que le problème soit sous sa forme non généralisée, celui-ci est caractérisé par :

• n : le nombre de disque (dans ton cas n <= 8, mais en vrai le problème se résout de la même manière dès que n est plus grand que 1)
• D, A, I : les piles de départ, d'arrivée et intermédiaire (ou pile de gauche, de droite, et du milieu).

L'objectif est de déplacer les n disques (empilés de bas en haut du plus large au plus étroit) de D vers A en exploitant I tout en garantissant qu'à chaque étape de l'algorithme, un disque n'est jamais par dessus un disque de diamètre inférieur.

Concernant la partie du programme qui résout le problème

Comme l'indique Phil_1857 #1 le problème peut se résoudre en écrivant un programme récursif, mais il est également possible de l'écrire sous forme itérative. L'avantage de la version récursive, c'est qu'elle est assez naturelle à écrire, elle est même donnée ici.

procédure Hanoï(n, D, A, I)
    si n ≠ 0
        Hanoï(n-1, D, I, A)
        Déplacer le disque de D vers A
        Hanoï(n-1, I, A, D)
    fin-si
fin-procédure

Il te suffit donc de retranscrire tout cela en python en exploitant la structure de Pile qui t'a été donnée. Prenons quelques instants pour expliquer ce que ça fait.

• n désigne le nombre de disque qui ne sont dans D et qu'on doit emmener dans A. Dans ton cas n est initialisé à N=8 et va progressivement diminuer, jusqu'à atteindre n=0 (si ton code est correct !).
• Lorsque n = 0, alors il n'y a plus de disque à déplacer et on a résolu le problème.
• Si n est strictement supérieur à 0, alors on cherche à se mettre dans une situation où il n'en reste plus que n-1 à déplacer de D vers A.
  • Il y a à ce stade n disques dans D, et N-n dans A.
  • On commence par déplacer les n-1 disques de D vers I en s'appuyant sur A (sans se préoccupe de ce qu'il y a dans A à ce stade, tout ce qu'elle contient déjà ne bougera pas). Cette étape est réalisée par l'appel récursif Hanoï(n-1, D, I, A). À l'issu de cet appel, il reste 1 disque dans D, n-1 disques dans I, et il y en a toujours N-n dans A.
  • Ensuite on déplace le dernier disque resté dans D vers A. Il y a donc à l'issu de cette instruction 0 disque dans D, n-1 dans I, et N-n+1 dans A.
  • Enfin, on déplace les n-1 disques de I vers A en s'appuyant sur D. C'est ce que réalise l'appel récursif Hanoï(n-1, I, A, D). À l'issu de cet appel récursif on a donc 0 disques dans I, N disques dans A et 0 disques dans D.
• Note qu'au cours de ces appels, D, I et A changent de rôle.

Le premier appel récursif est Hanoï(8, G, M, D) où G désigne la pile de gauche, M la pile du milieu, D la pile de droite.

En python, les variables se notent en minuscule et les caractères accentués sont une mauvaise idée, donc nous allons devoir adapter un peu les notations "maths". Admettons que l'on commence avec ce programme :

def hanoi(n, d, i, a):
    # A COMPELTER

# Initialisation
N = 8
g = cpile()
for k in range(n):
    enfiler(g, N - k)
m = cpile()
d = cpile()
print(g, m, d)

# Résolution
hanoi(N, g, m, d)
print(g, m, d)

Peux-tu compléter la fonction hanoi et nous montrer ce que tu as obtenu ?

Concernant le diamètre des disques

Note que dans ce programme, on n'a jamais besoin de se préoccuper de la taille des disques : si les empilements de départ sont initialement bien formés, alors il le reste tout au cours du jeu. C'est pour ça qu'à ce stade, on n'a même pas besoin de se préoccuper du diamètre des disques et dans l'absolu, on pourrait donc matérialiser un disque dans une pile par un symbole arbitraire.

Cependant, on aura besoin de le connaître si on veut dessiner les disques avec le bon diamètre. C'est pourquoi on a intérêt à représenter chaque disque par un entier qui correspond à son propre diamètre. Ainsi, lorsqu'on voudra afficher une pile, il suffira d'itérer sur les disques quel contient et adapter le rendu en fonction de son diamètre.

Concernant le code en charge d'afficher en ASCII art l'état du problème

L'exercice est assez mal formulé, mais comme tu l'as vu dans la première section, chaque appel récursif se matérialise en trois grandes étapes. Mais cela ne correspond pas aux trois étapes dont parle ton énoncé. Donc dans un premier temps ce que tu pourrais faire c'est afficher l'état du jeu après avoir réalisé l'instruction "Déplacer le disque de  D vers A".

Pour faire simple, tu peux sans doute représenter chaque disque par le nombre qui correspond à son diamètre, et ensuite réfléchir comment le représenter en ASCII art.

Personnellement ce que je ferais, c'est représenter un disque par des étoiles, le nombre d'étoiles étant proportionnel à son diamètre. Dans ton cas les diamètres vont de 1 à 8 et on aimerait que les disques soient tous centrés au niveau de leur tige.

En python, tu peux utiliser la multiplication pour répéter une chaîne. Par exemple "A" * 8 équivaut à AAAAAAAA. Tu peux donc de la même manière réfléchir à comment dessiner un disque de diamètre d. Je pense que le plus simple, c'est de le représenter par 2 * (d - 1) + 1 étoiles. À gauche de ces étoiles, il faudra dessiner N - d espaces (idem à droite si tu as des choses à écrire sur cette même ligne de texte. Appelons cette fonction dessiner_disque(d).

Par soucis de simplicité, je pense que tu as intérêt à dessiner chaque tige de disque les unes à la suite des autres, verticalement.

Si tu sais dessiner un disque, tu sais presque dessiner une pile : il suffit d'itérer sur chacun de ses éléments (du plus haut au plus bas) et d'appeler la fonction dessiner_disque en lui passant en paramètre le diamètre du disque courant.

Bonne chance