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
#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
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 :
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.
đ Script Python |
---|
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 | 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
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
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