\documentclass[a4paper, 12pt]{article}

\usepackage{amsmath, amssymb}


%%%%%%%% PDF %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{ifpdf}

\ifpdf
  \usepackage[pdftex]{color,graphicx}
  \usepackage[pdftex ,colorlinks=true,
        urlcolor=blue,
        citecolor=blue,
        pdfstartview=FitH]{hyperref} 
\else
  \usepackage[dvips]{color}
  \usepackage[pagebackref,%
              colorlinks=true,urlcolor=blue,citecolor=blue]{hyperref}
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Algorithmes Additifs et Suites de Fibonacci.\\
}
\author{TP-2, Module I41, Licence Informatique\\
universit\'e du sud Toulon-Var}

\date{Mars 2007}

%%%%%%%% DEFINITION %%%%%%%%%%%%%%%%%%%%%%%%
\def\terminal#1{
$$
\fbox{
   \vbox{\hsize=65mm 
   \noindent
   \texttt{#1}
   }
  }
$$
}

\newtheorem{exercice}{Exercice}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

La suite de Fibonnacci $F_n$ est la suite d'entiers positifs
d\'efinie par les relations :
$$
F_0 = 0,\quad F_1 = 1,\qquad\forall n\geq 2,\  F_n = F_{n-1} + F_{n-2}.
$$
Nous avons vu en cours 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$, par~: 

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

En particulier, $F_n$ cro\^{\i}t exponentiellement
$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

\section{Fibonacci r\'ecursif}

\begin{enumerate}
  \item Implanter une fonction r\'ecursive \texttt{long long fibrec(int n)} pourcalculer le $n$-eme terme de la suite de Fibonacci.
  \item Soit $T(n)$ le temps de calcul. Faire des mesures de temps de calcul pour d\'eterminer les meilleures constantes $A$ et $B$ tel que : 
$$T(n) = A B^n.$$
\end{enumerate}

\section{Fibonacci it\'eratif}

\begin{enumerate}
  \item Implanter une fonction it\'erative \texttt{long long fibiter(int n)} pour calculer le $n$-eme terme de la suite de Fibonacci.
  \item Quelle est la forme du temps de calcul ?
\item D\'eterminer empiriquement la plus grande valeur de $n$ pour laquelle
votre fonction renvoie un r\'esultat correct.
\item D\'eterminer empiriquement $\lim_{n\to\infty} \frac{F_{n+1}}{F_n}$.
\item Expliquer les r\'esultats deux des questions pr\'ec\'edentes.

\end{enumerate}

\section{Fibonacci sur les grands nombres}


La figure (\ref{FIB}) propose un extrait de programme en
langage C pour calculer les termes de rang \'elev\'e de la 
suite de Fibonacci, les nombres \'etant repr\'esent\'es par
des pointeurs sur des entiers.


\begin{enumerate}
  \item Implanter la fonction \texttt{int digits(int n)} qui d\'etermine 
la taille d\'ecimale de $F_n$. 
  \item Implanter la fonction \texttt{void add( int *s, int* a, int* b)} 
qui calcule dans $s$ la somme des nombres $a$ et $b$.  
 \item Implanter la fonction \texttt{void copier( int *d, int* s)} qui
calcule dans $d$ le nombre $s$.
\item V\'efifier le bon fonctionnement de votre programme en calculant 
$F_{1000}$.
\item D\'eterminer une expression du temps de calcul en fonction de $n$.
\end{enumerate}


\setbox100=\vtop{%%
\hsize=50mm
\begin{verbatim}
int TAILLE;

int main( int argc, char *argv[])
{ int  n, *a, *b, *c;
       n = atoi( argv[1 ]);
  TAILLE = nbdigits( n );
  a = ( int* ) calloc( TAILLE, sizeof(int) );
  b = ( int* ) calloc( TAILLE, sizeof(int) ); 
  c = ( int* ) calloc( TAILLE, sizeof(int) );
  b[0] = 1;
  n = n - 2;
  while ( n > 0 ) {
    add( c, a, b );
    copier( a, b );
    copier( b, c )
    n = n - 1;
  }
  imprimer( b );
  free(a); free(b); free(c);
  return 0;
}

\end{verbatim}
}
\begin{figure}[h]
\hbox to 5 truecm{\box100}
\caption{\label{FIB}morceau de programme}
\end{figure}


\end{document}
