Sujet n°3

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

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 assez petites 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() 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] 

>>> delta([]) 
AssertionError: Tableau vide !

Une solution

def delta(tab):
    """
    tab - list, tableau non vide de nombres entiers
    Sortie: list - tableau dont chaque élément est la différence
            entre deux éléments consécutifs de tab, dans l'ordre
    """
    assert len(tab) > 0, 'Tableau vide !'
    diff = [tab[0]]
    for i in range(1, len(tab)):
        diff.append(tab[i] - tab[i-1])
    return diff



if __name__ == '__main__':
    from random import randint
    print(delta([1000, 800, 802, 1000, 1003]) == [1000, -200, 2, 198, 3])

    print(delta([42]) == [42])

    print(delta([729, 183, 672, 134, 65, 451, 968, 277]) == [729, -546, 489, -538, -69, 386, 517, -691])

    t = [randint(0, 1000) for _ in range(8)]
    print(t)
    print(delta(t))

    delta([])

Exercice n°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.

En effectuant un parcours en profondeur infixe de l’arbre binaire ci-contre, on retrouve l’expression notée habituellement : 3 × (8 + 7) – (2 + 1)

La classe Noeud ci-après permet d’implémenter une structure d’arbre binaire.

Compléter la fonction récursive expression_infixe() qui prend en paramètre un objet de la classe Noeud et qui renvoie l’expression arithmétique représentée par l’arbre binaire passé en paramètre, sous forme d’une chaîne de caractères contenant des parenthèses.

Exemple

Résultat attendu avec l’arbre ci-dessus :

>>> e = Noeud(Noeud(Noeud(None, 3, None), '*', Noeud(Noeud(None, 8, None),
'+', Noeud(None, 7, None))), '-', Noeud(Noeud(None, 2, None), '+', 
Noeud(None, 1, None)))

>>> expression_infixe(e)
'((3*(8+7))-(2+1))'

class Noeud:
    '''
    Classe implémentant un Noeud d'arbre binaire disposant
    de 3 attributs :
    - valeur : la valeur de l'étiquette,
    - gauche : le sous-arbre gauche.
    - droit : le sous-arbre droit.
    '''
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit = d

    def __str__(self):
        return str(self.valeur)

    def est_une_feuille(self):
        '''Renvoie True si et seulement si le noeud est une
           feuille'''
        return self.gauche is None and self.droit is None

def expression_infixe(e):
    s = ...
    if e.gauche is not None:
        s = '(' + s + expression_infixe(...)
    s = s + ...
    if ... is not None:
        s = s + ... + ...
    return s

Commentaire sur le code original

1. Pour télécharger l'original du fichier à compléter, cliquer ici.

2. Le code original comportait un test en lignes 29 et 30 nécessaire au renvoi de valeur :

       if ... :
           return s
   

   On peut s'interroger sur cette condition puisque l'énoncé ne précise rien. Dans le doute, un « if True : » conviendrait.

Une solution

class Noeud:
    '''
    Classe implémentant un noeud d'arbre binaire disposant de 3
    attributs :
    - valeur : la valeur de l'étiquette,
    - gauche : le sous-arbre gauche.
    - droit : le sous-arbre droit.
    '''
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit = d

    def __str__(self):
        return str(self.valeur)

    def est_une_feuille(self):
        '''Renvoie True si et seulement si le noeud est une feuille'''
        return self.gauche is None and self.droit is None


def expression_infixe(e):
    s = ''
    if e.gauche is not None:
        s = '(' + s + expression_infixe(e.gauche)
    s = s + str(e)
    if e.droit is not None:
        s = s + expression_infixe(e.droit) + ')'
    return s




if __name__ == '__main__':
    e = Noeud(Noeud(Noeud(None, 3, None), '*', Noeud(Noeud(None, 8, None),
        '+', Noeud(None, 7, None))), '-', Noeud(Noeud(None, 2, None), '+',
        Noeud(None, 1, None)))
    print(expression_infixe(e) == '((3*(8+7))-(2+1))')

    e = Noeud(Noeud(Noeud(None, 5, None), '-', Noeud(None, 2, None)), '*',  Noeud(Noeud(None, 4, None), '-', Noeud(Noeud(None, 3, None), '+', Noeud(None, 1, None))))
    print(expression_infixe(e) == '((5-2)*(4-(3+1)))')