La racine carrée entière

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques

Énoncé

Écrire une fonction racine_entiere(n) qui calcule $⌊ n ⌋$ (le plus grand entier $k$ tel que $k^{2} \leq n$ ) par dichotomie sur $k$ en temps $O (lo g n)$ sans utiliser de nombres flottants.

Corrigé

On cherche la valeur frontière dans l'intervalle d'entiers $[[0, n]]$ :

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 g

Variant : La quantité $d - g$ décroît strictement à chaque étape grâce à l'arrondi supérieur du milieu.

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.