1. Apprendre
    2. /
  2. Cours
    3. /
  3. Structures de données et algorithmes en Python
Connected

Exercice

Suite de Fibonacci

Dans cet exercice, vous allez implémenter la suite de Fibonacci, omniprésente dans la nature. La suite ressemble à ceci : « 0, 1, 1, 2, 3, 5, 8… ». Vous allez créer une implémentation récursive d'un algorithme qui génère cette suite.

Les deux premiers nombres sont 0 et 1, et chaque nombre suivant est la somme des deux précédents.

On peut définir cette suite de façon récursive ainsi : \(fib(n)=fib(n-1)+fib(n-2)\), avec \(fib(0)=0\) et \(fib(1)=1\), où \(n\) est la \(n^e\) position dans la suite.

À la première étape, vous coderez Fibonacci en utilisant la récursion. À la deuxième étape, vous l'améliorerez au moyen de la programmation dynamique, en enregistrant les solutions des sous-problèmes dans la variable cache.

Instructions 1/2

undefined XP
  • 1
    • Définissez le cas de base.
    • Appelez la fonction fibonacci() de façon récursive.
  • 2
    • Vérifiez si la valeur existe dans cache.
    • Enregistrez le résultat dans cache pour éviter de le recalculer plus tard.