Exercices

Chapitre 4: Recherche dichotomique

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 nom, prénom, lieu de naissance et date de naissance.

Combien de comparaisons sont nécessaires pour retrouver une personne dans cet annuaire ?

Le jeu du "plus petit, plus grand"

  1. Écrire un programme qui joue au jeu du "plus petit-plus grand":
  2. Le programme choisit un nombre au hasard entre 1 et 100,
  3. l'utilisateur choisit un nombre au hasard,
  4. l'ordinateur indique si le nombre est plus petit, plus-grand ou deviné, jusqu'à ce que l'utilisateur l'ait trouvé.
  5. En combien d'étapes au plus peut-on deviner le nombre:
  6. Si on procède au hasard?
  7. Si on applique la méthode de la dichotomie?
  8. Écrire un autre programme qui cherche à deviner le nombre par la méthode de dichotomie et qui affiche le nombre de tours utilisés.

Informatique et sciences du numérique Spécialité ISN en terminale S - Avec des exercices corrigés et des idées de projets par Gilles Dowek