\documentstyle[a4,french]{article}
\newtheorem{theoreme}{Théorème}
%% Pour un tabbing en choisissant la fonte
\makeatletter
\def\@startline{\footnotesize\tt\global\@curtabmar\@nxttabmar
   \global\@curtab\@curtabmar\global\setbox\@curline\hbox{}\@startfield\strut}
\makeatother
%% Mise en page
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  0mm
\evensidemargin 0mm
\textwidth 170mm
\textheight 245mm
\advance\textheight by \topskip
 
\begin{document}
\stepcounter{section}
\section{Exercices simples}
\stepcounter{subsection}
\subsection{Gestion d'un tableau d'entiers}
\begin{enumerate}
\item Étant donné un tableau d'entiers $t_{initial}$, écrire une procédure
qui fabrique un tableau de même longueur $t_{final}$, où chaque élément
$t_{final}[n]$ est la somme $\sum_{k\leq n}t_{initial}[k]$ des $n$
premiers éléments de $t_{initial}$.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
TYPE Tableau = ARRAY[1..Longueur] OF INTEGER; \\
PROCEDURE Somme(ti : Tableau; VAR tf : Tableau); \\
VAR i : 1..Longueur; \\
BEGIN \\
\> tf[1] := ti[1]; \\
\> FOR i := 2 TO Longueur DO \\
\> \> tf[i] := tf[i-1] + ti[i]; \\
END; \\
\end{tabbing}

\item Étant donné un tableau d'entiers $t_{initial}$ et un entier $N$,
écrire une procédure qui donne le plus petit élément de $t_{initial}$
qui soit strictement plus grand que $N$.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \=
\hspace*{3em} \= \hspace*{3em} \= \kill
PROCEDURE Suivant(ti : Tableau; N : INTEGER; VAR petit : INTEGER); \\
VAR \\
\> i : 1..Longueur; \\
\> trouvé : BOOLEAN;
   \{ Il n'y a pas toujours d'élément de $t_{initial}$ supérieur à $N$ \} \\
BEGIN \\
\> trouvé := False; \\
\> FOR i := 1 TO Longueur DO \\
\> \> IF ( ti[i] >{} N ) THEN \\
\> \> \> IF Trouvé THEN \\
\> \> \> \> IF ti[i] <{} petit THEN \\
\> \> \> \> \> petit := ti[i] \\
\> \> \> ELSE \\
\> \> \> BEGIN \\
\> \> \> \> Trouvé := True; \\
\> \> \> \> petit := ti[i] \\
\> \> \> END; \\
\> IF NOT Trouvé THEN \\
\> \> petit := N; \\
END; \\
\end{tabbing}
Parfois, il n'y a pas d'élément de $t_{initial}$ qui soit strictement
plus grand que $N$. On décide alors (par convention) que le résultat
est $N$.

\item Utiliser la réponse à la question précédente pour écrire une procédure
qui, étant donné un tableau d'entiers tous différents $t_{initial}$ fabrique
un tableau $t_{final}$ qui contienne les mêmes éléments que $t_{initial}$,
en ordre croissant. Cet algorithme de tri s'appelle {\bf tri par sélection}.
Réfléchir à ce qui se passe si $t_{initial}$ contient deux fois le même
nombre.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \=
\hspace*{3em} \= \hspace*{3em} \= \kill
PROCEDURE Trie(ti : Tableau; VAR tf : Tableau); \\
VAR \\
\> i : 1..Longueur; \\
BEGIN \\
\> \{ On cherche quel est le plus petit élément de ti \} \\
\> tf[1] := ti[1]; \\
\> FOR i := 2 TO Longueur DO \\
\> \> IF ti[i] <{} petit THEN \\
\> \> \> tf[1] := ti[i]; \\
\> \{ On continue, élément par élément, pour trouver le suivant... \} \\
\> FOR i := 2 TO Longueur DO \\
\> \> Suivant(ti,tf[i-1], tf[i]);
END; \\
\end{tabbing}
S'il y a plusieurs éléments identiques (par exemple {\tt 3 5 1 3 6 3 4}),
le tableau $t_{final}$ contient au début la liste triée et à la fin
le plus grand élément est répété plusieurs fois (pour notre exemple
{\tt 1 3 4 5 6 6 6}). Le tri par sélection ne marche donc pas pour ce
genre de tableaux.
\end{enumerate}

\end{document}
