C3 : Exercices

C3.E1 : Manipulation des piles

On s'intéresse aux structures de données de type pile que l'on implémente à l'aide des fonctions suivantes :

• - cree_pile() qui renvoie une pile vide ;
• - est_pile_vide(p) qui renvoie true ou false ;
• - depile(p) qui renvoie le dernier élément empilé (ou None si la pile p est vide) ;
• - empile(p, elt) qui ajoute elt à la pile p.

1) On considère la suite d'instructions suivante :

p1 = cree_pile()
p2 = cree_pile()
p3 = cree_pile()
empile(p1, 10)
empile(p1, 15)
empile(p1, 5)
empile(p2, 20)
empile(p2, 25)

Représenter les piles p1, p2 et p3 à la fin de l'exécution de ce code en recopiant et complétant le schéma ci-dessous.

2) Que renvoient les instructions suivantes :

• - est_pile_vide(p1) ?
• - est_pile_vide(p2) ?
• - est_pile_vide(p3) ?

3) Représenter les piles p1, p2 et p3 à la fin de l'exécution du code suivant :

empile(p3, depile(p2))
empile(p1, depile(p2))
empile(p2, depile(p3))
empile(p2, depile(p1))

4) Proposer une suite d'instructions de façon à inverser l'ordre des éléments de p1.

C3.E2 : Appartenance à une pile

1) Écrire une fonction est_dans(elt, pile:Pile) qui :

• - prend un élément et une instance de la classe Pile en paramètres ;
• - renvoie True ou False suivant si l'élément est dans la pile ou non.

Remarque : cette fonction ne devra pas avoir d'effets de bords.

2) Ajouter la méthode contient(self, elt) à la classe Pile. Cette méthode doit prendre un élément en paramètre et renvoyer True ou False suivant si l'élément se trouve dans la pile ou non.

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def est_dans(elt, pile:Pile) -> bool:
    rep = False
    p0 = Pile()
    # dépilage de p pour voir si elt est dans p
    continuer = True
    while continuer:
        elt0 = pile.depile()
        p0.empile(elt0)
        if elt0 == elt:
            continuer = False
            rep = True
        elif pile.est_vide():
            continuer = False
    # rempilage dans p pour que p retrouve son état initial
    while not p0.est_vide():
        pile.empile(p0.depile())
    return rep

p1 = Pile()
print(est_dans(4,p1)) #False
p1.empile(3)
p1.empile(4)
print(est_dans(4,p1)) #True
print(est_dans(5,p1)) #False
p1.depile()
print(est_dans(3,p1)) #True
print(est_dans(4,p1)) #false

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None
    def contient(self, elt):
        return elt in self.__valeurs

p1 = Pile()
print(p1.contient(4)) #False
p1.empile(3)
p1.empile(4)
print(p1.contient(4)) #True
print(p1.contient(5)) #False
p1.depile()
print(p1.contient(3)) #True
print(p1.contient(4)) #False

C3.E3 : Plus grande valeur d'une pile

Écrire une fonction maxi(p:Pile) qui :

• - prend une instance de la classe Pile en paramètre ;
• - renvoie la plus grande valeur de cette pile si elle n'est pas vide et None sinon.

Remarque : cette fonction ne devra pas avoir d'effet de bords.

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def maxi(p:Pile) -> bool:
    p0 = Pile()
    if p.est_vide():
        return None
    # dépilage du premier élément de p
    elt_max = p.depile()
    p0.empile(elt_max)
    # dépilage de p pour voir si elt est dans p
    while not p.est_vide():
        elt = p.depile()
        p0.empile(elt)
        if elt > elt_max:
            elt_max = elt
    # rempilage dans p pour que p retrouve son état initial
    while not p0.est_vide():
        p.empile(p0.depile())
    return elt_max

p1 = Pile()
print(maxi(p1)) #None
p1.empile(3)
p1.empile(4)
print(maxi(p1)) #4
p1.empile(2)
print(maxi(p1)) #4

C3.E4 : Nombre d'éléments d'une file

Écrire une fonction long(f:File)->int qui :

• - prend un objet instance de la classe File en paramètre ;
• - renvoie le nombre d'éléments de cette file.

Remarque : cette fonction ne devra pas avoir d'effet de bords.

C3.E5(*) : Comparaison de deux files

Écrire une fonction sont_identiques(f1:File, f2:File) qui prend deux objets qui sont des instances d'une classe File en paramètres et renvoie True si les deux piles sont identiques ou False dans le cas contraire.

Remarque : les files passées en paramètres doivent retrouver leur état d'origine à la fin de l'exécution de la fonction.

class File:
    def __init__(self):
        self.__donnees = []

    def est_vide(self):
        return self.__donnees == []

    def enfile(self, elt):
        self.__donnees = [elt] + self.__donnees

    def defile(self):
        if not self.est_vide():
            return self.__donnees.pop()
        else:
            return None
    def to_str(self):
        chaine = "→ "
        for elt in self.__donnees:
            chaine = chaine + str(elt) + " "
        chaine = chaine + "→"
        return chaine

def sont_identiques(f1:File, f2:File):
    f1_bis = File()
    f2_bis = File()
    identiques = True
    while not (f1.est_vide() and f2.est_vide()):
        elt1 = f1.defile()
        if elt1 != None:
            f1_bis.enfile(elt1)
        elt2 = f2.defile()
        if elt2 != None:
            f2_bis.enfile(elt2)
        if elt1 != elt2:
            identiques = False
    while not f1_bis.est_vide():
        f1.enfile(f1_bis.defile())
    while not f2_bis.est_vide():
        f2.enfile(f2_bis.defile())
    return identiques


# Programme principal
print('=== Test n° 1 ===')
fi1 = File()
fi1.enfile(10)
fi1.enfile(20)
fi2 = File()
fi2.enfile(10)
fi2.enfile(20)
print(sont_identiques(fi1, fi2))
print(fi1.to_str())
print(fi2.to_str())

print('=== Test n° 2 ===')
fi1 = File()
fi2 = File()
print(sont_identiques(fi1, fi2))
print(fi1.to_str())
print(fi2.to_str())

print('=== Test n° 3 ===')
fi1 = File()
fi1.enfile(50)
fi2 = File()
fi2.enfile(10)
fi2.enfile(20)
print(sont_identiques(fi1, fi2))
print(fi1.to_str())
print(fi2.to_str())

print('=== Test n° 4 ===')
fi1 = File()
fi1.enfile(100)
fi1.enfile(200)
fi2 = File()
fi2.enfile(10)
fi2.enfile(20)
print(sont_identiques(fi1, fi2))
print(fi1.to_str())
print(fi2.to_str())

C3.Pb1 : Un bon parenthésage

On considère une chaine de caractères incluant à la fois des parenthèses rondes () est des parenthèses carrées [].

La chaine est bien parenthésée si :

• • chaque parenthèse ouvrante est associée à une unique parenthèse fermente du même type, et réciproquement,
• • les paires de parenthèses ne sont pas entrelassées.

Par exemple :

• • "()" est bien parenthésée,
• • "[()]" est bien parenthésée
• • "[]()" est bien parenthésée
• • "(" n'est pas bien parenthésée
• • "]" n'est pas bien parenthésée
• • "()]" n'est pas bien parenthésée
• • "([]" n'est pas bien parenthésée
• • "([)]" n'est pas bien parenthésée

1) Rappeler la spécificité des piles et des listes.

2) Quelle structure de données pour les parenthèses vous semble être la plus adaptée au problème ?

3) Écrire une fonction qui prend une chaine avec parenthèses en paramètre et renvoie True si la chaine est bien parenthésée ou False dans le cas contraire.

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def est_ok(chaine):
    li_ouv = ["(", "[", "{"]
    li_ferm = [")", "]", "}"]
    pile = Pile()
    for c in chaine:
        if c in li_ouv:
            pile.empile(c)
        elif c in li_ferm:
            if pile.est_vide():
                return False
            else:
                c2 = pile.depile()
                if c != li_ferm[li_ouv.index(c2)]:
                    return False
    if pile.est_vide():
        return True
    else:
        return False

print(est_ok("()") == True)
print(est_ok(")") == False)
print(est_ok("(") == False)
print(est_ok("[()]") == True)
print(est_ok("[(])") == False)
print(est_ok("()[]") == True)
print(est_ok("()]") == False)
print(est_ok("()[") == False)

C3.Pb2 : Retour sur le jeu "Ranger les assiettes"

Pour cet exercice, on dispose d'une classe Pile dont l'interface est :

• - le constructeur : qui permet d'avoir une pile vide
• - est_vide : qui renvoie True ou False suivant si la pile est vide ou non ;
• - empile(elt) : qui permet d'ajouter un élément à la pile ;
• - depile : qui permet d'enlever et de récupérer l'élément de la pile (ou None si la pile est vide) ;
• - to_str : qui renvoie une chaine de caractères permettant de visualiser le contenu de la pile ;
• - est_egale_a(p2:Pile) : qui renvoie True ou False suivant si la pile est égale à la pile p2 passée en paramètre.

En utilisation cette classe Pile, programmer le jeu "Ranger les assiettes".

Le code ci-dessous n'est pas utile à la résolution de l'exercice, il est donné uniquement pour tester son programme.

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

    def to_str(self) -> str:
        '''
        Méthode qui renvoie une chaine de caractère correspondant au contenu de la Pile.
        '''
        chaine = ""
        for val in self.__valeurs:
            chaine = chaine + str(val)
        return chaine

    def est_egale(self, pile2) -> Bool:
        '''
        Methode qui permet de tester l'égalité avec une autre pile passée en paramètre.
        Param pile2 (Pile)
        Return (Bool)
        '''
        pile2_inv = Pile()

        # Comparaison des éléments en dépilant pile2
        test = True
        if ( (self.est_vide() and not pile2.est_vide())
                or (not self.est_vide() and pile2.est_vide()) ) :
            test = False
        else:
            pos = len(self.__valeurs)-1
            while pos >= 0 and not pile2.est_vide():
                elt = self.__valeurs[pos]
                elt2 = pile2.depile()
                if elt != elt2:
                    test = False
                pile2_inv.empile(elt2)
                pos = pos - 1

            # Rempilage de pile2
            while not pile2_inv.est_vide():
                pile2.empile(pile2_inv.depile())

        return test

C3.Pb3 : Les tours de Hanoï

D'après l'encyclopédie en ligne Wikipédia, "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 plus d'un disque à la fois ;
• - on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

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

A faire : Programmer le jeu des Tours de Hanoï en Python en utilisant une structure de données de type Pile.