NSI (terminale) · Chapitre 6 · Exercice de TD

Racine carrée entière par dichotomie

Diviser pour régner · niveau 2

É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)$ .

100 % gratuit

Essaie le suivant avec le tuteur

Faire l'exercice suivant avec le tuteur

Sans compte : le cours, le premier QCM, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant avec le tuteur →