PGCD impératif

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

Énoncé

Écrire pgcd avec une boucle while, et donner son variant.

Corrigé

let pgcd a b =
  let x = ref a and y = ref b in
  while !y <> 0 do
    let r = !x mod !y in
    x := !y;
    y := r
  done;
  !x

Variant : !y. Il reste positif tant que la condition !y <> 0 (avec !y initialement $\geq 0$ ) tient, et il décroît strictement car le nouveau !y vaut !x mod !y $<! y$ . La boucle se termine donc.

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.