Aller au contenu

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

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