Programmation Dynamique
La programmation dynamique est « l’art » de construire un certain état en s’appuyant sur les états précédents. Lors des calculs, on utilise souvent les valeurs déjà obtenues au cours de l’exécution. Les nombres de Fibonacci en sont un excellent exemple, car ils peuvent être calculés grâce à la programmation dynamique :
Ainsi, pour calculer
fib(2), on utilise les valeurs fib(1) et fib(0), ce qui donne fib(2) = 1. Pour obtenir la valeur suivante dans la suite de Fibonacci, on se sert de la valeur précédemment calculée : fib(3) = fib(2) + fib(1) = 1 + 1 = 2. De même, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 et fib(5) = fib(4) + fib(3) = 3 + 2 = 5, et ainsi de suite.À chaque itération, nous calculons la valeur courante de la suite de Fibonacci à partir des états précédents que nous avons déjà déterminés. On peut l’implémenter avec une liste :
n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1 (valeurs initiales)
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])Pour
n = 5, le programme affiche 5, tandis que pour n = 7, il affiche 13.Le fait de calculer de manière répétée l’état actuel (dans notre cas, le nombre de Fibonacci courant) à partir des états précédents constitue l’essence même de la programmation dynamique.
💡
La programmation dynamique est une technique qui consiste à construire l’état courant à partir des états précédents.
Défi - nombres de Tribonacci
Après avoir exploré les nombres de Fibonacci, vous vous êtes ennuyé et avez décidé de vous intéresser plutôt aux nombres de Tribonacci. Ces nombres se définissent ainsi :
Votre tâche est de déterminer le
n-ième nombre de Tribonacci.Entrée
L’entrée se compose d’un seul entier
n (1 ≤ n ≤ 30).Sortie
La sortie doit contenir le
n-ième nombre de Tribonacci.Exemples
Entrée | Sortie |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB