Ep 47

le document

l'algorithme

Issue de : 23-NSI-08

EXERCICE 1

Sur le réseau social TipTop, on s’intéresse au nombre de « like » des abonnés. Les données sont stockées dans des dictionnaires où les clés sont les pseudos et les valeurs correspondantes sont les nombres de « like » comme ci-dessous :

• {'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}

Écrire une fonction max_dico qui :

• Prend en paramètre un dictionnaire dico non vide dont les clés sont des chaînes de caractères et les valeurs associées sont des entiers ;
• Renvoie un tuple dont :
  • La première valeur est la clé du dictionnaire associée à la valeur maximale ;
  • La seconde valeur est la première valeur maximale présente dans le dictionnaire.

🐍 Script Python

>>> max_dico({ 'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50 })
('Ada', 201)
>>> max_dico({ 'Alan': 222, 'Ada': 201, 'Eve': 222, 'Tim': 50 })
('Alan', 222

Réponse

Complétez le code ci-dessous

###

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

#Mettre votre code icibksl-nlbksl-nldef maxpy-unddico(dico):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert maxpy-unddico({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}) == ('Ada', 201)bksl-nl assert maxpy-unddico({'Alan': 222, 'Ada': 201, 'Eve': 220, 'Tim': 50}) == ('Alan', 222)bksl-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

---

---

Solution

###

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

def maxpy-unddico(dico):bksl-nl clepy-undmax = ''bksl-nl valpy-undmax = 0bksl-nl for cle in dico:bksl-nl if dico[cle] > valpy-undmax:bksl-nl valpy-undmax = dico[cle]bksl-nl clepy-undmax = clebksl-nl return (clepy-undmax, valpy-undmax)bksl-nl bksl-nl# Testez votre algorithmebksl-nltry:bksl-nl assert maxpy-unddico({'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50}) == ('Ada', 201)bksl-nl assert maxpy-unddico({'Alan': 222, 'Ada': 201, 'Eve': 220, 'Tim': 50}) == ('Alan', 222)bksl-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-nlbksl-nl

---

---

EXERCICE 2

Nous avons l’habitude de noter les expressions arithmétiques avec des parenthèses comme par exemple : (2 + 3) × 5.

Il existe une autre notation utilisée par certaines calculatrices, appelée notation postfixe, qui n’utilise pas de parenthèses.

L’expression arithmétique précédente est alors obtenue en saisissant successivement 2, puis 3, puis l’opérateur +, puis 5, et enfin l’opérateur ×. On modélise cette saisie par le tableau [2, 3, '+', 5, '*'].

Autre exemple, la notation postfixe de 3 × 2 + 5 est modélisée par le tableau :

• [3, 2, '*', 5, '+']

D’une manière plus générale, la valeur associée à une expression arithmétique en notation postfixe est déterminée à l’aide d’une pile en parcourant l’expression arithmétique de gauche à droite de la façon suivante :

• Si l’élément parcouru est un nombre, on le place au sommet de la pile ;
• Si l’élément parcouru est un opérateur, on récupère les deux éléments situés au sommet de la pile et on leur applique l’opérateur. On place alors le résultat au sommet de la pile.
• À la fin du parcours, il reste alors un seul élément dans la pile qui est le résultat de l’expression arithmétique.

Dans le cadre de cet exercice, on se limitera aux opérations × et +.

Pour cet exercice, on dispose d’une classe Pile qui implémente les méthodes de base sur la structure de pile.

Compléter le script de la fonction eval_expression qui reçoit en paramètre une liste python représentant la notation postfixe d’une expression arithmétique et qui renvoie sa valeur associée.

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()

def eval_expression(tab):
    p = Pile()
    for ... in tab: 
        if element != '+' ... element != '*': 
            p.empiler(...) 
        else:
            if element == ...: 
                resultat = ... + ... 
            else:
                resultat = ... 
            p.empiler(...) 
    return ...

🐍 Script Python

>>> max_dico({ 'Bob': 102, 'Ada': 201, 'Alice': 103, 'Tim': 50 })
('Ada', 201)
>>> max_dico({ 'Alan': 222, 'Ada': 201, 'Eve': 222, 'Tim': 50 })
('Alan', 222

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 le booléen True si la pile est vide, False sinon."""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.bksl-nl """bksl-nl assert not self.estpy-undvide()bksl-nl return self.contenu.pop()bksl-nlbksl-nldef evalpy-undexpression(tab):bksl-nl p = Pile()bksl-nl for ... in tab:bksl-nl if element != '+' ... element != 'py-str':bksl-nl p.empiler(...)bksl-nl else:bksl-nl if element == ...:bksl-nl resultat = p.depiler() + ...bksl-nl else:bksl-nl resultat = ...bksl-nl p.empiler(...)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 le booléen True si la pile est vide, False sinon."""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.bksl-nl """bksl-nl assert not self.estpy-undvide()bksl-nl return self.contenu.pop()bksl-nlbksl-nldef evalpy-undexpression(tab):bksl-nl p = Pile()bksl-nl for element in tab:bksl-nl if element != '+' and element != 'py-str':bksl-nl p.empiler(element)bksl-nl else:bksl-nl if element == '+':bksl-nl resultat = p.depiler() + p.depiler()bksl-nl else:bksl-nl resultat = p.depiler() py-str p.depiler()bksl-nl p.empiler(resultat)bksl-nl return p.depiler()bksl-nlbksl-nltry:bksl-nl assert evalpy-undexpression([2, 3, '+', 5, 'py-str']) == 25bksl-nl assert evalpy-undexpression([1, 2, '+', 3, 'py-str']) == 9bksl-nl assert evalpy-undexpression([1, 2, 3, '+', 'py-str']) == 5bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

---

---