L'algorithme d'Euclide

Exercice · OCaml (option informatique), chapitre 1 — Découvrir OCaml : expressions, valeurs et types

Énoncé

Écrire une fonction récursive pgcd calculant le PGCD de deux entiers naturels, par l'algorithme d'Euclide ( $pgcd (a, 0) = a$ et $pgcd (a, b) = pgcd (b, a mod b)$ ). La tester mentalement sur pgcd 30 12.

Corrigé

let rec pgcd a b =
  if b = 0 then a
  else pgcd b (a mod b)

Déroulé de pgcd 30 12 : $\to$ pgcd 12 6 (car $30 mod 12 = 6$ ) $\to$ pgcd 6 0 (car $12 mod 6 = 0$ ) $\to$ renvoie 6. Le cas de base b = 0 est atteint car le reste a mod b décroît strictement et reste positif : la suite des seconds arguments est une suite d'entiers naturels strictement décroissante, donc finie.

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.