\newpage
\section{Suite de Fibonacci}
\contribution{Ph. langevin}{21 Octobre 2009}
La suite de Fibonacci $F_n$ est la suite d'entiers positifs
d\'efinie par la relation de r\'ecurrence d'ordre deux~:

\begin{equation}
F_0 = 0,\quad F_1 = 1,\qquad\forall n\geq 2,\  F_n = F_{n-1} + F_{n-2}.
\end{equation}

On d\'emontre sans difficult\'e que $F_n$ s'exprime \`a partir
des deux racines l'\'equation $X^2=X+1$ qui sont $\phi\approx 1.618$ 
et $\hat\phi\approx -0.6$ : 

\begin{equation}
F_n = \frac 1{\sqrt{5}}(\phi^n - \hat\phi^n)
\end{equation}

En particulier, $F_n$ cro\^{\i}t exponentiellement, plus
pr\'ecis\'ement, $F_n$ est \'equivalent \`a $\frac 1{\sqrt{5}} \phi^n$
au voisinage de l'infini. Par exemple $F_{10} = 55$,
$$F_{100}=354224848179261915075$$ et $F_{1000}$ est un nombre de 289 
chiffres d\'ecimaux : 
43 466 557 686 937 456 435 688 527 675 040 625 802 564 660 517 371 
780 402 481 729 089 536
555 417 949 051 890 403 879 840 079 255 169 295 922 593 080 322 634 
775 209 689 623 239 873 322
471 161 642 996 440 906 533 187 938 298 969 649 928 516 003 704 476 
137 795 166 849 228 875

\begin{multicols}{2}
\begin{lstlisting}[language=palgo]
FibRec( n : indice )
debut
   si ( n <= 1 ) alors
    retourner n
   fsi
   retourner
      Fibrec(n-1) + Fibrec(n-2)
fin
\end{lstlisting}
\columnbreak
La m\'ethode r\'ecursive consiste \`a appliquer d\'efinition r\'ecursive. Il 
s'agit d'une approche na\"ive (aucun effort!). L'implantation requiert un langage
r\'ecursif, c'est le cas de la majorit\'e des langages. Si nous notons $R(n)$ le nombre
d'\'etapes pour calculer $F_n$ alors $T( 0 ) = 1$, $T( 1 ) = 1$, et  pour tout
$n\geq 2$ : 
$$
 T(n) = T(n-1) + T(n-2).
$$ 
Le temps de calcul d'une implantation sera proportionnel \`a $F_{n+1}$, il
est \emph{exponentiel} en $n$.
\end{multicols}


\begin{multicols}{2}
\begin{lstlisting}[language=palgo]
FibIter( n : indice )
variable x, y, t: nombre
debut
   x := 0
   y := 1
   tantque ( n > 0 )
       t := x + y
       x := y
       y := t
     n := n-1
   ftq
   retourner x
fin
\end{lstlisting}
\columnbreak
L'approche it\'erative demande plus de travail de la part
du concepteur. Le nombre
d'it\'erations effectu\'ees pour calculer $F_n$ est 
proportionnel \`a $n$. Le temps de cacul d'une implantation
sera de la forme $An+B$, on dit qu'il est \emph{lin\'eaire}.

\vspace{5mm}
\begin{tabular}{|c|r|r|r|r|}
\hline
$n$    &10 &20 &40 &80\\
\hline
$R(n)$ &$0.00001$ &$0.0018$ &$57$       & 2000 an !\\
$I(n)$ &$0.00001$ &$0.00002$ &$0.00004$ &$0.00008$\\
\hline
\end{tabular}
\vspace{5mm}

Le tableau ci-dessus montre qu'il ne sera pas possible
de calculer $F_{80}$ par la m\'ethode r\'ecursive au 
cours d'une s\'eance de travaux-pratiques\ldots

\end{multicols}