NSI (terminale) · Chapitre 7 · Exercice d'entraînement

La suite de Tribonacci

La programmation dynamique · Mémoïsation et approche ascendante · niveau 1 (application)

Énoncé

La suite de Tribonacci.

La suite de Tribonacci est définie par $T_{0} = 0$ , $T_{1} = 0$ , $T_{2} = 1$ et, pour $n \geq 3$ , $T_{n} = T_{n - 1} + T_{n - 2} + T_{n - 3}$ .

Calculer à la main $T_{3}$ à $T_{10}$ .
Écrire une version récursive mémoïsée trib_memo(n, memo) et une version ascendante trib_asc(n).
Pourquoi la version récursive naïve serait-elle très lente ? Quel est le coût des deux versions écrites ?

Un exercice à chercher : son corrigé n'est pas publié. Sur Adloun, le tuteur guide par questions, sans donner la réponse.