Sujet n°21
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 plus petit, nécessitant donc
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]
Une solution
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 | def delta(liste):
"""
liste - 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 liste, dans l'ordre
"""
assert len(liste) > 0, 'Tableau vide !'
diff = [liste[0]]
for i in range(1, len(liste)):
diff.append(liste[i] - liste[i-1])
return diff
if __name__ == '__main__':
# Exemples de l'énoncé
print(delta([1000, 800, 802, 1000, 1003]) == [1000, -200, 2, 198, 3])
print(delta([42]) == [42])
# Exemples supplémentaires
from random import randint
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)]
rep = [t[0]]
print(delta(t) == rep + [t[i]-t[i-1] for i in range(1, len(t))])
|
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 parcourant en profondeur infixe 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))'
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
28
29
30
31
32
33
34
35
36
37 | class Noeud:
'''
classe implémentant un noeud d'arbre binaire
'''
def __init__(self, g, v, d):
'''
un objet Noeud possède 3 attributs :
- gauche : le sous-arbre gauche,
- valeur : la valeur de l'étiquette,
- droit : le sous-arbre droit.
'''
self.gauche = g
self.valeur = v
self.droit = d
def __str__(self):
'''
renvoie la représentation du noeud en chaine de caractères
'''
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
Pour télécharger l'original du fichier à compléter,
cliquer ici.
Une solution
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | class Noeud:
'''
classe implémentant un noeud d'arbre binaire
'''
def __init__(self, g, v, d):
'''
un objet Noeud possède 3 attributs :
- gauche : le sous-arbre gauche,
- valeur : la valeur de l'étiquette,
- droit : le sous-arbre droit.
'''
self.gauche = g
self.valeur = v
self.droit = d
def __str__(self):
'''
renvoie la représentation du noeud en chaine de caractères
'''
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__':
# Exemple de l'énoncé
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))')
# Exemple supplémentaire
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)))')
|