adplus-dvertising

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Suite de Fibonacci, solution top-down

Suite de Fibonacci, solution top-down

La suite de Fibonacci est une séquence de nombres entiers où chaque terme est la somme des deux termes précédents. Elle commence généralement avec les deux premiers termes, 0 et 1, et continue ainsi : 0, 1, 1, 2, 3, 5, 8, 13, 21, ... et ainsi de suite. La suite de Fibonacci est nommée d'après le mathématicien italien Leonardo Fibonacci, qui l'a introduite dans son livre "Liber Abaci" en 1202.

 

Solution récursive

La suite de Fibonacci peut être calculée à l'aide d'une approche récursive simple en utilisant la formule suivante :

$$F_n= \left\{ \begin{array}{ccr} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1}+F_{n-2} & sinon \\ \end{array} \right.$$

Voici un exemple d'implémentation récursive en Python :

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

n = 10
print(fibonacci_recursive(n))

Cependant, cette approche récursive simple présente un inconvénient majeur : elle effectue de nombreux calculs redondants, ce qui entraîne une complexité temporelle exponentielle (\(O(2^n)\).

 

Solution Top-down

Pour améliorer l'efficacité de l'approche récursive, nous pouvons utiliser la mémoisation. La mémoisation est une technique de programmation dynamique qui stocke les résultats des sous-problèmes dans un dictionnaire ou un tableau, évitant ainsi les calculs redondants.

Voici un exemple d'implémentation de la suite de Fibonacci avec mémoisation en Python :

def fibonacci_memoization(n, memo={}):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n not in memo:
        memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

n = 10
print(fibonacci_memoization(n))

La fonction fibonacci_memoization prend un argument n qui indique le nombre d'éléments de la séquence de Fibonacci que l'on souhaite calculer. Il y a également un argument optionnel memo qui contient les résultats précédemment calculés pour éviter de recalculer les mêmes valeurs plusieurs fois.

Le code commence par vérifier si n est 0 ou 1, auquel cas il retourne directement la valeur correspondante (0 pour n=0, 1 pour n=1).

Si n n'est pas dans le dictionnaire memo, cela signifie que nous n'avons pas encore calculé la valeur pour n et nous devons la calculer. Pour cela, nous utilisons la relation de récurrence de la séquence de Fibonacci : fib(n) = fib(n-1) + fib(n-2). Nous calculons donc les valeurs fibonacci_memoization(n-1, memo) et fibonacci_memoization(n-2, memo) en récursant sur les deux termes de la relation, en utilisant le même dictionnaire memo pour stocker les résultats intermédiaires.

Une fois que nous avons calculé la valeur pour n, nous stockons le résultat dans le dictionnaire memo pour une utilisation ultérieure et nous retournons la valeur.

En utilisant la mémoisation, la complexité temporelle est réduite à O(n), ce qui rend cette approche beaucoup plus efficace pour calculer de grands termes de la suite de Fibonacci.

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.