Aller au contenu

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

###
#Mettre votre code icibksl-nlbksl-nl



Solution

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

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

###
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

###
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