Sujet n°25
Sujet original
Pour télécharger l'énoncé original, cliquer ici.
Exercice n°1
Écrire une fonction enumere qui prend en paramètre une liste L et renvoie un
dictionnaire d dont les clés sont les éléments de L avec pour valeur associée la liste des
indices de l’élément dans la liste L.
Commentaires
Ici, le mot « liste » est à comprendre dans le sens
« liste Python » (c'est-à-dire tableau) plutôt que
dans le sens du type abstrait de données liste
étudié en Terminale.
Exemple
>>> enumere([1, 1, 2, 3, 2, 1])
{1: [0, 1, 5], 2: [2, 4], 3: [3]}
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 | def enumere(L):
"""
L - list
Sortie: dict, dictionnaire qui, à chaque élément de L,
associe le tableau des indice où trouver cet élément dans L
"""
d = dict()
for i in range(len(L)):
if L[i] in d.keys():
d[L[i]].append(i)
else:
d[L[i]] = [i]
return d
if __name__ == '__main__':
# Exemple de l'énoncé
print(enumere([1, 1, 2, 3, 2, 1]) == {1: [0, 1, 5], 2: [2, 4], 3: [3]})
# Exemples supplémentaires
print(enumere([1, 1, 0, 0, 0, 1, 1]) == {0: [2, 3, 4], 1: [0, 1, 5, 6]})
print(enumere([0, 1]) == {0: [0], 1: [1]})
print(enumere([1, 0]) == {0: [1], 1: [0]})
|
Exercice n°2
Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.
Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.
1
2
3
4
5
6
7
8
9
10
11
12 | class Arbre:
def __init__(self, etiquette):
self.v = etiquette
self.fg = None
self.fd = None
def parcours(arbre, liste):
if arbre != None:
parcours(arbre.fg, liste)
liste.append(arbre.v)
parcours(arbre.fd, liste)
return liste
|
La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre
implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir
d’une liste vide passée en argument.
Compléter le code de la fonction insere qui insère un nœud d’étiquette cle en feuille de
l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon que
l’arbre ainsi complété soit encore un arbre binaire de recherche.
Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement
des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci-
dessous :
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | def insere(arbre, cle):
""" arbre est une instance de la classe Arbre qui implémente
un arbre binaire de recherche.
"""
if ...:
if ...:
insere(arbre.fg, cle)
else:
arbre.fg = Arbre(cle)
else:
if ...:
insere(arbre.fd, cle)
else:
arbre.fd = Arbre(cle)
|
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
50
51 | class Arbre:
def __init__(self, etiquette):
self.v = etiquette
self.fg = None
self.fd = None
def parcours(arbre, liste):
if arbre != None:
parcours(arbre.fg, liste)
liste.append(arbre.v)
parcours(arbre.fd, liste)
return liste
def insere(arbre, cle):
""" arbre est une instance de la classe Arbre qui implémente
un arbre binaire de recherche.
"""
if cle < arbre.v:
if arbre.fg is not None:
insere(arbre.fg, cle)
else:
arbre.fg = Arbre(cle)
else:
if arbre.fd is not None:
insere(arbre.fd, cle)
else:
arbre.fd = Arbre(cle)
if __name__ == '__main__':
# Exemple de l'énoncé
a = Arbre(5)
a.fg = Arbre(2)
a.fg.fd = Arbre(3)
a.fd = Arbre(7)
insere(a, 1)
insere(a, 4)
insere(a, 6)
insere(a, 8)
print(parcours(a, []) == [1, 2, 3, 4, 5, 6, 7, 8])
# Exemple supplémentaire
a = Arbre(8)
a.fg = Arbre(2)
a.fg.fd = Arbre(6)
a.fd = Arbre(9)
for i in range(4, 15, 3):
insere(a, i)
print(parcours(a, []) == [2, 4, 6, 7, 8, 9, 10, 13])
|