Fibonacci

 

 

  1. Si A(n) est le nombre d'additions nécessaires pour calculer FiboDef(n), on a : A(n) = A(n-1) + A(n-2) + 1
    ce qui peut se programmer.

    2. n F(n) Nombre d'additions
  2. Une autre façon de faire est de repérer le lien entre les deux suites A(n) et F(n).

    Un petit tableau

    n 0 1 2 3 4 5 6
    A(n) 0 0 1 2 4 7 ...
    F(n) 0 1 1 2 3 5 ...

    fait apparaître que A(n) = F(n+1) - 1. Reste à le démontrer.



    Retour à la page précédente