Q-Suite

La Q-Suite est définie ainsi :

Q(1)=1
Q(2)=1
Pour n>2, Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))

L'entrée du problème est une séquence contenant 2 valeur (i,j), avec i strictement inférieur à j. Vous devez répondre par un entier contenant la somme de tous les termes Q(i)+...+Q(j)

Le coin tuto

Bien que le calcul de Q(n) soit très facile à programmer de manière récursive, une telle fonction sera inefficace pour n assez grand. Le calcul demandé dans cet exercice peut donc prendre plusieurs minutes voire plusieurs heures, si on programme la fonction Q(n) de manière recursive.

Pour répondre en temps raisonnable, il faut donc calculer et stocker les résultats du calcul de Q(n) pour toutes les valeurs de n demandées dans l'exercice. D'autres optimisations sont possibles, mais celle-ci est suffisante pour résoudre l'exercice avec succès.