Les tours de Hanoï⚓︎

Indications et consignes⚓︎

Consignes

Vous devez tout d'abord télécharger ce fichier Python. À la fin, vous devez copier ce fichier, complété et renommé, dans le dossier devoir qui se trouve dans le dossier du groupe dans Echange.

Pour réaliser ce TP, vous pouvez le faire directement à l'aide du fichier Python et de Thonny. Vous pouvez aussi progresser en utilisant les IDE disponibles pour chaque exercice. Dans ce cas, vous devez copier vos fonctions dans le fichier au fur et à mesure.

Par contre, si vous êtes bloqué sur un exercice, vous pouvez réaliser les suivants à l'aide des IDE. En effet, le code de chaque fonction est ajouté en code caché à tous les exercices suivants.

Le code déjà présent dans le fichier

Le fichier contient déjà du code. En plus des fonctions à compléter au fur et à mesure des exercices, il y a aussi différentes classes et fonctions qui sont données. Il ne faut pas modifier ces classes et fonctions. De plus, vous ne devez pas utiliser les méthodes ou attributs des différentes classes, sauf mention contraire. Vous devez uniquement utiliser les fonctions indiquées dans les exemples.

Les piles

Pour manipuler les piles, vous pouvez utiliser les fonctions usuelles : pile_vide, est_vide, empile et depile.

>>> pile = pile_vide()
>>> est_vide(pile)
True
>>> empile(pile, 5)
>>> empile(pile, 3)
>>> depile(pile)
3
>>> est_vide(pile)
False

Vous pouvez également afficher le contenu d'une pile à l'aide de print. S'il y a plusieurs valeurs, le sommet se trouve à gauche et le fond de la pile à droite.

>>> pile = pile_vide()
>>> print(pile)
vide
>>> empile(pile, 5)
>>> print(pile)
5
>>> empile(pile, 3)
>>> empile(pile, 2)
>>> print(pile)
2/3/5

Ces piles sont "génériques". C'est-à-dire que vous pouvez tout à fait empiler des valeurs plus grandes sur des valeurs plus petites.

>>> pile = pile_vide()
>>> empile(pile, 2)
>>> empile(pile, 5)
>>> print(pile)
5/2

Dans le fichier Python, ces fonctions sont déjà définies et il ne faut pas les modifier.

Dans les IDE sur le site, ces fonctions sont également définie même si le code est cachée. Vous pouvez donc les utiliser dans chaque exercice sans rien rajouter.

Les piles et les disques

Les disques utilisés pour ce jeu seront représentés par des entiers correspondant à leurs tailles. Ainsi un disque de taille 5 sera représenté par le nombre 5 dans la pile.

Préparatifs⚓︎

Exercice 1

Compléter le code de la fonction sommet qui prend comme paramètre une pile non vide et renvoie la valeur se trouvant au sommet de la pile.

La pile doit retrouver son état initial après l'appel à cette fonction.

>>> p = pile_vide()
>>> empile(p, 5)
>>> empile(p, 4)
>>> empile(p, 1)
>>> print(p)
1/4/5
>>> sommet(p)
1
>>> print(p)  # On vérifie que la pile n'a pas changé
1/4/5

Évaluations restantes : ∞/∞

Exercice 2

Compléter le code de la fonction taille qui prend en paramètre une pile et renvoie le nombre d'éléments dans cette pile.

La pile doit retrouver son état initial après l'appel à cette fonction.

Utilisation des deux piles

Pour compter le nombre d'éléments, il faut dépiler la pile en empilant les éléments sur une autre pile. Il faut ensuite reconstituer la première pile, comme indiqué sur le schéma ci-dessous.

>>> p = pile_vide()
>>> empile(p, 5)
>>> empile(p, 4)
>>> empile(p, 2)
>>> print(p)
2/4/5
>>> taille(p)
3
>>> print(p)  # La pile n'a pas changé
2/4/5

Évaluations restantes : ∞/∞