Les Tours de Hanoï

« Les tours de Hanoï » est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d’une tour de « départ » à une tour d’« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles suivantes :

  • on ne peut déplacer qu’un seul disque à la fois ;
  • on ne peut pas placer un disque au dessus d’un disque plus petit.

On suppose que cette dernière règle est également respectée dans la configuration de départ.

 

Classe principale du jeu

Le jeu des tours de Hanoï est défini par la classe Jeu_Hanoi suivante :

class Jeu_Hanoi:
    def __init__(self, nbr_disq = 6):
        self.n = nbr_disq
        self.A = Pile()
        self.B = Pile()
        self.C = Pile()
        # Remplissage initial de la première pile
        for d in range(self.n):
            self.A.push(self.n-d)
Code complet à copier coller
#!/usr/bin/env python
# -*- coding: utf-8 -*-

################################################################################
class Pile:
    def __init__(self):
        self.l = ListeC()

    def est_vide(self):
        return self.l.est_vide()

    def pop(self):
        return self.l.supprimer_debut().data

    def push(self, n):
        self.l.ajouter_debut(n)


################################################################################
class Maillon():
    def __init__(self, data = None):
        self.data = data
        self.suiv = None


################################################################################
class ListeC():
    def __init__(self):
        self.debut = None

    def est_vide(self):
        """ Renvoie True si la liste est vide
        """
        return self.debut is None

    def ajouter_debut(self, nM):
        """ Ajoute un maillon au début de la liste
            Si nM n'est pas de type Maillon, le maillon est créé
            Renvoie le maillon ajouté
        """
        if not isinstance(nM, Maillon):
            nM = Maillon(nM)
        if self.est_vide():
            self.debut = nM
        else:
            nM.suiv = self.debut
            self.debut = nM
        return nM

    def supprimer_debut(self):
        """ Supprime et renvoie le premier maillon de la liste
            IndexError si la liste est vide
        """
        if self.debut is not None:
            d = self.debut
            self.debut = self.debut.suiv
            return d
        else:
            raise IndexError("list index out of range")


################################################################################
################################################################################
class Jeu_Hanoi:
    def __init__(self, nbr_disq = 6):
        self.n = nbr_disq
        self.A = Pile()
        self.B = Pile()
        self.C = Pile()
        # Remplissage initial de la première pile
        for d in range(self.n):
            self.A.push(self.n-d)

    def __repr__(self):
        def ch_dsq(n):
            s = ""
            # ??????
            return s

        def ch_tour(t):
            l = []
            p = Pile()
            while not t.est_vide():
                n = t.pop()
                l.append(ch_dsq(n))
                p.push(n)
            # ??????
            return l

        L = []
        for tour in [self.A, self.B, self.C]:
            L.append(ch_tour(tour))

        ch = ""
        for d in range(self.n):
            ch += L[0][d] + L[1][d] + L[2][d] + "\n"
        return ch


    def get_tour(self, nom):
        """ Renvoie la Pile nommée nom (type str)
                exemple : 'A' --> self.A
        """
        if nom == 'A':
            return self.A
        elif nom == 'B':
            return self.B
        elif nom == 'C':
            return self.C


def hanoi(j, n, d, a, l):
    pass
    # ?????


if __name__ == "__main__":
    j = Jeu_Hanoi()
    hanoi(j, j.n, 'A', 'C', 'B')

 

Affichage

d’un disque

La fonction ch_dsq(n)doit permettre de générer une chaîne de caractères représentant un disque de taille n(1 < n < nombre de disques dans le jeu). La longueur de cette chaîne ne dépend que du nombre de disques du jeu.

Exemples , pour un jeu à 6 disques :

    • ch_dsq(4)"  ****|****  "
    • ch_dsq(0)"      |      "

 

Compléter la fonction ch_dsq(n). (il pourra être nécessaire de la tester en dehors de la méthode __repr__())

 

d’une tour

La fonction ch_tour(t)permet de générer une liste de chaînes de caractères représentant l’ensemble des disques présents sur la tour t. La taille de de cette liste doit être toujours égale au nombre de disques du jeu.

Exemple pour une tour de 4 disques dans un jeu à 6 disques :

 ["      |      ", "      |      ", "     *|*     ", "   ***|***   ", "  ****|****  ", "******|******"]

 

Compléter la fonction ch_tour(t) permettant de générer une liste de lignes de texte représentant l’ensemble des disques fichés sur la tour t.

 

Déplacement

La méthode get_tour attend un seul argument (de type str, valant 'A', 'B' ou 'C') désignant une des tours du jeu et renvoie l’attributAttribut Un attribut est un identifiant (un nom) décrivant une information stockée dans une base. Les attributs correspondent aux colonnes si la relation à laquelle il appartient est représentée sous forme de table. A, B ou C de l’objet de type Jeu_Hanoi (de type Pile).

Écrire, pour la classe Jeu_Hanoi, une méthode deplacer, qui attend deux arguments de type str désignant deux des tours du jeu, et déplace le disque depuis la tour de « départ » (1er argument de la méthode) jusqu’à la tour d' »arrivée » (2ème argument de la méthode).
Remarque : inutile de vérifier si la pile de départ est vide ou pas

 

 

 

Résolution du jeu

La résolution du jeu peut se faire de façon extrêmement simple … si l’on parvient à identifier la récursivité de la méthode :

Déplacer une pile de n disques depuis une tour de départ vers une tour d’arrivée en utilisant une tour libre (opération que l’on n’a pas le droit de faire en une seule étape) :

Revient à :

  • déplacer une pile de n-1 disques depuis une tour de départ vers une tour libre (opération que l’on n’a pas le droit de faire en une seule étape) :

  • déplacer le disque restant (depuis la tour de départ) vers la tour d’arrivée (opération autorisée !) :

  • et enfin re-déplacer la pile de n-1 disques depuis la tour initialement libre (et qui le redevient !) vers la tour d’arrivée (opération que l’on n’a pas le droit de faire en une seule étape) :

 

Écrire une fonction hanoi(j, n, d, a, l), sous forme récursive qui résout le jeu j (type Jeu_Hanoi) , ce qui revient à déplacer n disques (de type int) depuis une tour de départ d (type str) vers une tour d’arrivée a (type str) en utilisant une tour libre l (type str).

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code