Deviner un mot par dichotomie
Exercice supplémentaire · niveau 3 (difficile) · sciences numériques et technologie (seconde), chapitre 7 — Projets et mini-jeux · Le nombre mystère
Énoncé
La dichotomie ne sert pas qu'aux nombres. Écrire une fonction qui trouve un mot dans une liste triée de mots, en divisant l'intervalle par deux, et compter les comparaisons sur une liste de mots.
Corrigé
def cherche(mots, cible):
bas, haut, comparaisons = 0, len(mots) - 1, 0
while bas <= haut:
milieu = (bas + haut) // 2
comparaisons = comparaisons + 1
if mots[milieu] < cible:
bas = milieu + 1
elif mots[milieu] > cible:
haut = milieu - 1
else:
return milieu, comparaisons
return -1, comparaisons
mots = ["mot%05d" % i for i in range(10000)]
print(cherche(mots, "mot07321")) # (7321, 14 ou moins)Quatorze comparaisons au pire pour dix mille mots, contre dix mille pour un parcours séquentiel.
La condition indispensable est que la liste soit TRIÉE : c'est ce qui permet d'éliminer une moitié sur une seule comparaison. Sur une liste quelconque, la méthode renvoie n'importe quoi sans le signaler — un des pièges classiques, car le programme ne plante pas. C'est aussi ce que fait un dictionnaire papier quand on l'ouvre au milieu.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.