\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{Agorithme Euclidien}

\author{TP-4, Module I41, Licence Informatique\\
universit\'e du sud Toulon-Var}

\date{Avril 2007}
%%%%%%%% DEFINITION %%%%%%%%%%%%%%%%%%%%%%%%
\def\terminal#1{
$$
\fbox{
   \vbox{\hsize=65mm 
   \noindent
   \texttt{#1}
   }
  }
$$
}
\def\pgcd{\textsc{pgcd}}

\newtheorem{exercice}{Exercice}

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

\begin{document}

\maketitle

Pour cette s\'eance de TPs, on utilise des nombres sign\'es
de 64 bits :


$$\texttt{typedef long long nombre;}$$

\section{Analyse de l'algorithme d'Euclide.}

\begin{enumerate}
\item Implanter une fonction \texttt{nombre pgcd( nombre a, nombre b)}
  qui calculer et retourne le PGCD des entiers $a$ et $b$.
\item On note $i(a,b)$ le nombre d'it\'eration de l'algororithme d'Euclide
  engendr\'e par le calcul de $\pgcd(a,b)$. Implanter une
  fonction \texttt{nombre pgcdcpt( nombre a, nombre b, int *cpt)}
  qui retourne  $\pgcd(a,b)$ et calcule le nombre d'it\'erations.
\item On note $\mu(a)$ la moyenne des $i(a,b)$  et
$m(a)$ le nombre maximal d'it\'erations ($1\leq b\leq a$). 
Repr\'esenter graphiquement
ces fonctions.
\item D\'eterminer des estimations empiriques des fonctions $m(a)$ et $\mu(a)$.
\item D\'eterminer deux entiers $a$ et $b$ tel que $i(a,b)=64$.
\end{enumerate}

\section{Euclide \'Etendu : version r\'ecursive.}

\begin{enumerate}
\item Implanter une fonction r\'ecursive :
$$\texttt{nombre pgcd( nombre a, nombre b, nombre *u, nombre *v)}$$
qui calcule des entiers $u$ et $v$ tels que :
$
\pgcd(a,b) = au + bv
$
\item Modifier cette fonction pour tracer les quotients et
restes successifs engendr\'es par l'algorithme d'Euclide.
\end{enumerate}


\end{document}
