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

Question

Bonjour,

J'aurais besoin d'un algorithme par rapport au projet d'Hanoï, je n'y arrive vraiment pas du tout et je dois le rendre lundi qui arrive. Voici les consignes à respecter de ce projet :

Explication :

Le problème des tours de Hanoï est un problème mathématique assez connu. On dispose de 3 tiges et, empilés sur la tige de gauche, de disques de tailles croissantes.

L’objectif est de déplacer tous les disques de la tige 1 à la tige 3 en respectant les règles suivantes :

Un seul disque peut être déplacé à la fois
	On ne peut jamais poser un disque sur un disque de taille inférieure.

Important :

L’objectif de ce projet est donc de définir une structure de donnée adaptée (parmi les trois structures de données que l’on a vu : listes chaÎnées, piles ou files) pour modéliser les disques, puis de conceptualiser et implémenter un algorithme qui permet de résoudre le problème.

Il faut que l'algorithme demande au joueur (nous) de choisir un nombre de disques afin que l'ordinateur résolve le problème de manière automatique tout en affichant les disques sur les tiges MAIS PAS chaque déplacement. Par exemple, si on choisit 5, premièrement on affiche les 5 disques sur la tige de gauche, puis deuxièmement le disque le plus grand sur la tige de droite et les 4 autres au milieu et dernièrement tous les disques à droite, soit 3 affichages avec important l'ASCII ART !

Tout cela avec un niveau lycée terminale, ne sortez pas des fonctions trop compliquées please.

Le nombre de disques possible de choisir par le joueur sera limité à 8 !

Aide :

On peut aborder le problème de la façon suivante :

Pour envoyer un tour de taille n de la place de gauche à la place de droite :

On envoie les n-1 premiers disques sur la place du milieu, ce qui revient à résoudre le jeu pour n-1 disques avec le départ à gauche et l’arrivée au milieu.
	On envoie le disque n à droite.
	On envoie les n-1 premiers disques sur la place de droite, ce qui revient à résoudre le jeu pour n-1 disques avec le départ au milieu et l’arrivée à droite.

Vous pouvez utiliser PILES, les FILES ou les LISTES CHAÎNÉES. Il est recommandé d'utiliser les piles dont les fonctions de base sont données ci-dessous. Si l'on utilise autre chose, détailler les explications détaillées pour bien que le programme soit compréhensible.

def cpile():
    return[]

def est_vide(P):
    if len(P)==0:
        return True
    else :
        return False

def empile(P,e):
    P=P.append(e)
    return P

def depiler(P):
    print(P.pop())

def sommet(P):
    if est_vide(P):
        return "impossible"
    else:
        return P[-1]

def taille(P):
    return len(P)

P=cpile()

Dans le cas où vous utiliserez les FILES, voici les fonctions de base :
def cfile():
    return[]

def estvide(F):
    if len(F)==0:
        return True
    else:
        return False

def enfiler(F,x):
    F.insert(0,x)

def defiler(F):
    if estvide(F):
        return None
    else:
        premier=F.pop()
        return premier

def tete(F):
    if estvide(F):
        return None
    else:
        return F[-1]

def taille(F):
    return len(F)

A partir de ces fonctions, il faut créer l'algorithme permettant à l'ordinateur de jouer et de gagner à la fin.

En final, il faudrait que cet algorithme affiche bien les disques à l'aide de ASCII ART et qu'il résout tout automatiquement MAIS avec une limite de 8 disques.

Je vous remercie d'avoir pris le temps de lire et de m'aider car vraiment je compte sur vous !

Phil_1857 · Answer

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

mamiemando · Answer

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

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

2 réponses

Discussions similaires