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

Énoncé du problème

Exercice 1

Exercice 2