\documentclass[twocolumn,a4paper]{article}
\usepackage{french,tp}
\begin{document}

\begin{header}
\Huge Corrig\'e du contr\^ole
\bigskip
\end{header}

\small

\section*{Premier exercice}

$\bullet$ {\tt 17 $<$ 2}
\\ une {\em expression} de type {\tt BOOLEAN}.

$\bullet$ {\tt FOR i:=1 TO 10 DO writeln(i)}
\\ une {\em instruction}, plus précisément une {\em itération énumérée}.

$\bullet$ {\tt 7 / 5}
\\ une {\em expression} de type {\tt REAL}.

$\bullet$ {\tt writeln('2+2=',4)}
\\ une {\em instruction}, plus précisément un {\em appel de proc\'edure}.

$\bullet$ {\tt VAR i:INTEGER}
\\ une {\em d\'eclaration de variable}.

$\bullet$ {\tt 17. * 2}
\\ une {\em expression} de type {\tt REAL}.

$\bullet$ {\tt IF (a=0) THEN readln(z)}
\\ une {\em instruction}, plus précisément un {\em branchement conditionnel}.

$\bullet$ {\tt a := 2+2}
\\ une {\em instruction}, plus précisément une {\em affectation}.

$\bullet$ {\tt WHILE (a<>0) DO a:=a-1}
\\ une {\em instruction}, plus précisément
une {\em itération conditionnelle} (tout comme un {\tt REPEAT UNTIL}).

$\bullet$ {\tt FUNCTION Somme(a,b:INTEGER):INTEGER}
\\ une {\em d\'eclaration de fonction}.

\section*{Troisi\`eme exercice}

$\bullet$ On a:
\begin{eqnarray*}
91 & = & 45 \times 2 + 1 = (22 \times 2 + 1) \times 2 + 2^0 \\
& = & 22 \times 2^2 + 2^1 + 2^0 \\
& = &  (11 \times 2) \times 2^2+2^1+2^0\\
& = & 11 \times 2^3 + 2^1 + 2^0 \\
& = & (5 \times 2 +1) \times 2^3 + 2^1 + 2^0 \\
& = & 5 \times 2^4 + 2^3 + 2^1 + 2^0 \\
& = & (2 \times 2+1) \times 2^4 + 2^3 + 2^1 + 2^0 \\
& = & 2^6 + 2^4+ 2^3 + 2^1 + 2^0 \\
& = & 2^6 + 0 \times 2^5 + 2^4 + 2^3
	+ 0 \times 2^2 + 2^1 + 2^0 \\
& = & (1011011)_2
\end{eqnarray*}
En pratique, on effectue des divisions euclidiennes 
successives par 2, jusqu'\`a ce que le quotient soit nul
(il ne faut donc pas oublier le dernier reste), puis l'on
renverse l'ordre des restes. On avait:
\begin{eqnarray*}
91 & = & 45 \times 2 + 1 \\
45 & = & 22 \times 2 + 1 \\
22 & = & 11 \times 2 + 0 \\
11 & = & 5 \times 2 + 1 \\
5 & = & 2 \times 2 + 1 \\
2 & = & 1 \times 2 + 0 \\
1 & = & 0 \times 2 + 1 
\end{eqnarray*}
On obtient bien la m\^eme chose.
\newpage

$\bullet$
Cette fois, on fait \'evidemment des divisions euclidiennes par 16:
\begin{eqnarray*}
91 = 5 \times 16 + 11 \\
5 = 0 \times 16 + 5 \\
\end{eqnarray*}
En base hexad\'ecimale, on utilise les ``chiffres''
A,B,C,D,E,F au lieu de 10,11,12,13,14,15. Finalement:
$$ 91 = (5B)_{16}.$$

 
$\bullet$ On demandait une {\em expression},
pas une {\em instruction}, et encore moins un {\em programme}:
\begin{center}
\tt  (x >= (y+z)) AND 
((y+z) >= (x*(a-(c+2)/d)+1))
\end{center}

\section*{Quatri\`eme Exercice}

Si on simule l'ordinateur, on obtient la s\'equence d'instructions
suivante (on note \verb|i_Aff| le paramètre passé à {\tt Aff}
par valeur et \verb|j_Aff| et \verb|i_Aff2| les variables locales) :
\begin{verbatim}
i := 2;
j := 7;
k := 3;
i_Aff := j;                  { vaut donc 7 }
j_Aff := i_Aff+1;            { vaut donc 8 }
writeln(i_Aff+1);            { car i_Aff >= 0 }
i_Aff := i_Aff+2;            { vaut donc 9 }
i_Aff2 := 5;
writeln(j_Aff + i_Aff2 + k); { car i_Aff2 >= 4}
writeln(i);
writeln(j);
\end{verbatim}
Il s'affiche donc \`a l'\'ecran:
\begin{verbatim}
8
16
2
7
\end{verbatim}
\newpage

\section*{Deuxi\`eme exercice (le plus long et le plus dur...)}

$\bullet$
{\tt TYPE Serie = ARRAY[1..100] OF REAL}.
\\ On peut aussi numéroter de 0 à 99.

$\bullet$
C'est le m\^eme principe que pour calculer une somme,
mais il faut initialiser à la valeur 1.

\begin{footnotesize}
\begin{verbatim}
FUNCTION Produit(S:Serie):REAL; { Passage par valeur }
VAR i:INTEGER; { Variable de boucle }
    P:REAL;    { Resultat temporaire }
BEGIN
  P := 1;
  FOR i := 1 TO 100 DO
    P := P * S[i]; { On multiplie par le i-eme terme}
  Produit := P; { On renvoie le resultat final }
END;
\end{verbatim}
\end{footnotesize}

On peut aussi faire ceci :
\begin{footnotesize}
\begin{verbatim}
FUNCTION Produit(S:Serie):REAL; { Passage par valeur }
VAR i:INTEGER; { Variable de boucle }
    P:REAL;    { Resultat temporaire }
BEGIN
  P := S[1]; { Le produit commence par le premier terme }
  FOR i := 2 TO 100 DO
    P := P * S[i]; { On multiplie par le i-eme terme}
  Produit := P; { On renvoie le resultat final }
END;
\end{verbatim}
\end{footnotesize}

$\bullet$
Il ne faut pas oublier que pour qu'une procédure
modifie le contenu d'une variable passée en argument,
l'argument doit passer par référence.
\begin{footnotesize}
\begin{verbatim}
PROCEDURE Negation(VAR S:Serie);
VAR i:INTEGER; { Variable de boucle }
BEGIN
  FOR i := 1 TO 100 DO
    S[i] := -S[i]; { On change le i-eme element }
END;
\end{verbatim}
\end{footnotesize}

$\bullet$ 
Le plus simple est de remarquer que le renversement
peut être effectué en deux temps :
[1,2,\dots,99,100] devient d'abord
$$ [51,52,\dots,99,100,1,2,\dots,49,50].$$
(en \'echangeant le 1er avec le 50i\`eme, le 2\`eme avec le 51i\`eme,
etc.)
Puis, dans un second temps, il devient:
$$ [100,99,\dots,52,51,1,2,\dots,49,50].$$
(en renversant l'ordre des 50 premiers \'el\'ements, comme
on l'a vu pour miroir, c'est-\`a-dire par d'autres \'echanges)
On obtient:
\begin{footnotesize}
\begin{verbatim}
PROCEDURE Renversement(VAR S:Serie); 
VAR i   : INTEGER; { Variable de boucle}
    Acc : REAL; { Pour faire des echanges }
BEGIN
  { Premier temps }
  FOR i := 1 TO 50 DO
  BEGIN { On echange le i-eme et le (50+i)-eme }
    Acc     := S[i];
    S[i]    := S[50+i];
    S[50+i] := Acc;
  END;
  { Deuxieme temps }
  FOR i := 1 TO 25 DO
  BEGIN { On echange le i-eme et le (51-i)-eme }
    Acc     := S[i]; 
    S[i]    := S[51-i];
    S[51-i] := Acc;
  END;
END;
\end{verbatim}
\end{footnotesize}
\newpage

$\bullet$
Si on avait le droit \`a une variable locale de type {\tt Serie},
ce serait nettement plus simple :
\begin{footnotesize}
\begin{verbatim}
PROCEDURE Somme(VAR S:Serie);
VAR T:Serie; { Resultat intermediaire }
    i:INTEGER;
BEGIN
{ Cas particuliers }
  T[1]   := S[100]+S[2];
  T[100] := S[99]+S[1];
{ Cas general }
  FOR i := 2 TO 99
  DO T[i] := S[i-1]+S[i+1];
{ Maintenant, on met a jour}
  S := T;
END;
\end{verbatim}
\end{footnotesize}

Mais puisqu'on n'a pas le droit \`a une variable locale
de type {\tt Serie}, il faut changer de m\'ethode.
On peut par exemple proc\'eder en deux temps:
le tableau devient d'abord
$$[2,3,4,\dots,99,100,1]$$
(en d\'ecalant les \'el\'ements sur la gauche)
puis
$$ [2+100,3+1,4+2,\dots,99+91,100+98,1+99].$$
(en rajoutant l'\'el\'ement pr\'ec\'edant le pr\'ec\'edent)
On doit utiliser des accumulateurs pour sauvegarder
les valeurs sur les bords. On obtient:
\begin{footnotesize}
\begin{verbatim}
PROCEDURE Somme(VAR S:Serie);
VAR i:INTEGER;
    Acc,Acc1,Acc2:REAL;
BEGIN
  { Premier Temps }
  Acc1 := S[1]; { On sauvegarde }
  FOR i := 1 TO 99 DO
    S[i] := S[i+1];
  S[100] := Acc1;
  { Deuxieme temps } 
  Acc1 := S[99];
  Acc2 := S[100];
  FOR i := 100 DOWNTO 3 DO { Surtout pas dans l'autre sens }
    S[i] := S[i]+S[i-2];
  { Maintenant, cas particuliers }
  S[2] := S[2] + Acc2;
  S[1] := S[1] + Acc1;
END;
\end{verbatim}
\end{footnotesize}

Pour se convaincre, simuler toutes ces proc\'edures et fonctions
\`a la main sur un exemple concret.

\end{document}
