Ep 03

le document

l'algorithme

Issue de : 23-NSI-10

EXERCICE 1

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

Exemples :

🐍 Script Python

>>> tab([98, 12, 104, 23, 131, 9])
131
>>> tab([-27, 24, -3, 15])
24

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

#Mettre votre code icibksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def maximumpy-undtableau(tab):bksl-nl maximum = tab[0]bksl-nl for element in tab:bksl-nl if element > maximum:bksl-nl maximum = elementbksl-nl return maximumbksl-nlbksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert maximumpy-undtableau([98, 12, 104, 23, 131, 9]) == 131bksl-nl assert maximumpy-undtableau([-27, 24, -3, 15]) == 24bksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

---

---

EXERCICE 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 :

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """Renvoie un booléen indiquant si la pile est vide."""
        return self.contenu == []

    def empiler(self, v):
        """Place l'élément v au sommet de la pile"""
        self.contenu.append(v)

    def depiler(self):
        """
        Retire et renvoie l'élément placé au sommet de la pile,
        si la pile n’est pas vide. Produit une erreur sinon.
        """
        assert not self.est_vide()
        return self.contenu.pop()

On souhaite programmer une fonction parenthesage qui prend en paramètre une chaîne de caractères ch formée 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.

Exemple :

🐍 Script Python

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

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Pile:bksl-nl """Classe définissant une structure de pile."""bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = []bksl-nlbksl-nl def estpy-undvide(self):bksl-nl """Renvoie un booléen indiquant si la pile est vide."""bksl-nl return self.contenu == []bksl-nlbksl-nl def empiler(self, v):bksl-nl """Place l'élément v au sommet de la pile"""bksl-nl self.contenu.append(v)bksl-nlbksl-nl def depiler(self):bksl-nl """bksl-nl Retire et renvoie l'élément placé au sommet de la pile,bksl-nl si la pile n’est pas vide. Produit une erreur sinon.bksl-nl """bksl-nl assert not self.estpy-undvide()bksl-nl return self.contenu.pop()bksl-nlbksl-nldef bonpy-undparenthesage(ch):bksl-nl """Renvoie un booléen indiquant si la chaîne chbksl-nl est bien parenthésée"""bksl-nl p = Pile()bksl-nl for c in ch:bksl-nl if c == ...: bksl-nl p.empiler(c)bksl-nl elif c == ...: bksl-nl if p.estpy-undvide():bksl-nl ...bksl-nl else:bksl-nl ...bksl-nl return ...bksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Pile:bksl-nl """Classe définissant une structure de pile."""bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = []bksl-nlbksl-nl def estpy-undvide(self):bksl-nl """Renvoie un booléen indiquant si la pile est vide."""bksl-nl return self.contenu == []bksl-nlbksl-nl def empiler(self, v):bksl-nl """Place l'élément v au sommet de la pile"""bksl-nl self.contenu.append(v)bksl-nlbksl-nl def depiler(self):bksl-nl """bksl-nl Retire et renvoie l'élément placé au sommet de la pile,bksl-nl si la pile n’est pas vide. Produit une erreur sinon.bksl-nl """bksl-nl assert not self.estpy-undvide()bksl-nl return self.contenu.pop()bksl-nlbksl-nldef bonpy-undparenthesage(ch):bksl-nl """Renvoie True si la chaîne ch est bien parenthésée et False sinon"""bksl-nl p = Pile()bksl-nl for c in ch:bksl-nl if c == '(':bksl-nl p.empiler(c)bksl-nl elif c == ')':bksl-nl if p.estpy-undvide():bksl-nl return Falsebksl-nl else:bksl-nl p.depiler()bksl-nl return p.estpy-undvide()bksl-nlbksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert bonpy-undparenthesage("((()())(()))") == Truebksl-nl assert bonpy-undparenthesage("())(()))") == Falsebksl-nl assert bonpy-undparenthesage("(())(())") == Falsebksl-nl print('Tout semble correct 👍')bksl-nl bksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

---

---