Retour à la page précédente

1. Elle donne une première façon de programmer le calcul du Nième terme.
   Par exemple en Javascript :
   
   function FiboDef(n)
   {if (n==0) {return 0;}
   else {if (n==1) {return 1;}
   ........ else {return (FiboDef(n-1) + FiboDef(n-2));} } }
   

2. Vous pouvez donc obtenir les valeurs désirées.

   n F(n)

   Mais vous constatez vite que le calcul devient lent. Essayez de programmer le même algorithme dans votre langage favori. Vous devriez constater le même ralentissement, peut être pas exactement pour les mêmes valeurs de n.
   
3. Pourquoi ce ralentissement ? A cause de la complexité de l'algorithme. Essayons de la visualiser.
   Ajoutez à votre programme l'affichage des appels, et un nombre de tirets indiquant la profondeur des appels, comme dans l'exemple ci-dessous.
   
   
   
   
   n

 

4. Une autre façon de faire : calculer le nombre d'additions A(n) nécessaires pour calculer FiboDef(n). Solution.
   
   

Fibonacci linéaire
Revenons sur la définition de la suite. Chaque terme est la somme des deux précédents.

Donc ............. le terme qui suit 3 ; 5 est 8. Le suivant 13, ensuite 21.

..................... Autrement dit, le terme qui suit 5 ; 8 est 13. Le suivant 21.

................................................................ Le terme qui suit 8 ; 13 est 21.

Une façon plus mathématique d'écrire cela :

Cette écriture devrait vous mener tout droit à la programmation d'une fonction g(n, b, a) en fonction de g(n-1, ?, ?). N'oubliez pas la condition d'arrêt Indication Solution.

Retour à la page précédente