Aller au contenu

Sujet n°24

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

Écrire la fonction maxliste, prenant en paramètre un tableau non vide de nombres tab (type list) et renvoyant le plus grand élément de ce tableau.

Exemples

>>> maxliste([98, 12, 104, 23, 131, 9])
131

>>> maxliste([-27, 24, -3, 15])
24
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def maxliste(tab):
    """
    tab - list, tableau non vide d'entiers
    Sortie: int - Plus grand élément de tab
    """
    maxi = tab[0]
    for elt in tab:
        if elt > maxi:
            maxi = elt
    return maxi


if __name__ == '__main__':
    print(maxliste([98, 12, 104, 23, 131, 9]) == 131)
    print(maxliste([-27, 24, -3, 15]) == 24)

Exercice n°2

On dispose de chaînes de caractères contenant uniquement des parenthèses ouvrantes et fermantes.

Un parenthésage est correct si :

  • le nombre de parenthèses ouvrantes de la chaîne est égal au nombre de parenthèses fermantes.
  • en parcourant la chaîne de gauche à droite, le nombre de parenthèses déjà ouvertes doit être, à tout moment, supérieur ou égal au nombre de parenthèses déjà fermées.

Ainsi, "((()())(()))" est un parenthésage correct.
Les parenthésages "())(()" et "(())(()" sont, eux, incorrects.

On dispose du code de la classe Pile suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Pile:
    """ Classe définissant une pile """
    def __init__(self, valeurs=[]):
        self.valeurs = valeurs

    def est_vide(self):
        """Renvoie True si la pile est vide, False sinon"""
        return self.valeurs == []

    def empiler(self, c):
        """Place l’élément c au sommet de la pile"""
        self.valeurs.append(c)

    def depiler(self):
        """Supprime l’élément placé au sommet de la pile, à condition qu’elle soit non vide"""
        if self.est_vide() == False:
            self.valeurs.pop()

On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne ch de parenthèses et renvoie True si la chaîne est bien parenthésée et False sinon. Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve une parenthèse fermante, on dépile (si possible !) la parenthèse ouvrante stockée au sommet de la pile. La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide. Elle est, par contre, mal parenthésée :

  • si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide ;
  • ou si, à la fin du parcours, la pile n’est pas vide.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def parenthesage (ch):
    """Renvoie True si la chaîne ch est bien parenthésée et False sinon"""
    p = Pile([])
    for c in ch:
        if c == ...:
            p.empiler(c)
        elif c == ...:
            if p.est_vide():
                return ...
            else:
                ...
    return p.est_vide()

assert parenthesage("((()())(()))") == True
assert parenthesage("())(()") == False
assert parenthesage("(())(()") == False
Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. On retrouve à nouveau un objet ayant un paramètre mutable valeurs initialisé par défaut, donc tous les problèmes d'effets de bord déjà commentés dans d'autres sujets...
    La ligne 3 diffère donc du code original pour éviter ces problèmes.

  3. L'exemple est proposé avec des assertions, ce qui diffère des énoncés habituels et devrait être évité par soucis d'harmonisation :

    >>> parenthesage("((()())(()))")
    True
    >>> parenthesage("())(()")
    False
    >>> parenthesage("(())(()")
    False
    

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Pile:
    """ Classe définissant une pile """
    def __init__(self, valeurs=[]):
        self.valeurs = valeurs

    def est_vide(self):
        """Renvoie True si la pile est vide, False sinon"""
        return self.valeurs == []

    def empiler(self, c):
        """Place l’élément c au sommet de la pile"""
        self.valeurs.append(c)

    def depiler(self):
        """Supprime l’élément placé au sommet de la pile, à condition qu’elle soit non vide"""
        if self.est_vide() == False:
            self.valeurs.pop()


def parenthesage (ch):
    """Renvoie True si la chaîne ch est bien parenthésée et False sinon"""
    p = Pile()
    for c in ch:
        if c == "(":
            p.empiler(c)
        elif c == ")":
            if p.est_vide():
                return False
            else:
                p.depiler()
    return p.est_vide()


if __name__ == '__main__':
    print(parenthesage("((()())(()))") == True)
    print(parenthesage("())(()") == False)
    print(parenthesage("(())(()") == False)