Ep 21

▶ Télécharger le sujet en pdf.

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

###

Lancer Télécharger Téléverser Recharger Sauvegarder

# Mettez votre code icibksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

bksl-nldef 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-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.

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 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.

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

🐍 Script Python

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

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Noeud:bksl-nl '''bksl-nl classe implémentant un noeud d'arbre binairebksl-nl '''bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, g, v, d):bksl-nl '''bksl-nl un objet Noeud possède 3 attributs :bksl-nl - gauche : le sous-arbre gauche,bksl-nl - valeur : la valeur de l'étiquette,bksl-nl - droit : le sous-arbre droit.bksl-nl '''bksl-nl self.gauche = gbksl-nl self.valeur = vbksl-nl self.droit = dbksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl '''bksl-nl renvoie la représentation du noeud en chaine de caractèresbksl-nl '''bksl-nl return str(self.valeur)bksl-nlbksl-nl def estpy-undunepy-undfeuille(self):bksl-nl '''bksl-nl renvoie True si et seulement si le noeud est une feuillebksl-nl '''bksl-nl return self.gauche is None and self.droit is Nonebksl-nlbksl-nlbksl-nldef expressionpy-undinfixe(e):bksl-nl s = ...bksl-nl if e.gauche is not None:bksl-nl s = '(' + s + expressionpy-undinfixe(...)bksl-nl s = s + ...bksl-nl if ... is not None:bksl-nl s = s + ... + ...bksl-nl return sbksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Noeud:bksl-nl '''bksl-nl classe implémentant un noeud d'arbre binairebksl-nl '''bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, g, v, d):bksl-nl '''bksl-nl un objet Noeud possède 3 attributs :bksl-nl - gauche : le sous-arbre gauche,bksl-nl - valeur : la valeur de l'étiquette,bksl-nl - droit : le sous-arbre droit.bksl-nl '''bksl-nl self.gauche = gbksl-nl self.valeur = vbksl-nl self.droit = dbksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl '''bksl-nl renvoie la représentation du noeud en chaine de caractèresbksl-nl '''bksl-nl return str(self.valeur)bksl-nlbksl-nl def estpy-undunepy-undfeuille(self):bksl-nl '''bksl-nl renvoie True si et seulement si le noeud est une feuillebksl-nl '''bksl-nl return self.gauche is None and self.droit is Nonebksl-nlbksl-nlbksl-nldef expressionpy-undinfixe(e):bksl-nl s = ''bksl-nl if e.gauche is not None:bksl-nl s = '(' + s + expressionpy-undinfixe(e.gauche)bksl-nl s = s + str(e.valeur)bksl-nl if e.droit is not None:bksl-nl s = s + expressionpy-undinfixe(e.droit) + ')'bksl-nl return sbksl-nlbksl-nl

---

---