Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Fibonacci memoise
La suite de Fibonacci est un classique : chaque nombre est la somme des deux précédents. fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(2) = 1, fibonacci(3) = 2, fibonacci(4) = 3, fibonacci(5) = 5, etc.
Le problème de la version récursive naive, c'est qu'elle recalcule les memes valeurs des millions de fois. fibonacci(50) prendrait des milliards d'opérations.
La solution : la memoisation. C'est comme prendre des notes pendant un examen. Chaque fois que tu calcules fibonacci(n), tu notes le résultat. La prochaine fois qu'on te demande fibonacci(n), tu regardes tes notes au lieu de recalculer.
En Python, on utilise un dictionnaire memo pour stocker les résultats deja calcules.
Écris une fonction fibonacci(n, memo=None) qui calcule le n-ieme terme avec memoisation. Elle doit pouvoir calculer fibonacci(50) en moins d'une seconde.
Tests (2/4)
Cas de base
assert fibonacci(0) == 0
assert fibonacci(1) == 1
Fibonacci 10
assert fibonacci(10) == 55
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 0:
return 0
if n == 1:
return 1
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]