Ep 08
le document
l'algorithme
Issue de : 23-NSI-21
EXERCICE 1
Le codage par diffĂ©rence (delta encoding en anglais) permet de compresser un tableau dedonnĂ©es en indiquant pour chaque donnĂ©e, sa diffĂ©rence avec la prĂ©cĂ©dente (plutĂŽt que la donnĂ©e elle-mĂȘme). On se retrouve alors avec un tableau de donnĂ©es plus petit, nĂ©cessitant moins de place en mĂ©moire. Cette mĂ©thode se rĂ©vĂšle efficace lorsque les valeurs consĂ©cutives
sont proches.
Programmer la fonction delta(liste)
qui prend en paramĂštre un tableau non vide de nombres entiers et qui renvoie un tableau contenant les valeurs entiĂšres compressĂ©es Ă lâaide cette technique.
Exemples :
đ Script Python>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
[42]
RĂ©ponse
Complétez le code ci-dessous
# Mettez votre code icibksl-nlbksl-nl
Solution
def delta(tab):bksl-nl diff = [tab[0]]bksl-nl for i in range(1, len(tab)):bksl-nl diff.append(tab[i] - tab[i-1])bksl-nl return diffbksl-nlbksl-nltry:bksl-nl assert delta([1000, 800, 802, 1000, 1003]) == [1000, -200, 2, 198, 3]bksl-nl assert delta([42]) == [42]bksl-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-nlbksl-nlbksl-nl
EXERCICE 2
Une expression arithmĂ©tique ne comportant que les quatre opĂ©rations +, â, Ă, Ă· peut ĂȘtre reprĂ©sentĂ©e sous forme dâarbre binaire. Les nĆuds internes sont des opĂ©rateurs et les feuilles
sont des nombres. Dans un tel arbre, la disposition des nĆuds joue le rĂŽle des parenthĂšses que nous connaissons bien.
![image](../arbre.png)
En parcourant en profondeur infixe lâarbre binaire ci-dessus, on retrouve lâexpression notĂ©e habituellement :
\[(3 \times (8 + 7)) â (2 + 1)\]
La classe Expr
ci-aprĂšs permet dâimplĂ©menter une structure dâarbre binaire.
La classe Expr
ci-aprĂšs permet dâimplĂ©menter une structure dâarbre binaire pour reprĂ©senter de telles expressions.
ComplĂ©ter la mĂ©thode rĂ©cursive infixe qui renvoie une chaĂźne de caractĂšres contenant des parenthĂšses reprĂ©sentant lâexpression arithmĂ©tique sur laquelle on lâapplique.
đ 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 | class Expr:
"""Classe implémentant un arbre d'expression."""
def __init__(self, g, v, d):
"""un objet Expr possĂšde 3 attributs :
- gauche : la sous-expression gauche ;
- valeur : la valeur de l'étiquette, opérande ou nombre ;
- droite : la sous-expression droite."""
self.gauche = g
self.valeur = v
self.droite = d
def est_une_feuille(self):
"""renvoie True si et seulement
si le noeud est une feuille"""
return self.gauche is None and self.droite is None
def infixe(self):
"""renvoie la représentation infixe de l'expression en
chaine de caractĂšres"""
s = ...
if self.gauche is not None:
s = '(' + s + ... .infixe()
s = s + ...
if ... is not None:
s = s + ... + ...
return s
|
đ Script Python>>> a = Expr(Expr(None, 1, None), '+', Expr(None, 2, None))
>>> a.infixe()
'(1+2)'
>>> b = Expr(Expr(Expr(None, 1, None), '+', Expr(None, 2, None)),
'*', Expr(Expr(None, 3, None), '+', Expr(None, 4, None)))
>>> b.infixe()
'((1+2)*(3+4))'
>>> e = Expr(Expr(Expr(None, 3, None), '*', Expr(Expr(None, 8, None),
'+', Expr(None, 7, None))),
'-', Expr(Expr(None, 2, None), '+', Expr(None, 1, None)))
>>> e.infixe()
'((3*(8+7))-(2+1))'
RĂ©ponse
Complétez le code ci-dessous
class Expr:bksl-nl """Classe implémentant un arbre d'expression."""bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, g, v, d):bksl-nl """un objet Expr possÚde 3 attributs :bksl-nl - gauche : la sous-expression gauche ;bksl-nl - valeur : la valeur de l'étiquette, opérande ou nombre ;bksl-nl - droite : la sous-expression droite."""bksl-nl self.gauche = gbksl-nl self.valeur = vbksl-nl self.droite = dbksl-nlbksl-nl def estpy-undunepy-undfeuille(self):bksl-nl """renvoie True si et seulement bksl-nl si le noeud est une feuille"""bksl-nl return self.gauche is None and self.droite is Nonebksl-nlbksl-nl def infixe(self):bksl-nl """renvoie la représentation infixe de l'expression enbksl-nl chaine de caractÚres"""bksl-nl s = ... bksl-nl if self.gauche is not None:bksl-nl s = '(' + s + ... .infixe() bksl-nl s = s + ... bksl-nl if ... is not None: bksl-nl s = s + ... + ... bksl-nl return sbksl-nl
Solution
class Expr:bksl-nl """Classe implĂ©mentant un arbre d'expression."""bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, g, v, d):bksl-nl """un objet Expr possĂšde 3 attributs :bksl-nl - gauche : la sous-expression gauche ;bksl-nl - valeur : la valeur de l'Ă©tiquette, opĂ©rande ou nombre ;bksl-nl - droite : la sous-expression droite."""bksl-nl self.gauche = gbksl-nl self.valeur = vbksl-nl self.droite = dbksl-nlbksl-nl def estpy-undunepy-undfeuille(self):bksl-nl """renvoie True si et seulement bksl-nl si le noeud est une feuille"""bksl-nl return self.gauche is None and self.droite is Nonebksl-nlbksl-nl def infixe(self):bksl-nl """renvoie la reprĂ©sentation infixe de l'expression enbksl-nl chaine de caractĂšres"""bksl-nl s = ''bksl-nl if self.gauche is not None:bksl-nl s = '(' + s + self.gauche.infixe() bksl-nl s = s + str(self.valeur) bksl-nl if self.droite is not None: bksl-nl s = s + self.droite.infixe() + ')'bksl-nl return sbksl-nlbksl-nltry:bksl-nl a = Expr(Expr(None, 1, None), '+', Expr(None, 2, None))bksl-nl assert a.infixe() == '(1+2)'bksl-nlbksl-nl b = Expr(Expr(Expr(None, 1, None), '+', Expr(None, 2, None)),bksl-nl 'py-str', Expr(Expr(None, 3, None), '+', Expr(None, 4, None)))bksl-nl assert b.infixe() == '((1+2)py-str(3+4))'bksl-nlbksl-nl e = Expr(Expr(Expr(None, 3, None), 'py-str', Expr(Expr(None, 8, None),bksl-nl '+', Expr(None, 7, None))),bksl-nl '-', Expr(Expr(None, 2, None), '+', Expr(None, 1, None)))bksl-nl assert e.infixe() == '((3py-str(8+7))-(2+1))'bksl-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-nlbksl-nl