Exercices de programmation pour classes préparatoires
Écrire une fonction fibonacci : int -> int qui renvoie le n-ième terme de la suite de Fibonacci, définie par F(0) = 0, F(1) = 1 et F(n) = F(n-1) + F(n-2) pour n ≥ 2.
La version récursive naïve est en temps exponentiel et ne permet pas de calculer fibonacci 40 en un temps raisonnable. On demande ici une implémentation efficace par mémoïsation : stocker les valeurs déjà calculées dans une Hashtbl ou un tableau, afin que chaque F(k) ne soit calculé qu'une seule fois.
La fonction doit être capable de calculer au moins fibonacci 50 en un temps négligeable.
On suppose n ≥ 0.
| Appel | Résultat attendu |
|---|---|
| fibonacci 0 | 0 |
| fibonacci 1 | 1 |
Connectez-vous pour soumettre du code.