Racine carrée entière

Exercice · OCaml (option informatique), chapitre 4 — Programmation impérative : références et boucles

Énoncé

Écrire racine n ( $n \geq 0$ ) renvoyant le plus grand entier $r$ tel que $r^{2} \leq n$ , avec une boucle while, et prouver sa terminaison par un variant.

Corrigé

let racine n =
  let r = ref 0 in
  while (!r + 1) * (!r + 1) <= n do
    r := !r + 1
  done;
  !r

On incrémente r tant que (r+1)^2 ne dépasse pas n. À la sortie, r^2 <= n < (r+1)^2 : c'est bien la partie entière de $n$ . Variant : n - !r <em> !r, entier positif tant que la boucle tourne, qui décroît strictement (!r croît de $1$ ). (racine 10 $= 3$ , car $3^{2} = 9 \leq 10 < 16 = 4^{2}$ .)*

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.