informatique (tronc commun des prépas scientifiques) · Chapitre 5 · Application directe du cours
La racine carrée entière
Algorithmes dichotomiques · niveau 1 (application)
Énoncé
Écrire une fonction racine_entiere(n) qui calcule (le plus grand entier tel que ) par dichotomie sur en temps sans utiliser de nombres flottants.
Corrigé
On cherche la valeur frontière dans l'intervalle d'entiers :
def racine_entiere(n: int) -> int:
"""Précondition : n >= 0."""
g, d = 0, n
while g < d:
# Invariant : g**2 <= n et (d+1)**2 > n
# Arrondi du milieu vers le haut pour éviter une boucle infinie quand d - g = 1
m = (g + d + 1) // 2
if m * m <= n:
g = m # La réponse est dans [m, d]
else:
d = m - 1 # La réponse est dans [g, m-1]
return gVariant : La quantité décroît strictement à chaque étape grâce à l'arrondi supérieur du milieu.