\documentclass{article}
 
\usepackage[latin1]{inputenc}
\usepackage{epsfig}
 
\textheight=247mm
\textwidth=160mm
 
\headheight=12pt \headsep=20pt \footskip=36pt
 
\topmargin=297mm
\advance \topmargin by -\textheight
\divide  \topmargin by 2
\advance \topmargin by -1in
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
 
\leftmargin=210mm
\advance \leftmargin by -\textwidth
\divide  \leftmargin by 2
\advance \leftmargin by -1in 
\oddsidemargin=\leftmargin
\evensidemargin=\leftmargin
 
\abovedisplayskip=3mm
\belowdisplayskip=3mm
\abovedisplayshortskip=0mm
\belowdisplayshortskip=2mm
\unitlength=1mm
% \topskip=1cm
\parindent=0cm
\parskip=1ex
% \pagestyle{empty}
% \raggedbottom
%
% Exercices numerotes mais pas en italique.
%   \newtheorem{exercice}{Exercice}
%   \newenvironment{exo}{\begin{exercice}\rm }{\end{exercice}}
 
\newcounter{numeroquestion}
\def\Que{\addtocounter{numeroquestion}{1}
     \par{\bf\alph{numeroquestion})\ \ }}
 
 
 
\usepackage{amsfonts}
%\usepackage{isolatin1}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{alltt}
\usepackage{theorem}
{\theorembodyfont{\rmfamily} \newtheorem{exo}{Exercice}}
 
\newenvironment{sol}[1]{{\bfseries\Large Exo \ref{#1}.}}%
{\smallskip}
 
 
\begin{document}
%% ENONCES CC1  Eric Colin de Verdiere  2001/2002

COMMUN A TOUS LES ENONCES :

Il est demandé, pour le problème suivant, de proposer une solution en
pseudo-langage, puis une implantation en C++. L'évaluation tiendra
compte de la lisibilité de votre réponse (commentaires et
indentation).

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

{\bf Sujet~: calcul des variations d'un polynôme de degré $\leq 2$}

Écrire un programme qui lit trois réels $a,b$ et $c$ et qui donne les
variations de la fonction $f:x\mapsto ax^2+bx+c$.

On tiendra compte du fait que $a$ (et $b$, et $c$) peuvent être nuls.
On rappelle que, si $a\neq 0$, le changement de variation de $f$
intervient à l'abscisse $-\frac{b}{2a}$.

Par exemple~:
\begin{itemize}
  \item Si $f(x)=x^2+2x+6$, le programme doit répondre~:
    \begin{verbatim}f est décroissante entre -inf et -1 et croissante entre -1 et +inf.\end{verbatim}
  \item Si $f(x)=3x+7$, le programme doit répondre~:
    \begin{verbatim}f est croissante entre -inf et +inf.\end{verbatim}
  \item Si $f(x)=3$ (fonction constante), le programme doit répondre~:
    \begin{verbatim}f est constante entre -inf et +inf.\end{verbatim}
\end{itemize}

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

{\bf Sujet~: calcul de l'image $f(R)$ d'un polynôme $f$ de degré
  $\leq 2$}

Écrire un programme qui lit trois réels $a,b$ et $c$, coefficients de
la fonction $f(x)=ax^2+bx+c$, et qui calcule l'ensemble image $f(R)$,
c'est-à-dire l'ensemble des valeurs prises par $f(x)$ lorsque $x$
décrit $R$.

On tiendra compte du fait que $a$ (et $b$, et $c$) peuvent être nuls.
On rappelle que, si $a\neq 0$, le changement de variation de $f$
intervient à l'abscisse $x=-\frac{b}{2a}$.

Par exemple~:
\begin{itemize}
  \item Si $f(x)=x^2+2x+6$, le programme doit répondre~:
    \begin{verbatim}[5, +inf[\end{verbatim}
  \item Si $f(x)=-3x^2+7$, le programme doit répondre~:

    \begin{verbatim}]-inf, 7]\end{verbatim}

  \item Si $f(x)=2x+5$, le programme doit répondre~:
    \begin{verbatim}]-inf, +inf[\end{verbatim}
  \item Si $f(x)=3$ (fonction constante), le programme doit répondre~:
    \begin{verbatim}3\end{verbatim}
\end{itemize}

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

{\bf Sujet~: tester si un triangle de longueurs des côtés données est
  rectangle}

Écrire un programme qui lit trois réels $a,b$ et $c$, et qui répond si
oui ou non un triangle de côtés $a,b$ et $c$ est rectangle. Si au
moins l'un des trois réels est négatif alors le triangle n'est pas
rectangle.

On rappelle qu'un triangle est rectangle si et seulement si les trois
longueurs $x,y$ et $z$ de ses côtés, avec $z$ la plus grande longueur,
sont positives ou nulles et vérifient $x^2+y^2=z^2$ (théorème de
Pythagore).

Par exemple~:
\begin{itemize}
  \item On rentre 1, 2, 3. Le programme répond~:
    \begin{verbatim}Triangle non rectangle\end{verbatim}
    car $1^2+2^2\neq 3^2$.
  \item On rentre 3, 5, 4. Le programme répond~:
    \begin{verbatim}Triangle rectangle\end{verbatim}
    car $3^2+4^2=5^2$.
  \item On rentre 5, -3, 4. Le programme répond~:
    \begin{verbatim}Triangle non rectangle\end{verbatim}
    car $-3<0$.
\end{itemize}

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

{\bf Sujet~: tester si un triangle de longueurs des côtés données existe.}

Écrire un programme qui lit trois réels $a,b$ et $c$, et qui répond
s'il existe ou non un triangle de côtés $a,b$ et $c$ dans le
plan. (Les triangles aplatis sont considérés comme des triangles.)



On rappelle qu'on peut dessiner dans le plan un triangle dont les
longueurs des côtés sont $x,y$ et $z$, où $z$ est la plus grande des
longueurs, si et seulement si $z\leq x+y$ (inégalité triangulaire).

Par exemple~:
\begin{itemize}
  \item On rentre 1, 2, 12. Le programme répond~:
    \begin{verbatim}Ce n'est pas un triangle.\end{verbatim}
    car $12>1+2$.
  \item On rentre 3, 5, 4. Le programme répond~:
    \begin{verbatim}C'est un triangle.\end{verbatim}
    car $5\leq 3+4$.
  \item On rentre 5, -3, 4. Le programme répond~:
    \begin{verbatim}Ce n'est pas un triangle.\end{verbatim}
    car $5>4+(-3)$.
\end{itemize}



\begin{quotation}
  \noindent\textsl{Il est demandé, pour le problème suivant, de~:
    \begin{enumerate}
    \item proposer une solution en pseudo-langage~ \textnormal{[env. 15
        pts/20]}~;
    \item pour la (ou les) boucle(s) introduite(s) dans cette
      solution, écrire l'invariant correspondant (on ne demande pas de
      le prouver). Terminaison de l'algorithme~? \textnormal{[env. 5
        pts/20]}.
    \end{enumerate}
    Aucune ligne en C++ ne doit donc être écrite. La solution sera
    rédigée sur cette feuille. L'évaluation tiendra compte de la
    lisibilité de votre réponse~:
  \begin{itemize}
  \item commentaires (aux endroits où cela semble nécessaire~: rôle de
    chaque variable, boucle,~\ldots)~;
  \item indentation.
  \end{itemize}
  }
\end{quotation}

L'énoncé de l'invariant pourrait commencer de la façon suivante~: <<
Si l'on considère la suite $a_1,\ldots, a_n$ des nombres entrés
jusqu'à présent, alors telle variable vérifie telle propriété\ldots{} >>.


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

Écrire un programme qui lit une suite de nombres entiers croissante
(au sens large), et qui affiche le nombre de nombres distincts dans
cette suite.
La suite s'arrête quand l'utilisateur entre un nombre qui est
inférieur au précédent.

Par exemple~:
\begin{itemize}
\item L'utilisateur entre \verb+1+, \verb+3+, \verb+4+, \verb+2+; la
  lecture des nombres s'arrête ici car $2<4$. La suite considérée est
  $1,3,4$, qui contient trois nombres distincts. Le programme répond~:
  \verb+3+.
\item L'utilisateur entre \verb+8+, \verb+8+, \verb+8+ puis un nombre
  $<8$. La suite $8,8,8$ ne contient qu'un seul nombre, 8. Le
  programme répond~: \verb+1+.
\item L'utilisateur entre \verb+7+, \verb+7+, \verb+7+, \verb+9+,
  \verb+10+, \verb+12+, \verb+12+, et un nombre $<12$. La suite
  $7,7,7,9,10,12,12$ contient 4 nombres distincts. Le programme
  répond~: \verb+4+.
\end{itemize}

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

Écrire un programme qui lit une suite de nombres entiers croissante
(au sens large), et qui affiche le nombre qui apparaît le plus souvent
dans cette suite. Si plusieurs nombres apparaissent avec la même
fréquence, le programme renvoie un des nombres qui apparaît le plus
fréquemment.

La suite s'arrête quand l'utilisateur entre un nombre qui est
inférieur au précédent.

Par exemple~:
\begin{itemize}

\item L'utilisateur entre \verb+3+, \verb+3+, \verb+4+, \verb+2+; la
  lecture des nombres s'arrête ici car $2<4$. La suite considérée est
  $3,3,4$. Le nombre qui apparaît le plus fréquemment dans cette suite
  est $3$~: le programme répond \verb+3+.
\item L'utilisateur entre \verb+8+, \verb+8+, \verb+8+ puis un nombre
  $<8$. Le nombre qui apparaît le plus souvent dans la suite $8,8,8$
  est $8$ (c'est d'ailleurs le seul). Le programme répond~: \verb+8+.
\item L'utilisateur entre \verb+7+, \verb+7+, \verb+7+, \verb+9+,
  \verb+10+, \verb+12+, \verb+12+, et un nombre $<12$. Le nombre qui
  revient le plus fréquemment dans la suite $7,7,7,9,10,12,12$ est
  $7$.  Le programme répond~: \verb+7+.
\item L'utilisateur entre \verb+7+, \verb+7+, \verb+8+, \verb+9+,
  \verb+9+, et un nombre $<9$. Le programme peut alors répondre~:
  \verb+7+, ou bien~: \verb+9+ (les deux réponses sont acceptées).
\end{itemize}

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

Écrire un programme qui lit une suite de nombres entiers positifs ou
nuls, et qui affiche \verb+OUI+ s'il y a deux nombres consécutifs de
cette suite qui sont zéro et un (ou un et zéro), et \verb+NON+ sinon.

La suite s'arrête quand l'utilisateur entre un nombre strictement
négatif.

Par exemple~:
\begin{itemize}
\item L'utilisateur entre \verb+3+, \verb+4+, \verb+1+, \verb+-2+; la
  lecture des nombres s'arrête ici car $-2<0$. La suite considérée est
  $3,4,1$. Le programme répond \verb+NON+.
\item L'utilisateur entre \verb+1+, \verb+0+, \verb+8+ puis un nombre
  négatif. Le programme répond \verb+OUI+ car la suite $1,0,8$
  contient un 1 et un 0 consécutifs.
\item L'utilisateur entre \verb+8+, \verb+0+, \verb+1+ puis un nombre
  négatif. Le programme répond \verb+OUI+ car la suite $8,0,1$
  contient un 0 et un 1 consécutifs.
\item L'utilisateur entre \verb+3+, \verb+0+, \verb+1+, \verb+0+
  puis un nombre négatif. Le programme répond \verb+OUI+.
\item L'utilisateur entre \verb+1+, \verb+4+, \verb+0+ puis un nombre
  négatif. Le programme répond \verb+NON+ (le 1 et le 0 ne sont pas
  consécutifs).
\end{itemize}

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

Écrire un programme qui lit une suite de nombres entiers positifs, et
qui compte le nombre de croissances de cette suite, c'est-à-dire le
nombre de termes plus grands (au sens large) que leur prédécesseur (on
considère que le premier terme n'est jamais plus grand que son
prédécesseur).

La suite s'arrête quand l'utilisateur entre un nombre négatif.

Par exemple~:
\begin{itemize}
\item L'utilisateur entre \verb+3+, \verb+4+, \verb+1+, \verb+-2+; la
  lecture des nombres s'arrête ici car $-2<0$. La suite considérée est
  $3,4,1$. Le programme répond \verb+1+ (seul $4$ est un terme plus
  grand que son prédécesseur).
\item L'utilisateur entre \verb+1+, \verb+4+, \verb+8+, \verb+5+,
  \verb+8+ puis un nombre négatif. Le programme répond \verb+3+ car la
  suite $1,4,8,5,8$ a trois termes plus grands que leurs
  prédécesseurs~: le $4$ et les deux $8$.
\item L'utilisateur entre \verb+4+, \verb+3+, \verb+2+, \verb+1+, puis
  un nombre négatif. Le programme répond \verb+0+ car aucun terme
  n'est plus grand que son prédécesseur puisque la suite est
  strictement décroissante.
\item L'utilisateur entre \verb+1+, \verb+1+, \verb+1+ puis un nombre
  négatif. Le programme répond \verb+2+, car le deuxième et le
  troisième $1$ sont des termes plus grands (au sens large) que leur
  prédécesseur~; le premier terme n'est pas considéré comme un nombre
  plus grand que son prédécesseur.
\end{itemize}


%% ENONCES CC3  Eric Colin de Verdiere  2001/2002

Soient \verb+début+ et \verb+fin+ deux constantes entières avec
\verb+début+<\verb+fin+, $I$ l'ensemble des entiers entre
\verb+début+ et \verb+fin+. On code une fonction $f$ de $I$ dans $I$
par un tableau \verb+f+ indexé par l'ensemble des entiers $I$, à
valeurs dans $I$. Ainsi, la valeur de $f(i)$ est codée en
pseudo-langage par \verb+f[i]+.

L'objet du programme en pseudo-langage suivant est de calculer
l'itérée $n^{\mbox{ième}}$ de la fonction $f$, c'est-à-dire la
fonction $g=f\circ f\circ\ldots\circ f$ (où $n$ fonctions $f$
apparaissent dans la formule précédente).

\begin{verbatim}
PROGRAMME itérée
    CONSTANTES entières : début = 3, fin = 8
    TYPE TabFonc : tableau d'entiers indexé par [début..fin]

DÉBUT itérée
    VARIABLES :
        n : entier     // le nombre d'itérations
        i : entier     // l'itération courante
        j : entier     // l'indice courant
        f : TabFonc    // la fonction f
        g : TabFonc    // la fonction g, qui est le résultat à la fin

    // lecture du nombre d'itérations
    AFFICHER "Entrez le nombre d'itérations > 0"
    RÉPÉTER
        LIRE n
    JUSQU'À ( n > 0 )

    // initialisation des variables
    INITIALISER f aléatoirement avec des entiers entre début et fin
    COPIER f dans g
    AFFICHER "La fonction f est :"
    AFFICHER f

    // calcul de g
    POUR i <- 2 jusqu'à n FAIRE                   // première boucle
        POUR j <- début jusquà fin FAIRE         // seconde boucle
            g[j] <- f[g[j]]
        FIN POUR                                  // fin seconde boucle
        // invariant première boucle : ici, g contient la i-ème itérée de f
    FIN POUR                                      // fin première boucle

    // affichage du résultat
    AFFICHER "La ", n, "ième itérée de f est"
    AFFICHER g
FIN itérée
\end{verbatim}


\section{Implantation en C++ [env. 4 pts/5]}

Faire une implantation en C++ de ce programme.

La traduction des commentaires est facultative, mais la notation
tiendra compte de l'indentation.

La première ligne du programme doit contenir, en commentaire, votre
nom et votre prénom. Le programme doit être imprimé à la fin de la
séance.

Attention, l'implantation utilise des tableaux de taille fixée au
début du programme par des constantes \verb+début+ et \verb+fin+.
Votre programme doit encore fonctionner si l'on modifie la valeur de
ces constantes.

L'exemple ci-dessous est un extrait de programme qui rappelle la
syntaxe pour tirer des nombres au hasard~:

\begin{verbatim}
#include<stdlib.h>
#include<time.h>
...
int a,b;
...
srand(time(NULL)); // ligne à ne mettre qu'une seule fois avant toute utilisation de rand()
a = rand() % b;    // a contient maintenant un nombre aléatoire entre 0 et b-1
\end{verbatim}

\vspace{1eX}

\section{Question [env. 1 pt/5]}

(Réponse à donner ci-dessous).

L'algorithme fonctionne-t-il encore si l'on remplace la ligne~:
\verb+g[j] <- f[g[j]]+ par~: \verb+g[j] <- g[f[j]]+~? Justifiez.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Soient \verb+début+ et \verb+fin+ deux constantes entières avec
\verb+début+<\verb+fin+, $I$ l'ensemble des entiers entre
\verb+début+ et \verb+fin+. On code une fonction $f$ de $I$ dans $I$
par un tableau \verb+f+ indexé par l'ensemble des entiers $I$, à
valeurs dans $I$. Ainsi, la valeur de $f(i)$ est codée en
pseudo-langage par \verb+f[i]+.

L'objet du programme en pseudo-langage suivant est de générer une
permutation aléatoire de $I$, c'est-à-dire une bijection de $I$ dans
$I$.

\begin{verbatim}
PROGRAMME permutation
    CONSTANTES entières : début = 3, fin = 8
    TYPE TabFonc : tableau d'entiers indexé par [début..fin]

DÉBUT permutation
    VARIABLES :
        i : entier     // un indice
        j : entier     // un indice qui va être échangé avec i
        f : TabFonc    // la fonction f

    INITIALISER le tableau f à l'identité (f[i]=i pour tout i)

    POUR i <- début jusqu'à fin  FAIRE           // boucle
        j <- un nombre au hasard entre i et fin (compris)
        SI (j différent de i)
        ALORS
            ÉCHANGER f[i] et f[j]
        FIN SI
    FIN POUR                                      // fin boucle

    // affichage du résultat
    AFFICHER "Une permutation aléatoire est :"
    AFFICHER f

FIN permutation
\end{verbatim}

\section{Implantation en C++ [env. 3,75 pts/5]}

Faire une implantation en C++ de ce programme.

La traduction des commentaires est facultative, mais la notation
tiendra compte de l'indentation.

La première ligne du programme doit contenir, en commentaire, votre
nom et votre prénom. Le programme doit être imprimé à la fin de la
séance.

Attention, l'implantation utilise des tableaux de taille fixée au
début du programme par des constantes \verb+début+ et \verb+fin+.
Votre programme doit encore fonctionner si l'on modifie la valeur de
ces constantes.

L'exemple ci-dessous est un extrait de programme qui rappelle la

syntaxe pour tirer des nombres au hasard~:

\begin{verbatim}
#include<stdlib.h>
#include<time.h>
...
int a,b;
...
srand(time(NULL)); // ligne à ne mettre qu'une seule fois avant toute utilisation de rand()
a = rand() % b;    // a contient maintenant un nombre aléatoire entre 0 et b-1
\end{verbatim}

\vspace{1eX}

\section{Questions [env. 1,25 pt/5]}

(Réponses à donner ci-dessous).

Que calcule l'algorithme, dans chacun des cas suivants~? Justifiez.

\begin{enumerate}
\item On remplace la ligne~: \verb+POUR i <- début jusqu'à fin FAIRE+

\noindent par~: \verb+POUR i <- début jusqu'à fin-1 FAIRE+.
\item On remplace la ligne~: \verb+POUR i <- début jusqu'à fin FAIRE+

\noindent par~: \verb!POUR i <- début+1 jusqu'à fin FAIRE!.
\end{enumerate}

%% ENONCES CC4  Eric Colin de Verdiere  2001/2002

\noindent{\sl L'exercice suivant est à traiter en pseudo-langage (à rendre sur
  cette feuille) et en C++ (à imprimer en fin de séance, la première
  ligne du programme devant être un commentaire portant votre nom).}

\vspace{1eM}

Une \emph{sauterelle} est un objet, assimilé à un point matériel, qui
est astreint à se déplacer dans le plan et est doté d'une orientation
(direction dans laquelle il pointe). On peut demander à une sauterelle
d'\emph{avancer} d'une certaine distance (dans la direction vers
laquelle elle pointe), de \emph{tourner à gauche} ou \emph{à droite}
d'un certain angle (changer son orientation)~; on veut aussi pouvoir
calculer facilement sa \emph{distance à l'origine}.


Une sauterelle est parfaitement définie par trois flottants~: ses
coordonnées dans le plan $x$ et $y$, et son angle $\theta$ (en
radians, entre $0$ et $2\pi$)~; voir figure ci-dessous.


On demande d'écrire les fonctions et procédures suivantes, {\bf en
  prenant garde à utiliser les passages par référence et par valeur à
  bon escient}~:

\begin{enumerate}
\item \verb!init!~: procédure qui prend en arguments $x$, $y$ et
  $\theta$ et qui initialise la sauterelle à la position $(0,0)$,
  orientation $0$ radians.
\item \verb!tg! (tourner à gauche)~: procédure qui prend en arguments
  $x$, $y$, $\theta$, et l'angle $\alpha$ (toujours en radians), et
  qui augmente l'angle $\theta$ de $\alpha$.
\item \verb!avance!~: procédure qui prend en arguments les trois
  paramètres $x$, $y$, $\theta$ de la sauterelle et la distance $d$
  qu'elle doit parcourir. Cette procédure change donc $x$ et $y$ en
  fonction de $\theta$ et $d$.
\item \verb!dist! (distance à l'origine)~: fonction qui prend en
  arguments $x$, $y$ et $\theta$ et qui renvoie la distance de la
  sauterelle à l'origine.
\end{enumerate}

Le programme principal (à écrire pour tester votre programme~!) sera
par exemple~:

\noindent\begin{tabular}{p{0.71\linewidth}p{0.27\linewidth}}
\begin{verbatim}
#include <iostream.h>
#include <math.h>
const float pi=3.14159265358979;
...
void main()
{
    float x,y,t;          // variables de la sauterelle, t=theta
    init (x,y,t);         // met x,y,t à 0
    avance (x,y,t,10);    // maintenant, x=10, y=0, t=0
    tg (x,y,t, PI/4);     // maintenant, x=10, y=0, t=pi/4
    cout << dist(x,y,t);  // doit renvoyer 10
    cout << endl;
}
\end{verbatim}
&
%\vspace{0cm}\psfrag{x}{$(x,y)$}\psfrag{0}{$(0,0)$}\psfrag{t}{$\theta$}
%\includegraphics[width=\linewidth]{cc44f}
\end{tabular}



Pour la troisième question, on notera qu'il faut augmenter $x$ de
$d\cdot\cos\theta$ et $y$ de $d\cdot\sin\theta$. En C++, on utilisera
les fonctions \verb!cos! et \verb!sin!  (qui prennent un argument
flottant, en radians, et qui calculent son cosinus et son sinus).

\vspace{1eM}

{\scriptsize Note~: ce problème est inspiré du langage de
  programmation LOGO, qui permet de réaliser des dessins assez jolis
  en utilisant récursivement les fonctions décrites dans le sujet et
  en créant les routines d'affichage de la trajectoire de la
  sauterelle.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent{\sl L'exercice suivant est à traiter en pseudo-langage (à rendre sur
  cette feuille) et en C++ (à imprimer en fin de séance, la première
  ligne du programme devant être un commentaire portant votre nom).}

\vspace{1eM}

La \emph{suite de Fibonacci} est la suite $(F_n)_{n\in N}$ définie par 
$F_0=F_1=1$ et, pour $n\geq 0$, $F_{n+2}=F_{n-1}+F_n$. Ses premiers
termes sont~: $1,1,2,3,5,8,13,21,\ldots$

\begin{enumerate}
\item Écrire une procédure \verb!etape_fibo! qui prend deux paramètres
  entiers $a$ et $b$, et telle que, si on suppose que $a=F_n$ et
  $b=F_{n+1}$ pour un certain $n$ avant l'exécution de la procédure,
  alors après son exécution $a=F_{n+1}$ et $b=F_{n+2}$.
\item Écrire une fonction \verb!fibo! qui prend un paramètre entier
  $n$ et qui retourne l'entier $F_n$ (cette fonction utilisera la
  procédure \verb!etape_fibo!). Donner l'invariant de la boucle (sans
  le prouver).
\item On admet que $\frac{F_{n+1}}{F_n}$ tend, quand $n\rightarrow
  +\infty$, vers $\frac{1+\sqrt{5}}{2}$. Écrire une fonction
  \verb!terme! qui prend en entrée un flottant, $\varepsilon$, et qui
  renvoie le plus petit entier $n$ tel que
  $|\frac{F_{n+1}}{F_n}-\frac{1+\sqrt{5}}{2}|<\varepsilon$.
\item Écrire le programme principal qui lit un entier $n$ et affiche
  $F_n$, puis qui lit un flottant $\varepsilon>0$ et qui affiche le
  résultat de \verb!terme!($\varepsilon)$.
\end{enumerate}
Pour les fonctions et procédures, on prendra garde d'utiliser les
passages par référence et par valeur à bon escient.

Attention, pour la question 3, on rappelle que si $a$ et $b$ sont
entiers, \verb!a/b! désigne le quotient (entier) de $a$ par $b$. Par
contre, si $c$ est déclaré comme flottant, \verb!c=float(a)/float(b);!
calculera $c=\frac{a}{b}$ (division exacte).

On rappelle que la fonction valeur absolue sur les flottants se note
\verb+fabs+ (avec \verb!math.h!).
\end{document}