C16.3 : Suite de Fibonacci
Rappel sur la suite de Fibonacci
La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Le terme d'indice 0 est 0 et le terme d'indice 1 et 1.
Ainsi, les premiers termes de la suite sont : 0, 1, 1, 2, 3, 5, 8, 13, 21...
Programmation de la suite de Fibonacci
Programmation récursive
1) Écrire une fonction fibo_rec(n) qui prend un nombre entier n en paramètre et renvoie la valeur du nième terme de la suite de Fibonacci.
2) Construire, sous la forme d'un arbre, la pile des appels successifs à la fonction.
3) Pourquoi peut-on affirmer que cet algorithme n'est pas optimal ?
Programmation récursive dynamique, méthode descendante (top-down)
Ici, on s'appuiera sur le raisonnement récursif précédent, tout en utilisant un dictionnaire dont les clés sont les indices des termes de la suite et les valeurs, les valeurs des termes de la suite.
La fonction fibo_dyn_desc(n, dico) aura donc deux paramètres, l'indice du terme recherché et le dictionnaire des termes déjà calculés.
1) Écrire le code de la fonction.
2) Quel est le coût de cet algorithme ?
Programmation dynamique itérative, méthode ascendante (bottom-up)
Ici, on calcul les termes de la suite itérativement de 0 à n en stockant les valeurs dans une liste.
1) Écrire la fonction fibo_dyn_asc(n) qui prend un nombre entier n en paramètre et renvoie la valeur du nième terme de la suite.
2) Quel est le coût de cet algorithme ?