Exercices
Chapitre 2: Algorithmes de recherche
1 Recherche dans un annuaire
On suppose que l’on a un annuaire qui contient les huit milliards d’êtres humains dans l’ordre alphabétique de leurs noms, prénom, lieu de naissance et date de naissance.
Combien de comparaisons sont nécessaires pour retrouver une personne dans cet annuaire ?
2 Recherche dans un dictionnaire
La page suivante contient une liste de 336531 mots du français.
https://chrplr.github.io/openlexicon/datasets-info/Liste-de-mots-francais-Gutenberg/liste.de.mots.francais.frgut.txt
Après avoir téléchargé le fichier, vous pouvez importer les mots dans une liste avec le code python suivant.
# initialisation de la liste de mots vide
mots = []
with open('liste.de.mots.francais.frgut.txt') as f:
mots = [line.rstrip() for line in f]
# affichage du nombre de mots
len(mots) # renvoie 336531En python, le logarithme en base 2 est implémenté dans le module math.
- Implémenter l’algorithme de recherche dichotomique sur la liste
mots, et vérifier que dans le pire des cas le résultat de la recherche sera donnée en 19 tours de boucle. - Quel est le cas le plus favorable? le moins favorable?
3 Le jeu du “plus petit, plus grand”
- Écrire un programme qui joue au jeu du “plus petit-plus grand”:
- Le programme choisit un nombre au hasard entre 1 et 100,
- l’utilisateur choisit un nombre au hasard,
- l’ordinateur indique si le nombre est plus petit, plus-grand ou deviné, jusqu’à ce que l’utilisateur l’ait trouvé.
- En combien d’étapes au plus peut-on deviner le nombre:
- Si on procède au hasard?
- Si on applique la méthode de la dichotomie?
- Écrire un autre programme qui cherche à deviner le nombre par la méthode de dichotomie et qui affiche le nombre de tours utilisés.