InformatiqueCycle 4 · Algorithmique

Le nombre mystère

Trouve un nombre entre 1 et 100 en posant le moins de questions possible. Joue d'abord, puis regarde l'ordinateur appliquer un algorithme efficace : la recherche par dichotomie, qui coupe l'intervalle en deux à chaque essai.

Ta proposition :

Essais

Algorithme de dichotomie

Borne basse: 1
Borne haute: 100
Nombre d'essais: 0

Pourquoi c'est efficace : 100 → 50 → 25 → 13 → 7 → 4 → 2 → 1. Au plus 7 essais suffisent pour 100 nombres. Pour 1 million de nombres, 20 essais suffisent ; en testant les nombres un par un, il en faudrait jusqu'à 1 million.

Séquence clés en main : cette animation fait partie du Pack Informatique, avec fiches élèves, corrigés et évaluation.

Pour l'enseignant

Objectifs

Formaliser une stratégie sous forme d'algorithme.
Comparer l'efficacité de deux méthodes (recherche une par une / dichotomie).
Utiliser variables, boucle et condition.

Pistes

Programmer le jeu dans Scratch : l'ordinateur choisit, l'élève devine.
Puis inverser les rôles et programmer la dichotomie.
Lien avec la recherche d'un mot dans un dictionnaire.

Repère

Nombre maximal d'essais : le plus petit n tel que 2ⁿ ≥ N (N = taille de l'intervalle).