Exercice corrigé
Seuil et complexité pour la suite de Fibonacci
Difficile1èreMathematiquesSuites numériquesUtilisation d’algorithmes pour le calcul ou la simulation (Fibonacci, seuil, etc.)
3 questions : réponds, demande un indice si tu bloques, la correction s'affiche dès que tu as trouvé.
On souhaite savoir combien d'étapes il faut pour que la suite de Fibonacci dépasse 1000 en utilisant l'algorithme itératif (initialiser \(F_0=0, F_1=1\) puis itérer). On examine aussi le coût en additions.
Question 1
Quel est le plus petit entier \(n\) tel que \(F_n\ge1000\) ?
Question 2
En partant de i = 2 et en effectuant une addition par itération, combien d'additions sont nécessaires pour obtenir \(F_{17}\) ?
Réponds d'abord à la question précédente.
Question 3
Quelle est la complexité (ordre de grandeur) en nombre d'opérations pour calculer \(F_n\) par itération ?
Réponds d'abord à la question précédente.