\documentclass[a4paper,twocolumn]{article}
\usepackage{amstex,french,tp}
\advance\topmargin -1cm
\advance\textheight 1cm

\begin{document}

\begin{header}
\Huge Treizième TP
\bigskip
\end{header}

\section{Multiplication à la russe}
Pour multiplier entre eux deux entiers non négatifs $x$ et $y$,
on procède ainsi :
\begin{itemize}
\item[$\bullet$] On divise $x$ par 2 (division euclidienne sans
tenir compte du reste) et on multiplie $y$ par 2. On s'arrête
lorsque $x = 1$.
\item[$\bullet$] La valeur de $x y$ est alors la somme des valeurs
de $y$ correspondant à des $x$ impairs.
\end{itemize}

\begin{tabular}{l}
Exemple : $17 \times 13 = 221$ \cr
On a bien $221 = 13+208$. \cr
\end{tabular}
\begin{tabular}{rrl}
17 & 13 & $\leftarrow$ \cr
8 & 26 \cr
4 & 52 \cr
2 & 104 \cr
1 & 208 & $\leftarrow$ \cr
\end{tabular}

\bigskip
\fbox{\advance\hsize-10pt\begin{minipage}{\hsize}
Faire une fonction qui calcule le produit de deux entiers
avec cette méthode, en utilisant une unique variable locale.
\end{minipage}}

\vspace*{1cm}

\section{Racines d'un polynôme par la méthode de Newton}
On représente les polynômes par le type ci-dessous (voir TP 9)
\begin{verbatim}
CONST MaxDeg = 100;
TYPE Poly =
  RECORD
    Degre : -1..MaxDeg;
    Coeff : ARRAY[0..MaxDeg] OF REAL;
  END;
\end{verbatim}

La méthode de Newton pour trouver une racine d'une
fonction $f$ est la suivante :
\begin{itemize}
\item[$\bullet$]
on choisit une valeur $x_0$
\item[$\bullet$]
on calcule $x_{n+1} = x_n - {f(x_n)\over f'(x_n)}$
\end{itemize}

\bigskip

Pour mettre en {\oe}uvre cette méthode,
on fera les procédures et fonctions suivantes :
\begin{itemize}
\item[$\bullet$]
{\tt Entrée} pour saisir au clavier les coefficients d'un polynôme.
\item[$\bullet$]
{\tt Dérivée} qui calcule le polynôme dérivé.
\item[$\bullet$]
{\tt Affiche} qui affiche la liste des coefficients d'un polynôme.
\item[$\bullet$]
{\tt Valeur} qui calcule la valeur $P(x)$
lorsqu'on lui donne en arguments $P$ et $x$.
\end{itemize}

\vspace*{5mm}
\[
\qquad
\multiply\arraycolsep2
\divide\arraycolsep3
\begin{array}{|c|c|c|c|c|}\hline
 & & &2& \cr\hline
 & &1& & \cr\hline
\hskip1ex& & & & \cr\hline
 &\hskip1ex& & & \cr\hline
 & & & &3\cr\hline
\end{array}
\qquad
\begin{array}{|c|c|c|c|c|}\hline
 &6& &2& \cr\hline
 & &1& & \cr\hline
 &5& & & \cr\hline
4& & & & \cr\hline
 & & & &3\cr\hline
\end{array}
\qquad
\begin{array}{|c|c|c|c|c|}\hline
 &6& &2& \cr\hline
 & &1& & \cr\hline
 &5& & &9\cr\hline
4& & &8& \cr\hline
 & &7& &3\cr\hline
\end{array}
\]

\newpage
\section{Carrés magiques}
Le type suivant définit un tableau carré d'ordre 10 :
\begin{verbatim}
CONST Ordre = 10;
TYPE Carré = ARRAY[1..Ordre,1..Ordre] OF INTEGER;
\end{verbatim}

$\bullet$
Écrire deux fonctions {\tt SommeLigne} et {\tt SommeColonne}
qui calculent respectivement la somme des termes de la ligne $i$
et la somme des termes de la ligne $j$.

$\bullet$
Écrire deux fonctions {\tt Diagonale1} et {\tt Diagonale2}
qui calculent respectivement la somme des termes de la
première et seconde diagonale.

$\bullet$
On dit qu'un carré est magique si la somme des termes de chaque
ligne, de chaque colonne et des deux diagonales est identique.
Écrire une fonction {\tt Magique} dont le résultat est un
booléen qui dit si un carré est magique.

$\bullet$
On dit qu'un carré magique d'ordre $n$ est élémentaire si ses termes
sont les entiers de 1 à $n^2$.
Écrire une fonction {\tt Élémentaire} dont le résultat est un
booléen qui dit si un carré est un carré magique élémentaire.
\medskip

Par exemple, le carré ci-dessous est un carré magique élémentaire
d'ordre 3. La somme des lignes et colonnes est 15.
On pourra prouver (mathématiquement) que tous les carrés magiques
élémentaires sont d'ordre impair.

\[
\begin{array}{|c|c|c|}\hline
8&1&6\cr\hline 3&5&7\cr\hline 4&9&2\cr\hline
\end{array}
\]

$\bullet$
Voici une méthode pour construire des carrés magiques
d'ordre $n$ à partir d'une valeur initiale $x_0$ et d'un pas $p$.
Il suffit d'appliquer les règles suivantes. On peut être amené
à utiliser successivement plusieurs de ces règles.
\begin{enumerate}
\itemsep0pt
\item On écrit successivement les termes de la suite
arithmétique de premier terme $x_0$ et de raison $p$.
On écrit $x_0$ dans la case immédiatement au dessus
de la case centrale.
\item On remplit le tableau selon une diagonale ascendante
gauche--droite.
\item Si on sort en haut, on se repositionne en bas de la colonne.
\item Si on sort à droite, on se repositionne à gauche de la ligne.
\item Si on sort à gauche, on se repositionne à droite de la ligne.
\item Si la case est occupée, on {\em ricoche} suivant la diagonale
ascendante droite--gauche.
On reprendra à l'étape suivante le déplacement normal suivant
la diagonale ascendante gauche--droite.
\end{enumerate}

Voici le cheminement, pour $n=5$, $x_0=1$ et $p=1$.

\[
\multiply\arraycolsep2
\divide\arraycolsep3
\begin{array}{|c|c|c|c|c|}\hline
  &6& &2& \cr\hline
10& &1& & \cr\hline
  &5& & &9\cr\hline
 4& & &8& \cr\hline
11& &7& &3\cr\hline
\end{array}
\qquad
\divide\arraycolsep2
\begin{array}{|c|c|c|c|c|}\hline
  & 6&  & 2&15\cr\hline
10&  & 1&14&  \cr\hline
  & 5&13&  & 9\cr\hline
 4&12&  & 8&16\cr\hline
11&  & 7&  & 3\cr\hline
\end{array}
\qquad
\begin{array}{|c|c|c|c|c|}\hline
23& 6&19& 2&15\cr\hline
10&18& 1&14&22\cr\hline
17& 5&13&21& 9\cr\hline
 4&12&25& 8&16\cr\hline
11&24& 7&20& 3\cr\hline
\end{array}
\]

\end{document}
