Ep 33
ⶠTélécharger le sujet en pdf.
EXERCICE 1âïž
Dans cet exercice, un arbre binaire de caractĂšres est stockĂ© sous la forme dâun dictionnaire oĂč les clefs sont les caractĂšres des nĆuds de lâarbre et les valeurs, pour chaque clef, la liste des caractĂšres des fils gauche et droit du nĆud.
Par exemple, lâarbre :
est stocké dans
a = {'F':['B','G'], 'B':['A','D'], 'A':['',''], 'D':['C','E'], \
'C':['',''], 'E':['',''], 'G':['','I'], 'I':['','H'], \
'H':['','']}
Ăcrire une fonction rĂ©cursive taille prenant en paramĂštres un arbre binaire arbre sous la forme dâun dictionnaire et un caractĂšre lettre qui est la valeur du sommet de lâarbre, et qui renvoie la taille de lâarbre Ă savoir le nombre total de nĆuds.
On observe que, par exemple, arbre[lettre][0], respectivement arbre[lettre][1], permet dâatteindre la clĂ© du sous-arbre gauche, respectivement droit, de lâarbre arbre de sommet lettre.
Exemple :
>>> taille(a, âFâ)
9
RĂ©ponse
Complétez le code ci-dessous
Solution
EXERCICE 2âïž
On considÚre l'algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous-tableau des éléments non rangés et on place le plus petit élément en premiÚre position de ce sous-tableau.
Exemple avec le tableau : t = [41, 55, 21, 18, 12, 6, 25]
-
Ătape 1 : on parcourt tous les Ă©lĂ©ments du tableau, on permute le plus petit Ă©lĂ©ment avec le premier. Le tableau devient
t = [6, 55, 21, 18, 12, 41, 25] -
Ătape 2 : on parcourt tous les Ă©lĂ©ments sauf le premier, on permute le plus petit Ă©lĂ©ment trouvĂ© avec le second. Le tableau devient :
t = [6, 12, 21, 18, 55, 41, 25]
Et ainsi de suite.
La code de la fonction tri_selection qui implémente cet algorithme est donné ci-dessous.
Exemple :
>>> liste = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(liste)
>>> liste
[6, 12, 18, 21, 25, 41, 55]
On rappelle que l'instruction a, b = b, a Ă©change les contenus de a et de b.
RĂ©ponse
Complétez le code ci-dessous