Racine carrée entière par dichotomie

Exercice de TD · niveau 2 · NSI (terminale), chapitre 6 — Diviser pour régner

Énoncé

Racine carrée entière par dichotomie.

Calculer la partie entière de $n$ pour un entier $n \geq 0$ sans utiliser math.sqrt, par recherche dichotomique sur le résultat.

Corrigé

on cherche le plus grand entier $r$ tel que $r^{2} \leq n$ .


def racine_entiere(n):
    g, d = 0, n
    res = 0
    while g <= d:
        m = (g + d) // 2
        if m * m <= n:
            res = m          # candidat valable, on tente plus grand
            g = m + 1
        else:
            d = m - 1
    return res

La complexité est $O (lo g n)$ .

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.