\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}
\section{Quelques applications directes du cours}
Les corrigés de 1.1 et 1.2 ont été faits en cours.
\stepcounter{subsection}
\stepcounter{subsection}
\subsection{Passage par valeur ou par référence}
Les procédures {\tt Entre} et {\tt Échange} modifient {\tt t}. Ce qui
nous donne~:
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROCEDURE Entre (VAR t : Tableau);                          \\
PROCEDURE Affiche (t : Tableau);                            \\
PROCEDURE Échange (VAR t : Tableau; pos1, pos2 : Indice);   \\
\end{tabbing}

\section{Exercices simples}
\subsection{Arithmétique}
\begin{enumerate}
\item Écrire un programme qui demande à l'utilisateur un nombre entier $n$ et
affiche les entiers de 1 à $n$.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM PremiersEntiers;                                    \\
VAR i, n : INTEGER;                                         \\
BEGIN                                                       \\
\> Write('Entre un nombre'); ReadLn(n);                     \\
\> FOR i := 1 TO n DO                                       \\
\> \> WriteLn(i);                                           \\
END.                                                        \\
\end{tabbing}
\item Écrire un programme qui demande à l'utilisateur un nombre entier et
dit si ce nombre est pair.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM NombrePair;                                         \\
VAR n : INTEGER;                                            \\
BEGIN                                                       \\
\> Write('Entre un nombre'); ReadLn(n);                     \\
\> IF n MOD 2 = 0 THEN                                      \\
\> \> WriteLn(n,' est pair');                               \\
END.                                                        \\
\end{tabbing}
\item Écrire un programme qui demande à l'utilisateur un nombre entier et
affiche tous les diviseurs de ce nombre.

Un premier programme, qui teste pour tous les nombres positifs inférieurs à $n$
s'ils sont diviseurs de $n$. Attention~: si $n = 0$, tous les entiers
sont diviseurs de $n$. Si $n$ est négatif, on remarque que $n$ et $-n$
ont les mêmes diviseurs.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM Diviseurs;                                          \\
VAR n, diviseur : INTEGER;                                  \\
BEGIN                                                       \\
\> Write('Entre un nombre'); ReadLn(n);                     \\
\> IF n <{} 0 THEN                                          \\
\> \> n := - n;                                             \\
\> IF n = 0 THEN                                            \\
\> \> WriteLn('Tous les entiers divisent 0')                \\
\> ELSE                                                     \\
\> \> FOR diviseur := 1 TO n DO                             \\
\> \> \> IF n MOD diviseur = 0 THEN                         \\
\> \> \> \> WriteLn(diviseur);                              \\
END.                                                        \\
\end{tabbing}

On gagne du temps si on remarque que lorsqu'on écrit $n = a.b$,
l'un parmi $a$ et $b$ est inférieur à $\sqrt n$ et l'autre est
supérieur à $\sqrt n$.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM Diviseurs;                                          \\
VAR n, diviseur : INTEGER;                                  \\
BEGIN                                                       \\
\> Write('Entre un nombre'); ReadLn(n);                     \\
\> IF n <{} 0 THEN                                          \\
\> \> n := - n;                                             \\
\> IF n = 0 THEN                                            \\
\> \> WriteLn('Tous les entiers divisent 0')                \\
\> ELSE                                                     \\
\> \> FOR diviseur := 1 TO Trunc( Sqrt (n) ) DO             \\
\> \> \> IF n MOD diviseur = 0 THEN                         \\
\> \> \> \> WriteLn(diviseur, n DIV diviseur);              \\
END.                                                        \\
\end{tabbing}

\item Écrire un programme qui demande à l'utilisateur deux nombres entiers et
calcule leur PGCD. Attention, il existe plusieurs méthodes envisageables,
l'une d'entre elles effectue beaucoup moins d'opérations que les autres.

Un premier programme, qui teste pour tous les nombres positifs inférieurs à $n$
s'ils sont diviseurs de $m$ et $n$, le plus grand est le PGCD.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM PGCD;                                               \\
VAR m, n, d, plusgrand : INTEGER;                           \\
BEGIN                                                       \\
\> Write('Entre deux nombres'); ReadLn(m,n);                \\
\> IF (m <= 0) OR (n <= 0) THEN                             \\
\> \> WriteLn('Pas de nombre négatif SVP.')                 \\
\> ELSE                                                     \\
\> BEGIN                                                    \\
\> \> FOR d := 1 TO n DO                                    \\
\> \> \> IF ( m MOD d = 0 ) AND ( n MOD d = 0 ) THEN        \\
\> \> \> \> plusgrand := d;                                 \\
\> \> WriteLn(plusgrand);                                   \\
\> END                                                      \\
END.                                                        \\
\end{tabbing}

\def\MOD{\mathop{\mathrm{MOD}}}
\def\PGCD{\mathop{\mathrm{PGCD}}}
Un programme nettement plus efficace, qui utilise l'algorithme
dit d'Euclide. Le principe de cet algorithme est exprimé par le
théorème suivant~:
\begin{theoreme}
Si $r$ est le reste de la division euclidienne de $m$ par $n$,
alors le PGCD de $m$ et de $n$ est égal au PGCD de $r$ et de $n$.
\end{theoreme}
On pose $m_0 = m$ et $n_0 = n$ et l'algorithme d'Euclide calcule
les deux suites $(m_i)_i$ et $(n_i)_i$. On calcule $m_{i+1} = n_i$ et
$n_{i+1} = m_i \MOD n_i$, jusqu'à obtenir $n_N = 0$, on a alors
$m_N = \PGCD(m,n)$. Par exemple~:
\[ \begin{array}{cccccc}
m_i & 700 & 96 & 28 & 12 & 4 \\
n_i &  96 & 28 & 12 &  4 & 0 \\
\end{array} \]
Pour prouver que l'algorithme donne bien le PGCD, on fait les
deux remarques suivantes~:
\begin{itemize}
\item[i)]   $\PGCD(m_i,n_i)$ est constant pendant tout l'algorithme
puisque $\PGCD(m,n) = \PGCD(n,m \MOD n)$.
\item[ii)]  Si $m_i>n_i$, alors $m_i \MOD n_i < m_i$, donc la suite
$(m_i)_i$ est strictemnt décroissante, donc l'algorithme se termine.
\end{itemize}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM PGCD;                                               \\
VAR m, n, r : INTEGER;                                      \\
BEGIN                                                       \\
\> Write('Entre deux nombres'); ReadLn(m,n);                \\
\> IF (m <= 0) OR (n <= 0) THEN                             \\
\> \> WriteLn('Pas de nombre négatif SVP.')                 \\
\> ELSE                                                     \\
\> BEGIN                                                    \\
\> \> REPEAT                                                \\
\> \> \> r := m MOD n;                                      \\
\> \> \> m := n;                                            \\
\> \> \> n := r;                                            \\
\> \> UNTIL n = 0;                                          \\
\> \> WriteLn(m);                                           \\
\> END                                                      \\
END.                                                        \\
\end{tabbing}

\end{enumerate}

\end{document}
