Solution de Codage par différence - Sujet 30 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Le codage par différence (delta encoding en anglais) permet de compresser un tableau de donné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 :

>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]
>>> delta([42])
[42]

Exercice 2

EXERCICE 2 (10 points)

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.

flowchart TD
    r(("-")) --> m(("*"))
    r --> p1(("+"))
    m --> f3((3))
    m --> p2(("+"))
    p2 --> f8((8))
    p2 --> f7((7))
    p1 --> f2((2))
    p1 --> f1((1))

[Figure : arbre binaire d’expression. La racine porte l’étiquette -. Son fils gauche est un nœud * et son fils droit un nœud +. Le nœud * a pour fils gauche la feuille 3 et pour fils droit un nœud +, dont les deux fils sont les feuilles 8 et 7. Le nœud + de droite a pour fils les feuilles 2 et 1.]

En parcourant en profondeur infixe l’arbre binaire ci-dessus, on retrouve l’expression notée habituellement :

(3 × (8 + 7)) − (2 + 1)

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.

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érateur 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

Exemples :

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

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• 1 <= len(liste) <= 10^4
• liste est un tableau non vide de nombres entiers
• -10^9 <= liste[i] <= 10^9

Exercice 2

Contraintes :

• l’arbre comporte au plus 10^3 nœuds
• la profondeur de l’arbre est au plus 50
• chaque nœud interne possède exactement deux fils (gauche et droite non None), et chaque feuille n’en possède aucun (gauche et droite valent None)
• la valeur d’un nœud interne est l’une des chaînes de caractères '+', '-', '*', '/'
• la valeur d’une feuille est un entier tel que -10^9 <= valeur <= 10^9

Exercice 1 - le codage par différence

L’idée. On recopie la première valeur telle quelle : sans elle, on ne pourrait plus rien reconstruire. Ensuite, chaque valeur est remplacée par son écart avec celle qui la précède, c’est-à-dire liste[i] - liste[i-1]. Il n’y a donc qu’un seul parcours du tableau à faire, et le tableau renvoyé a exactement la même longueur que celui de départ.

Un petit exemple. Pour [1000, 800, 802] : on écrit 1000, puis 800 - 1000 = -200, puis 802 - 800 = 2, ce qui donne [1000, -200, 2].

def delta(liste):
    resultat = [liste[0]]
    # à partir du deuxième élément, on ne garde que l'écart avec le précédent
    for i in range(1, len(liste)):
        resultat.append(liste[i] - liste[i - 1])
    return resultat

resultat est le tableau que l’on construit ; on le démarre directement avec liste[0]. La boucle part de 1 et non de 0, parce qu’à l’indice 0 il n’y a pas d’élément précédent à soustraire. Comme on ajoute une valeur par tour de boucle, le tableau final contient bien len(liste) valeurs. Le cas delta([42]) ne demande aucun traitement à part : la boucle ne tourne pas une seule fois et on renvoie [42].

Exercice 2 - la méthode infixe

L’idée. On fabrique la chaîne s morceau par morceau, dans l’ordre où on lit l’expression : la partie gauche, puis l’étiquette du noeud, puis la partie droite. Un noeud interne a deux fils : on ouvre une parenthèse avant de descendre à gauche, et on la referme après être remonté de la droite. Une feuille n’a pas de fils : ni parenthèse, ni descente, juste son nombre. C’est là qu’intervient la récursivité : pour obtenir la chaîne d’un fils, on rappelle infixe() sur ce fils.

Un petit exemple. Pour l’arbre dont la racine est + avec les feuilles 1 et 2 : s vaut d’abord '', puis '(' + '1' donc '(1', puis on colle l’étiquette et on obtient '(1+', puis le fils droit avec la parenthèse fermante donne '(1+2)'.

    def infixe(self):
        """renvoie la représentation infixe de l'expression en
        chaine de caractères"""
        s = ''
        # la parenthèse ouvrante accompagne le fils gauche et la fermante le
        # fils droit : une feuille n'a ni l'un ni l'autre, donc pas de parenthèses
        if self.gauche is not None:
            s = s + '(' + self.gauche.infixe()
        s = s + str(self.valeur)
        if self.droite is not None:
            s = s + self.droite.infixe() + ')'
        return s

s est la chaîne en cours de construction : elle part vide et grandit toujours par la droite. Attention au str(self.valeur) : la valeur d’une feuille est un entier, et on ne peut pas concaténer un entier à une chaîne de caractères. Sur une feuille, les deux if sont faux : on renvoie simplement le nombre, et c’est ce qui arrête la récursion. Sur un noeud interne, au contraire, les deux if sont vrais, ce qui garantit qu’une parenthèse ouverte est toujours refermée.