Fibonacci et compagnie – Qualification 2006

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

CONTRAINTES

• n \<= 5000, m \< n
• u(n) \< 1000000000

ENTREE

• La première ligne de l'entrée contient deux entiers : n et m, séparés par une espace.

SORTIE

La sortie contient une unique ligne : l'entier retourné par votre fonction.