Fibonacci

Cours/Algorithmie/Algorithmes classiques/Fibonacci

La suite de Fibonacci est définie par l'équation de récurrence :

$$ F(n) = \begin{cases} F(n-1) + F(n-2) \text{ si }n> 2\\ F(1) = F(2) = 1 \end{cases} $$

Nous allons utiliser cette suite pour donner des techniques utiles pour l'étude d'algorithmes récursifs

Valeurs

En utilisant l'équation de récurrence, montrez que :

$$ \begin{array}{ccccc} \Omega((\sqrt{2})^n)&=&F(n)&=& \mathcal{O}(2^n) \end{array} $$

En utilisant le fait que la suite de Fibonacci est une suite récurrente linéaire, on peut même donner une valeur explicite de chaque valeur. Démontrons le :

En utilisant le fait que les deux racines du polynôme $P(X) = X^2 -X-1$ sont $\phi_+ = \frac{1 + \sqrt{5}}{2}$ et $\phi_- = \frac{1 - \sqrt{5}}{2}$, montrez que pour $n>0$ :

$$ F(n) = \frac{\phi_+^n - \phi_-^n}{\sqrt{5}} $$

Fibonacci récursif

algorithme fibonacci_rec(n: entier) → entier:
    si n ≤ 2:
        rendre 1
    rendre fibonacci_rec(n-1) + fibonacci_rec(n-2)

Montrez que le programme précédent est bien un algorithme qui calcule la valeur de Fibonacci.

Montrez que la complexité de l'algorithme fibonacci_rec(n) est en $\Omega(F(n))$.

Sa complexité est rédhibitoire.

Récursif terminal

L'algorithme récursif est sous optimal car il recalcule plein de fois la même chose. Pour calculer $F(n)$ il calcule deux fois $F(n-2)$, une fois dans la somme et une fois dans le calcul de $F(n-1)$.

Utilisez la transformation en récursion terminale pour améliorer la complexité de cet algorithme récursif.

Fibonacci Itératif

Créez un algorithme itératif calculant $F(n)$ avec une complexité de $\mathcal{O}(n)$