Compétences évaluées |
---|
Concevoir des solutions algorithmiques |
Traduire un algorithme dans un langage de programmation |
Tous les TP seront notés (barème indicatif).
- Tout TP non rendu avant la fin de la séance sera noté zéro.
- Veuillez mettre clairement vos noms sur votre code source ou noms de fichiers.
Arbres binaires de recherche¶
Recherche dichotomique (10 points)¶
Lorsque l'on a un tableau trié et que l'on cherche une valeur, on peut utiliser la recherche dichotomique pour trouver efficacement (c'est à dire rapidement) cet élément.
Pour cela on va découper le tabeau en deux à chaque fois et regarder si la valeur recherchée est inférieure ou supérieure à la valeur au milieu du tableau.
Dans le code ci-dessous on renvoie True
si la valeur recherchée est bien dans le tableau et False
sinon.
Par exemple si on cherche la valeur 4 avec le tableau suivant :
On rappelle que // est l'opérateur de la division entière.
L'exécution de la fonction sera :
Etape 1
-------
bas = 0
haut = 3
milieu = (0 + 3) // 2 = 1
- Le milieu est positionné à la valeur 2, car cela correspond à l'indice 1 du tableau.
- 2 est plus petit que 4, donc on sait que 4 se trouve à droite du tableau.
Etape 2
-------
bas = milieu + 1 = 1 + 1 = 2
haut = 3
milieu = (2 + 3) // 2 = 2
- Le milieu est positionné à la valeur 3, car cela correspond à l'indice 2 du tableau.
- 3 est plus petit que 4, donc on sait que 4 se trouve à droite du tableau.
Etape 3
-------
bas = milieu + 1 = 2 + 1 = 3
haut = 3
milieu = (3 + 3) // 2 = 3
- Le milieu est positionné à la valeur 4, la fonction retourne True.
- Complétez le code suivant :
def recherche_dichotomique(tableau, valeur_recherchee, bas, haut):
if bas > haut:
return False
else:
milieu = #COMPLETER_ICI#
if valeur_recherchee == tableau[milieu]:
return #COMPLETER_ICI#
# La valeur recherchée est à droite
elif valeur_recherchee > tableau[milieu]:
return recherche_dichotomique(tableau, #COMPLETER_ICI#, #COMPLETER_ICI# + 1, haut)
else:
# La valeur recherchée est à gauche
return recherche_dichotomique(tableau, #COMPLETER_ICI# , #COMPLETER_ICI#, milieu - 1)
tableau = [3, 4, 5, 6, 7, 18, 19]
valeur_recherchee = 19
result = recherche_dichotomique(tableau, valeur_recherchee, 0, len(array) - 1)
Exercice 2 (10 points)¶
Soit la classe suivante qui nous sert à représenter un noeud d'un arbre binaire de recherche.
class Noeud():
def __init__(self, v):
self.#COMPLETER# = None
self.ad = None
self.v = v
def insere(self, v):
n = self
est_insere = #Completer#
while not est_insere :
if v == n.v:
est_insere = True
elif v < n.v:
if n.ag != None:
n = n.ag
else:
n.ag = Noeud(v)
est_insere = #Completer#
else:
if n.ad != None:
n = n.ad
else:
n.ad = Noeud(v)
est_insere = #Completer#
def #COMPLETER#(self, vals):
for v in #COMPLETER#:
self.insere(v)
def recherche(#COMPLETER#):
if v == self.v:
return #COMPLETER#
elif #COMPLETER:
if self.ag is not None:
return self.#COMPLETER#.recherche(v)
else:
return False
elif #COMPLETER:
if self.ad is not None:
return self.#COMPLETER#.recherche(v)
else:
return False
racine = Noeud(18)
racine.insere_toutes_valeurs([12, 13, 15])
-
Complétez la méthode
recherche(self, v)
qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l’arbre (c'est à dire si la valeur appartient à l'arbre), False sinon. -
Ajouter deux assertions qui testent que la fonction
recherche
renvoie bien le bon résultat (cas où la valeur appartient à l'arbre et cas où la valeur n'appartient pas à l'arbre).