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

Suite de Syracuse

Programmation impérative : références et boucles · niveau 2

Énoncé

Écrire syracuse n ( $n \geq 1$ ), le nombre d'étapes pour atteindre $1$ (étape : $n \mapsto n /2$ si pair, $n \mapsto 3 n + 1$ sinon), avec une boucle while.

Corrigé

let syracuse n =
  let m = ref n and etapes = ref 0 in
  while !m <> 1 do
    if !m mod 2 = 0 then m := !m / 2
    else m := 3 * !m + 1;
    etapes := !etapes + 1
  done;
  !etapes

On itère la transformation jusqu'à atteindre 1, en comptant les étapes. Contrairement aux exemples précédents, on ne connaît aucun variant prouvant la terminaison pour tout n : c'est la conjecture de Syracuse, ouverte à ce jour. La boucle s'arrête en pratique, mais nul ne sait le démontrer en général.

Exercices semblables

PGCD impératif corrigé
Fibonacci itératif corrigé
Compter les diviseurs corrigé
Racine carrée entière corrigé
Test de primalité corrigé

Le cours du chapitre · Tous les exercices du chapitre