OCaml (option informatique) · Chapitre 4 · Exercice de TD

Racine carrée entière

Programmation impérative : références et boucles · niveau 3 (difficile)

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

Exercices semblables

Fibonacci itératif corrigé
Compter les diviseurs corrigé
Suite de Syracuse corrigé
Test de primalité corrigé
Partage d'une référence (aliasing) corrigé

Le cours du chapitre · Tous les exercices du chapitre