La dichotomie

Exercice supplémentaire · niveau 3 (difficile) · sciences numériques et technologie (seconde), chapitre 4 — Les boucles · La boucle non bornée : while

Énoncé

On cherche $2$ en encadrant : on part de $a = 1$ et $b = 2$ , on calcule le milieu $m$ , et l'on remplace $a$ ou $b$ par $m$ selon que $m^{2}$ est inférieur ou supérieur à $2$ . Écrire le programme qui s'arrête quand $b - a < 1 0^{- 6}$ , et compter les tours.

Corrigé

a = 1
b = 2
tours = 0
while b - a > 1e-6:
    m = (a + b) / 2
    if m * m < 2:
        a = m
    else:
        b = m
    tours = tours + 1
print(a, tours)   # 1.4142131... en 20 tours

Vingt tours suffisent pour six décimales, car la largeur de l'intervalle est divisée par deux à chaque étape : après $k$ tours elle vaut $2^{- k}$ , et $2^{- 20} \approx 1 0^{- 6}$ .

C'est spectaculairement plus efficace qu'un balayage : avancer par pas de $1 0^{- 6}$ demanderait un million de tours pour le même résultat. Chaque tour élimine la moitié des candidats restants — c'est le principe de la dichotomie, que l'on retrouve dans la recherche d'un mot dans un dictionnaire.

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.