DIFFICULTE
LIMITE DE MEMOIRE
2000 ko
LIMITE DE TEMPS
250 ms
ENONCE
La suite de Fibonacci est définie par :
u(0) = 1
u(1) = 1
u(n) = u(n-1) + u(n-2)
On souhaite généraliser cette suite.
M étant donné, on pose :
u(n) = 1 si n < m,
u(n) = u(n-1) + u(n-m) sinon
Ainsi, on retrouve la suite de Fibonacci en utilisant m = 2. Vous devez écrire une fonction qui prend en arguments n et m et qui renvoie u(n).
Exemple avec m = 3 :
u(30) = u(29) + u(27) = ... = 58425
- n <= 5000, m < n
- u(n) < 1000000000
- La première ligne de l'entrée contient deux entiers : n et m, séparés par une espace.
La sortie contient une unique ligne : l'entier retourné par votre fonction.
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
30 3 |
58425 |
