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

Fibonacci itératif

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

Énoncé

Écrire fibo n ( $n \geq 0$ ) en $Θ (n)$ avec deux références, et expliquer l'avantage sur la version doublement récursive du chapitre 3.

Corrigé

let fibo n =
  let a = ref 0 and b = ref 1 in
  for _i = 1 to n do
    let s = !a + !b in
    a := !b;
    b := s
  done;
  !a

On fait avancer une « fenêtre » de deux termes consécutifs. fibo 0 $= 0$ , fibo 1 $= 1$ , fibo 6 $= 8$ . Coût $Θ (n)$ : chaque terme est calculé une fois, là où la définition récursive naïve $u_{n} = u_{n - 1} + u_{n - 2}$ recalcule exponentiellement les mêmes valeurs.

Exercices semblables

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

Le cours du chapitre · Tous les exercices du chapitre