\chapterimage{pinkfloydummagumma}

\chapter{Méthodes de programmation}
\Pasc

\section{PASCAL}


Dans toute cette  section, pour plus de détails, on  pourra se référer à
l'ouvrage de Claude \textsc{Delannoy}\cite{del}.
\subsection{Types prédéfinis}

\subsubsection{Les entiers}

\paragraph{INTEGER}

Les opérateurs  associés sont \verb|+|,  \verb+-+, \verb+*+, \verb+DIV+,
\verb+MOD+, \verb+ABS+, \verb+SQR+, \verb+ODD+.

\begin{lstlisting}[caption={}]
PROGRAM entier;
VAR i :  INTEGER;

BEGIN
  WRITE('Entrez un entier : ');
  READLN(i);
  WRITELN('Le double de ',i,' est ',2*i);
  READLN;
END.             
\end{lstlisting}

Essayez avec $2^{30}-1$, $2^{31}-1$, $2^{31}$,...


\verb+INTEGER+  correspond aux entiers  relatifs et  \verb+CARDINAL+ aux
entiers naturels.

\paragraph{Les autres types d'entiers}


En fait, \verb+INTEGER+ et \verb+CARDINAL+ dépendent de l'ordinateur utilisé.  Pour pallier à
cette incertitude, il existe des types d'entiers aux tailles fixées:

\begin{itemize}
\item \verb+BYTE+: les entiers de 0 à $2^8-1=255$;
\item \verb+WORD+: les entiers de 0 à $2^{16}-1=\numprint{65535}$;
\item      \verb+LONGWORD+:      les       entiers      de      0      à
  $2^{32}-1=\numprint{4294967295}$;
\item \verb+QWORD+: les entiers de 0 à $2^{64}-1$;
\item \verb+SHORTINT+: les entiers de $-128$ à 127;
\item   \verb+SMALLINT+:   les    entiers   de   $-\numprint{32768}$   à
  $\numprint{32767}$;
\item \verb+LONGINT+: les entiers de $-2^{31}$ à $2^{31}-1$;
\item \verb+INT64+: les entiers de $-2^{63}$ à $2^{63}-1$;
\end{itemize}


\subsubsection{Les réels}
\paragraph{REAL}



Les opérateurs  associés sont \verb|+|,  \verb+-+, \verb+*+, \verb+/+,
\verb+ABS+,    \verb+SQR+,    \verb+SQRT+,    \verb+SIN+,    \verb+COS+,
\verb+ARCTAN+,    \verb+LN+,   \verb+EXP+,    \verb+FRAC+,   \verb+INT+,
\verb+ROUND+, \verb+TRUNC+, \verb+PI+.


Commentez ce programme:

\begin{lstlisting}[caption={}]
PROGRAM reel;
CONST x = 1.0e20;
      y = 2.0;

VAR adda : REAL;
    addb : REAL;

BEGIN
  adda:=(x+y)-x;
  addb:=(x-x)+y;
  WRITELN(adda:2:1,' = ',addb:2:1);
  READLN;
END.           
\end{lstlisting}



\paragraph{Les autres types réels}

Comme   pour   \verb+INTEGER+,   \verb+REAL+  dépend   de   l'ordinateur
utilisé. Pour plus de sûreté, on peut distinguer:

\begin{itemize}
\item \verb+SINGLE+ correspondant aux classes de réels de valeur absolue
  comprise entre $1,5\cdot  10^{-45}$ et $3,4\cdot 10^{38}$ avec  7 ou 8
  chiffres significatifs;
\item \verb+DOUBLE+ correspondant aux classes de réels de valeur absolue
  comprise entre $5,0\cdot  10^{-324}$ et $1,7\cdot 10^{308}$ avec  15 ou 16
  chiffres significatifs;
\end{itemize}

\subsubsection{CHAR}





Chaque caractère est associé à un codage binaire, en général
sur 8 bits (un octet) ce qui donne $2^8=256$ caractères possibles.

En fait,  un américain a mis au  point en 1961 l'ASCII  (on prononce \og
aski\fg{})   pour   \og   American   Standard   Code   for   Information
Interchange\fg{}  qui  codait 128  caractères  sur  7  bits ce  qui  est
suffisant pour les américains qui n'ont pas de lettres accentuées.

Il  a ensuite  fallu étendre  ce code  pour les  langues  comportant des
caractères  spéciaux  et là,  les  normes  diffèrent,  ce qui  crée  des
problèmes de compatibilité.

Depuis quelques années, le codage  \emph{Unicode} tente de remédier à ce
problème  en codant  tous  les caractères  existant.  C'est le  standard
utilisé sur les systèmes Linux par exemple.

La plupart des langages de programmation ont une commande qui associe le
code  ASCII  (éventuellement étendu)  à  un  caractère.  On pourra  donc
l'utiliser dans les algorithmes généraux.

\begin{table}[h!]
\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\whline
Caractère&  & ! & " & \# & \$ & \% & \& & ' & (  & ) & * & + & , & - & . & / & 0 & 1 & 2 \\
\hline
Code & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\
\hline
\end{tabularx}


\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&3 & 4 & 5 & 6 & 7 & 8 & 9 & : & ; & < & = & > & ? & @ & A & B & C & D & E \\
\hline
Code &51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69\\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère&F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X \\
\hline
Code &70 & 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88\\
\hline
\end{tabularx}





\begin{tabularx}{\linewidth}{Il*{19}{|X}I}
\hline
Caractère& Y & Z & [ & \verb+ \ + & ] & \verb+ ^ + & \verb+ _ + & \verb+ ` + & a & b & c & d & e & f & g & h & i & j & k \\
\hline
Code & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106 & 107 \\
\hline
\end{tabularx}



\begin{tabularx}{\linewidth}{Il*{19}{|X}I}

\hline
Caractère& l & m & n & o & p & q & r & s & t & u & v & w & x & y & z & \{ & | & \} & \verb+~+ \\
\hline
Code & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126\\
\whline
\end{tabularx}
\caption{Table des caractères ASCII affichables}
\end{table}


Les opérateurs  associés permettent les  conversion ASCII. Il  s'agit de
\verb+CHR+ et de \verb+ORD+.

\begin{lstlisting}[caption={}]
PROGRAM conv_ascii;

VAR c : CHAR;
i,min,max : INTEGER;

BEGIN
  WRITE('code inferieur :'); 
  READLN(min);
  WRITE('code superieur :'); 
  READLN(max);

  FOR i:=min TO max DO
      WRITELN(CHR(i), ' -> ',ORD(CHR(i)));
  READLN;
END.          
\end{lstlisting}

\subsubsection{BOOLEAN}

Rien de spécial: tout fonctionne comme sur la plupart des langages.

\begin{lstlisting}[caption={}]
PROGRAM bissextile;

VAR m : INTEGER;
    bis : BOOLEAN;
BEGIN
 WRITE('Entrez un millesime :'); 
 READLN(m);
 bis:= (m>1583) AND ((((m MOD 4)=0) AND ((m MOD 100)<>0)) OR ((m MOD 400)=0));
 WRITELN(bis);
 READLN;
END.            
\end{lstlisting}


\subsubsection{Type ordinal}


Les  types précédemment  étudiés sont  ordinaux  sauf bien  sûr le  type
\verb+REAL+.  On va  donc pouvoir  utiliser les  opérateurs \verb+SUCC+,
\verb+PRED+ et \verb+ORD+:

\begin{lstlisting}[caption={}]
PROGRAM ordinal;
VAR c :  CHAR;

BEGIN
  WRITE ('Entrez un caractere : ');
  READLN (c);
  WRITELN ('Son code ASCII est : ', ORD(c));
  WRITELN ('Son predecesseur est : ', PRED(c));
  WRITELN ('Son successeur est : ', SUCC(c));
  READLN;
END.              
\end{lstlisting}



\subsubsection{STRING}



En  français on parle  de \textit{chaîne  de caractère}.  N'importe quoi
comportant au plus 255 caractères écrits entre deux apostrophes \keystroke{${4}\atop{'\,\{}$} est une
chaîne de caractère. 

Ce  type n'est  pas  ordinal mais  on  peut utiliser  les opérateurs  de
comparaison. C'est l'ordre lexicographique  basé sur les codes ASCII qui
est alors utilisé.

On concatène les chaînes avec \verb|+|.

On obtient le nombre de caractères d'une chaîne avec \verb+length+.

Pour       extraire        une       sous-chaîne,       on       utilise
\verb+copy(mot,début,longueur)+ qui extrait  de la chaîne \verb+mot+ une
sous-chaîne  de longueur  \verb+longueur+ à  partir du  caractère numéro
\verb+début+.

\begin{lstlisting}[caption={}]
PROGRAM  exemple_copy ;

VAR mot : STRING;
      i : INTEGER;

BEGIN
  WRITE('Entrez un mot : ');
  READLN(mot);
  FOR i := 1 TO LENGTH(mot) DO
      WRITELN(COPY(mot,1,i));
  READLN
END.             
\end{lstlisting}


On peut transformer un nombre en chaîne avec \verb+STR(nombre,chaîne)+.

Par exemple \verb+STR(112,ch)+ place  dans la chaîne \verb+ch+ la chaîne
\verb+112+.

Comme pour \verb+WRITE+, on peut régler le format de la chaîne image.

Par exemple, \verb+STR(1.23e3:6:1,ch)+  placera dans \verb+ch+ la chaîne
\verb+ 1230.0+.

L'opération          inverse          de         \verb+STR+          est
\verb+VAL(chaîne,nombre,indicateur)+ où  \verb+indicateur+ vaut 0  si la
conversion s'est  bien passée  et sinon indique  la position  du premier
caractère de la chaîne qui a posé problème.

Pour  accéder  au  i-ème  caractère  d'une chaîne  \verb+ch+,  on  entre
classiquement \verb+ch[i]+.

Pour localiser la position d'une sous-chaîne dans une chaîne, on utilise:

\verb+POS(sous-chaîne,chaîne)+.  Le  nombre  renvoyé  sera  le  rang  où
commence la sous-chaîne. Si la chaîne ne contient pas la sous-chaîne, le
nombre renvoyé sera 0.

Pour supprimer une sous-chaîne d'une chaîne, on utilise:

\verb+DELETE(chaîne,début,longueur)+ qui efface une sous-chaîne de longueur
\verb+longueur+ à partir du caractère numéro \verb+début+.



\subsubsection{ARRAY}

C'est un tableau d'une ou  plusieurs lignes de longueur fixe constituées
d'éléments du même type.

Par exemple:

\begin{lstlisting}[caption={}]
PROGRAM ex_array;

TYPE Vecteur = ARRAY[1..3] OF REAL;
VAR V : Vecteur;
    i : BYTE;

BEGIN
  WRITELN('Entrez les coordonnees du vecteur : ');
  FOR  i:=1 TO 3 DO READLN(V[i]);
  WRITELN('Son abscisse est : ',V[1]:2:1);
  WRITELN('Son ordonnee est : ',V[2]:2:1);
  WRITELN('Sa cote est : ',V[3]:2:1);
  WRITELN('Sa norme est environ : ',sqrt(sqr(V[1])+ sqr(V[2])+sqr(V[3])):2:2);
  READLN
END.                 
\end{lstlisting}

Voici maintenant un exemple de tableau contenant plusieurs lignes:

\begin{lstlisting}[caption={}]
PROGRAM ex_array2;

TYPE Matrice = ARRAY[1..2,1..2] OF SINGLE;
VAR M   : Matrice;
    i,j : BYTE;
    determinant : SINGLE;

BEGIN
  WRITELN('Entrez les coordonnees des deux vecteurs : ');
  FOR  i:=1 TO 2 DO
    FOR j:=1 TO 2 DO READLN(M[i,j]);

  determinant:=M[1,1]*M[2,2]-M[1,2]*M[2,1];
  IF determinant=0 THEN
     WRITELN('Les vecteurs sont colineaires.')
  ELSE
     WRITELN('Les vecteurs ne sont pas colineaires.');
     WRITELN('Leur determinant vaut : ',determinant:2:1);
  READLN
END.                 
\end{lstlisting}


\subsubsection{RECORD}


Ce type permet  de créer des sortes de tableaux  dont les lignes peuvent
être de longueurs et de types différents:


\begin{lstlisting}[caption={}]
PROGRAM ex_record;

TYPE Jour = WORD;
     Mois = (Janvier,Fevrier,Mars,Avril,Mai,Juin,Juillet,Aout,Septembre,Octobre,Novembre,Decembre);
     Date = RECORD
       day : 1..31;
       month : Janvier..Decembre;
       year : WORD;
     END;

VAR  d : Date;

BEGIN
  WRITELN('Entrez le jour : ');
  READLN(d.day);
  WRITELN('Entrez le mois : ');
  READLN(d.month);
  WRITELN('Entrez l annee : ');
  READLN(d.year);
  WRITELN('La date est le : ',d.day,'/',ORD(d.month)+1,'/',d.year);
  READLN
END.   
\end{lstlisting}
 

\subsubsection{SET}


Il  s'agit   de  collections  non  ordonnée:  des   ensembles  au  sens
mathématique du terme.

On peut  les déclarer à l'aide  de \verb+SET+ ou  d'une collection entre
crochets.

\begin{lstlisting}[caption={}]
CONST chiffres : SET OF CHAR = [0..9];
CONST voyelles = ['a', 'e', 'i', 'o', 'u', 'y'];
TYPE lettres = SET OF CHAR;
\end{lstlisting}


On peut  réunir des ensembles  avec \verb|+|, obtenir  leur intersection
avec \verb+*+, leur différence avec \verb+-+.
On peut également les comparer à l'aide de \verb+=+ pour l'égalité et de
\verb+<=+ pour l'inclusion ou \verb+>=+.

\subsection{Priorité des opérateurs}

Dans le doute, on met autant  de paires de parenthèses que l'on souhaite
mais il faut savoir que PASCAL suit l'ordre suivant:

\begin{enumerate}
\item L'opérateur unaire \verb+-+ qui représente le passage à l'opposé;
\item \verb+NOT+;
\item \verb+* / DIV MOD AND+;
\item \verb|+ - OR XOR|;
\item \verb+= < <= > >= <> IN+
\end{enumerate}

\subsection{Structures conditionnelles}


Vous connaissez le fameux \verb+IF...THEN...ELSE+.

Il existe aussi l'instruction \verb+CASE+:

\begin{lstlisting}[caption={}]
PROGRAM example_case;

VAR n : INTEGER;
 
BEGIN
 WRITE(' entrez un nombre entier : ');
 READLN(n);
  CASE n OF
     0,1,2 : WRITELN('peut mieux faire');
     3..10 : WRITELN('insuffisant');
     11..17: WRITELN('pas mal');
  ELSE
     WRITELN('correct');
  END;
 READLN;
END.                      
\end{lstlisting}


\subsection{Structures de répétition}


\subsubsection{FOR}

La structure est globalement \verb+FOR...TO...DO...+.

Cependant,   il   y  a   quelques   petites  particularités   concernant
l'incrémentation.

Voici trois exemples parlant d'eux-mêmes:

\begin{lstlisting}[caption={}]
PROGRAM pour1;

VAR c : CHAR;

BEGIN
  FOR c:= 'a' TO 'z' DO
      WRITE(c);
  READLN
END.        
\end{lstlisting}

Puis:

\begin{lstlisting}[caption={}]
PROGRAM pour2;

VAR c : CHAR;

BEGIN
  FOR c:= 'Z' DOWNTO 'A' DO
      WRITE(c);
  READLN
END.   
\end{lstlisting}


Et enfin:

\begin{lstlisting}[caption={}]
PROGRAM pour3;

VAR i,n : INTEGER;

BEGIN
  i:=66;
  FOR n:= 1 TO 13 DO
      BEGIN
       WRITE(CHR(i),'-');
       i:=i+2;
      END;
  WRITE('fin');
  READLN
END.           
\end{lstlisting}


\subsubsection{WHILE}

La syntaxe est \verb+WHILE...DO...+ sans surprise.


\begin{lstlisting}[caption={}]
PROGRAM tantque;
VAR i : INTEGER;
BEGIN
  i:=66;
  WHILE i<=90 DO
      BEGIN
       WRITE(CHR(i),'-');
       i:=i+2;
      END;
  WRITELN('fin');
  WRITELN('i vaut maintenant ', i);
  READLN
END.
\end{lstlisting}




\subsubsection{REPEAT}

Une petite nouveauté dont la syntaxe est \verb+REPEAT...UNTIL...+ et qui
ressemble à \verb+WHILE+ avec cependant une petite différence:



\begin{lstlisting}[caption={}]
PROGRAM repete1;
VAR i : INTEGER;
BEGIN
  i:=66;
  REPEAT
       BEGIN
       WRITE(CHR(i),'-');
       i:=i+2 ;
       END;
  UNTIL i>90;
  WRITELN('fin');
  WRITELN('i vaut maintenant', i);
  READLN
END.          
\end{lstlisting}

On l'utilise souvent lorsqu'on ignore a priori le
nombre de répétitions:


\begin{lstlisting}[caption={}]
PROGRAM repete2;
VAR i : INTEGER;
BEGIN
  REPEAT
       BEGIN
       WRITELN('Entrez un nombre positif : ');
       READLN(i);
       WRITELN('Merci, c est gentil');
       END
  UNTIL i>10;
  WRITELN('C est fini maintenant');
  READLN
END.                     
\end{lstlisting}



\subsection{Types définis par l'utilisateur}

\subsubsection{Types énumérés}

\begin{lstlisting}[caption={}]
PROGRAM type_ord;

TYPE couleur=(trefle,carreau,coeur,pique);
VAR carte : couleur;

BEGIN
  FOR carte := trefle TO pique DO
    BEGIN
      IF (carte=trefle) OR (carte=pique)
      THEN WRITELN('Une carte de ',carte,' est noire.')
      ELSE WRITELN('Une carte de ',carte,' est rouge.')
    END;
  READLN
END.                  
\end{lstlisting}


\begin{lstlisting}[caption={}]
PROGRAM type_ord2;

TYPE jour=(lundi,mardi,mercredi,jeudi,vendredi,samedi,dimanche);
VAR date : jour;

BEGIN
  FOR date := lundi TO samedi DO
    BEGIN
      WRITE('Le ',date,' est le ',ORD(date)+1, 'e jour de la semaine.');
      WRITELN(' Il est suivi par ',SUCC(date),'.');
    END;
  READLN
END.          
\end{lstlisting}


\begin{lstlisting}[caption={}]
PROGRAM type_ord3;

TYPE jour=(lundi,mardi,mercredi,jeudi,vendredi,samedi,dimanche);
      boulot=lundi..vendredi;
VAR date : boulot;

BEGIN
  FOR date := boulot(0) TO boulot(4) DO
    BEGIN
      WRITELN('Le ',date,' est le ',ORD(date)+1, 'e jour de boulot de la semaine.');
    END;
  READLN
END.  
\end{lstlisting}



\subsection{Récursion}

\begin{flushright}
\begin{quote}{\large\slshape 
Définition: si vous ne comprenez toujours pas le sens du mot \og \textit{récursion}\fg{},
relisez cette phrase.}
\end{quote}
\end{flushright}


Voici un exemple qui illustre l'enchaînement des calculs:


\begin{lstlisting}[caption={}]
PROGRAM facto1;

VAR k : WORD;

FUNCTION fac ( n: INT64) : INT64;
BEGIN
  WRITELN('*** entree dans fac ; n= ',n);
  IF n=1 THEN fac:=1
  ELSE fac:=n*fac(n-1);
  WRITELN('--- sortie de fac ; n= ', n, ' et fac = ',fac);
END;

BEGIN
  WRITELN('Entrez l entier : ');
  READLN(k);
  WRITELN('Voici les etapes de calcul de ',k,'!');
  WRITELN(fac(k) );
  READLN
END.         
\end{lstlisting}


\section{Correction et terminaison d'un algorithme}

Cela  correspond à  la \textit{démonstration}  en mathématique.  Nous ne
ferons que survoler ces notions de \textit{génie logiciel} dans des cas simples.


Nous abuserons du résultat suivant:

  \begin{theoreme}[Suite strictement décroissante d'entiers naturels]
    Toute  suite strictement  décroissante  d'entiers naturels  converge
    vers 0.
    \end{theoreme}


Toutes nos preuves reprendront ce principe qui peut en fait être
généralisé  à un ensemble  muni d'une  relation d'ordre:  sous certaines
conditions (toute partie non vide admet un élément minimal) on parle d'\textit{ordre bien fondé}.

\subsection{Algorithmes impératifs}

La notion  centrale est l'\textit{\bf  invariance de boucle}.  Une étude
plus approfondie nécessite l'étude de  la logique des prédicats qui sera
menée en deuxième année.


Un \textbf{\it invariant de boucle} est une propriété qui est vraie:
\begin{itemize}
\item  avant
d'entrer dans la boucle (avant la première itération);
\item à chaque nouvelle itération;
\item en sortie de boucle.
\end{itemize}


Par exemple, considérons un programme de calcul de somme:

\begin{lstlisting}[caption={}]
PROGRAM calcul_somme;

VAR Nmax,n,S : QWORD;

BEGIN
WRITE('Entrez l entier superieur :');
READLN(Nmax);
 n:=0;
 S:=0;
 WHILE n<=Nmax DO
   BEGIN
    S:=S+n;
    n:=n+1
   END;
WRITE('La somme des ',Nmax,' premiers entiers naturels vaut ',S);
READLN
END. 
\end{lstlisting}


Soit la propriété $\mathfrak{p}(n):$  \og après $n$ itérations de
la boucle, la valeur de $S$ est $\displaystyle\sum_{k=0}^{n}k$ et $n \leqslant N$\fg{}.


La  preuve par  récurrence est  assez immédiate.  L'algorithme  est donc
\textit{correct}.

Occupons-nous  maintenant  de sa  \textit{terminaison}.  En général,  ce
problème est  indécidable (on ne peut  pas répondre par  \og oui\fg{} ou
\og non\fg{}).  Mais dans  certains cas, on  peut définir  une condition
suffisante  de  terminaison: il  s'agit  de  déterminer  une fonction  à
valeurs entières,  dont les variables  sont celles de  l'algorithme, qui
soit strictement monotone,  bornée et dont les valeurs  sont atteintes à
chaque itération.

En général, c'est la fonction qui définit le nombre d'itérations restant
à effectuer.

Par exemple, dans le cas précédent, ce pourrait être la fonction F:

$$F\colon (S,N,n)\longmapsto N-n$$

qui est strictement décroissante, à valeurs entières et bornée par 0.

\subsection{Algorithmes récursifs}

\subsubsection{Généralités}


Le principe  est un peu le  même mais on parle  cette fois l'\textit{\bf
  invariant d'appel récursif}.

Reprenons le cas de la somme:

\begin{lstlisting}[caption={}]
PROGRAM calcul_somme_rec;

VAR Nmax: QWORD;

FUNCTION som_ent(n:QWORD):QWORD;
  BEGIN
    IF n=0 THEN som_ent:=0
    ELSE som_ent:=som_ent(n-1)+n
  END;

BEGIN
WRITE('Entrez l entier superieur : ');
READLN(Nmax);
WRITE('La somme des ',Nmax,' premiers entiers naturels vaut ',som_ent(Nmax));
READLN
END.                    
\end{lstlisting}

La         propriété          $\mathfrak{P}(n)$         est:         \og
\verb+som_ent(n)+$=\displaystyle\sum_{k=0}^{n}k$\fg{}.

La preuve par récurrence est assez immédiate.


Pour ce  qui est de  la terminaison, le  principe est toujours  le même;
cependant,  dans la plupart  des cas,  la fonction  à exhiber  sera plus
immédiate et ne  dépendra que de $n$. Ici,  c'est clairement la fonction
$\mathfrak{Id}_{\bbn}\colon n\mapsto n$ qui est strictement décroissante
et minorée par 0.

\begin{DANGER}
  Attention! Ne  pas trouver de fonction  F convenant ne  prouve pas que
  l'algorithme ne termine pas. C'est  le cas par exemple de l'algorithme
  de Syracuse au sujet duquel on ne sait toujours pas conclure:

\begin{algo}
\FUNC{syracuse}{%
\pfarg{n}{entier naturel}}{entier naturel}
\BEGIN
\IF{n<>1}
\IF{n est pair}
\RETURN{syracuse(n/2)}
\ELSE
\RETURN{syracuse(3*n+1)}
\ENDIF
\ELSE
\RETURN{1}
\ENDIF
\END
\end{algo}

\end{DANGER}

\subsubsection{Algorithme récursif terminal}

On appelle  ainsi les  algorithmes dont l'appel  récursif ne  figure pas
comme argument ni de l'appel lui-même ni d'une autre fonction.

Dans  le  cas  précédent  du   calcul  de  somme,  l'appel  récursif  de
\verb+som_ent+ était \textit{enrobé} dans la fonction $F\colon (X,Y) \mapsto X+Y$.

On avait en effet \verb+som_ent(n):=F(som_ent(n-1),n)+.

On peut transformer un peu l'algorithme pour le rendre terminal:

\begin{lstlisting}[caption={}]
PROGRAM calcul_somme_term;

VAR Nmax: QWORD;

FUNCTION somme(n:QWORD):QWORD;
 FUNCTION som_ent(x,y:QWORD):QWORD;
   BEGIN
    IF x=n THEN som_ent:=y
    ELSE som_ent:=som_ent(x+1,y+x+1)
   END;
  BEGIN
   somme:=som_ent(0,0)
  END;

BEGIN
 WRITE('Entrez l entier superieur : ');
 READLN(Nmax);
 WRITE('La somme des ',Nmax,' premiers entiers naturels vaut ',somme(Nmax));
 READLN
END.              
\end{lstlisting}


Cependant, sur Pascal,  cela ne change rien. Ce  n'est efficace que dans
le cas d'un langage moderne et fonctionnel comme par exemple CAML...

Occupons-nous cependant de la preuve de la correction et de la terminaison de cet
algorithme qui est moins triviale que la précédente.

L'appel      de       \verb+somme(n)+      déclenche      l'appel      de
\verb+som_ent(0,0)+. Notons $(x_i,y_i)_{i\in\bbn}$  la suite des couples
d'arguments     passés    à     \verb+som_ent+    suite     à    l'appel
\verb+som_ent(0,0)+. On a $(x_0,y_0)=(0,0)$.

On peut démontrer que  $(x_i,y_i)=(i,S_i)$ pour tout entier naturel $i$,
avec $S_i=\displaystyle\sum_{k=0}^{i}k$ par récurrence (faites-le!).

Pour  prouver  la  terminaison,  on  montre que  la  fonction  $F\colon
i\mapsto  n-i$ est  strictement  décroissante tout  au  long des  appels
récursifs, à valeurs entières et minorée par 0.


\section{Récursion mutuelle}



On peut définir la parité d'un entier ainsi:

\begin{itemize}
\item 0 est pair;
\item $n$ est pair signifie que $n-1$ est impair;
\item 1 est impair;
\item $n$ est impair signifie que $n-1$ est pair.
\end{itemize}

On parle de récursion mutuelle  car la parité et l'imparité sont définie
récursivement l'une en fonction de l'autre.

Sur PASCAL, le mot magique est \verb+FORWARD+:

\begin{lstlisting}[caption={}]
PROGRAM mutuelle_rec;

VAR n:WORD;

FUNCTION impair(n:WORD):BOOLEAN; FORWARD;

FUNCTION pair(n:WORD):BOOLEAN;
BEGIN
  IF n=0
  THEN pair:=TRUE
  ELSE pair:=impair(n-1)
END;

FUNCTION impair(n:WORD):BOOLEAN;
BEGIN
  IF n=0
  THEN impair:=FALSE
  ELSE impair:=pair(n-1)
END;

BEGIN
  WRITE('Entrez un entier naturel : ');
  READLN(n);
  IF pair(n)
  THEN WRITELN(n, ' est pair.')
  ELSE WRITELN(n, ' est impair.');
  READLN
END.                                      
\end{lstlisting}

\section{Diviser pour régner}


\vfill

\eject


\modeexercice % entre en mode exercice
\section{EXERCICES}


\begin{listeexercices}

  \begin{exercice}[L'addition n'est plus associative ?!]
    Pour          tout           $p\in\bbn^*$,          on          pose
    $S_p=\displaystyle\sum_{n=1}^{p}\frac{1}{n^3}$.

Écrire deux fonctions calculant une  valeur approchée de $S_p$, l'une en
accumulant les  termes suivant les  valeurs croissantes de  $n$, l'autre
suivant les valeurs décroissantes de $n$. Comparez les résultats obtenus
pour diverses valeurs de $p$ en utilisant pour les valeurs des sommes le
type \verb+SINGLE+ puis le type \verb+DOUBLE+.

Sur un logiciel de calcul formel on obtient:
$$S_{10^{15}}\approx 1,20205690315959428539973816151$$
  \end{exercice}


  \begin{exercice}[Suite de Syracuse]
On  attend   toujours  la   preuve  de  la   convergence  de   la  suite
$(a_n)_{n\in\bbn}$ définie par:

$$
a_0=a\quad \text{et}\quad \forall n\in\bbn\quad a_{n+1}=
\begin{cases}
  \frac{a_n}{2}\quad \text{si } n \text{ est pair}\\
3a_n+1\quad\text{sinon}
\end{cases}
$$

Déterminez  des programmes  recevant comme  paramètre la  valeur  $a$ et
affichant la séquence des $a_n$ jusqu'au premier égal à 1.

Déterminez un programme renvoyant le plus petit $n$ tel que $a_n=1$ pour
un $a$ donné.

Déterminez   la    ou   les    valeur(s)   de   $a$    sur   $\llbracket
1;\numprint{10000}\rrbracket$  telle(s) que  le  plus petit  $n$ tel  que
$a_n=1$ soit maximal.
  \end{exercice}



  \begin{exercice}[Triangle de Pascal]
Affichez un  triangle de \textsc{Pascal} en  n'utilisant comme opération
arithmétique que des additions.

On obtiendra par exemple:

\begin{verbatim}
Indiquez le nombre de lignes  : 6

    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1
    1    5   10   10    5    1
\end{verbatim}

Modifiez  légèrement le  programme précédent  en remplaçant  les nombres
impairs  par  une   étoile  \verb+*+  et  les  nombres   pairs  par  une
espace. Qu'observez-vous pour 64 lignes par exemple ?


  \end{exercice}



  \begin{exercice}[Crible d'Ératosthène]

C'est  comme  au  collège:  vous  prenez les  premiers  nombres  entiers
naturels  et vous  rayez  les multiples  de  2, de  3,  etc. jusqu'à  ne
conserver que les nombres premiers.

Inspirez-vous de cette idée pour  obtenir une liste des entiers premiers
entre 2 et  un entier $n$ donné ainsi que  le nombres d'entiers premiers
inférieurs à $n$ (on note souvent ce nombre $\pi(n)$).
  \end{exercice}

  \begin{exercice}[Les tours de Hanoi]
    

% %\begin{figure}
% \begin{center}
%   \includegraphics[height=5cm]{Hanoi}
% \end{center}
% %\end{figure}

Nous  en  avons  déjà  parlé.  Vous pouvez  observer  la  résolution  du
problème à quatre disques à cette adresse \href{http://www.youtube.com/watch?v=aGlt2G-DC8c}{http://www.youtube.com/watch?v=aGlt2G-DC8c}

La situation de départ est la suivante:

%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{hanoi4}
\end{center}
%\end{figure}


Vous  pouvez montrer  que le  nombre minimum  de coups  pour  bouger $n$
disques suit la relation de récurrence:

$$C_0=0, \ \forall n\in\bbn^*,\ C_n=2C_{n-1}+1$$

Déterminez un programme utilisant  une fonction récursive pour détailler
chaque  coup  permettant  de  résoudre  le problème  à  $n$  disques  en
indiquant également le nombre total de coups.

  \end{exercice}



  \begin{exercice}[Conversions d'entiers]
Déterminez un programme convertissant un entier dans une base quelconque
(entre 2 et 10).

Vous en donnerez une version impérative et une version récursive.
  \end{exercice}



  \begin{exercice}[Analyse de fonctions récursives]
Commentez les fonctions suivantes:

\begin{lstlisting}[caption={}]
FUNCTION facto(n:WORD):WORD;
BEGIN
 IF n=0 
 THEN facto:=1
 ELSE facto:=facto(n+1)/(n+1)
END;
\end{lstlisting}


\begin{lstlisting}[caption={}]
FUNCTION Gibbs(a,b:WORD):WORD;
BEGIN
  IF a=0
  THEN Gibbs:=1
  ELSE Gibbs:=Gibbs(a-1,Gibbs(a,b))
END;
\end{lstlisting}
  \end{exercice}



  \begin{exercice}[Récursion multiple (e3a 2009)]


On  se  donne deux  entiers  $k\in\bbz$  et  $n\in\bbn$. Le  coefficient
binomial associé à ces deux entiers est:

$$
{n \choose k}=
\begin{cases}
  \frac{n!}{k!(n-k)!}\ \text{ si }\ 0 \leqslant k \leqslant n\\
0 \ \text{ sinon}
\end{cases}
$$

On a alors la formule de \textsc{Pascal}:

$$\forall n  \geqslant 1,\ \forall k\in\bbz,\  {n\choose k}={n-1 \choose
  k-1}+{n-1 \choose k}$$

\begin{enumerate}
\item \textit{Dans  cette question, on n'utilisera ni  liste, ni tableau
    et  la seule  opération  arithmétique autorisée  est l'addition;  on
    n'effectuera  donc  aucune   multiplication.}  Écrire  une  fonction
  récursive simple calculant le coefficient ${n\choose k}$.
\item On pose $n=\numprint{1000}$ et on souhaite construire un tableau t
  de longueur  $n+1$ tel  que si $k\in\llbracket  0,n\rrbracket$, t[$k$]
  contient la valeur de ${n\choose k}$.
  \begin{enumerate}
  \item Expliquez  brièvement pourquoi il n'est  pas possible d'utiliser
    la fonction de la question précédente.
\item Écrire un programme renvoyant le tableau convenablement rempli.
  \end{enumerate}
\end{enumerate}

  \end{exercice}


  \begin{exercice}[Racine carrée entière (e3a 2009)]
    On  s'intéresse  au  problème  suivant:  étant donné  un  entier  $n
    \geqslant  1$, on  souhaite déterminer  un entier  positif  $s_n$ de
    sorte que $s_n$ soit  \og proche\fg{} de $\sqrt{n}$. Nous étudierons
    différentes  approches pour résoudre  ce problème.  On se  donne les
    contraintes suivantes:
    \begin{enumerate}
    \item on ne travaillera qu'avec des entiers relatifs;
\item les opérations arithmétiques autorisées sur les entiers sont:
  \begin{enumerate}
  \item l'addition de deux entiers $a$ et $b$: \verb|a+b|;
  \item la soustraction de deux entiers $a$ et $b$: \verb+a-b+;
  \item la multiplication de deux entiers $a$ et $b$: \verb+a*b+;
  \item la  division euclidienne d'un  entier positif $a$ par  un entier
    strictement  positif $b$:  le reste  de la  division est  obtenu par
    \verb+a MOD b+ et le quotient par \verb+a DIV b+.
  \end{enumerate}
    \end{enumerate}
Dans  la  suite,  si $a$  et  $b$  sont  deux  entiers avec  $b_neq  0$,
l'écriture $\frac{a}{b}$  désigne le quotient  \textbf{rationnel} de $a$
par  $b$; si  $x$  est un  réel,  $\lfloor x\rfloor$  désigne la  partie
entière de $x$  et $\lceil x \rceil$ désigne le plafond  de $x$: le plus
petit entier supérieur ou égal à $x$.

\begin{enumerate}
\item \textbf{Algorithme naïf}

Dans cette partie,  étant donné un entier $n \geqslant  1$, on cherche à
déterminer le plus grand entier  $s_n$ tel que $s_n^2 \leqslant n$. Pour
cela, on passe en revue les entiers 1, 2, 3,... jusqu'à trouver $s_n$.
\begin{enumerate}
\item Écrire  une fonction \verb+isqrt_naif+ prenant $n$  en argument et
  renvoyant la valeur $s_n$ en utilisant le principe ci-dessus.
\item Déterminer la complexité de votre programme.
\end{enumerate}

\item \textbf{Une méthode dichotomique}

Dans cette partie, on reprend  le problème de la partie précédente. Afin
d'obtenir  une  méthode  plus  efficace,  on  considère  le  programme
suivant:

\begin{lstlisting}[caption={}]
FUNCTION isqrt(n:LONGINT):LONGINT;
  VAR x,y,z:LONGINT;
  BEGIN
    x:=1; y:=n;
    WHILE (y-x>1) DO
      BEGIN
       z:=(x+y) DIV 2;
       IF z*z>n THEN
         y:=z
       ELSE
         x:=z
      END;
    isqrt:=x
  END;           
\end{lstlisting}


Si $k \geqslant 1$, on note $x_k$ et $y_k$ les valeurs des variables $x$
et $y$  à la fin de la  $k$-eme itération de la  boucle \verb+WHILE+. On
convient que $x_0=1$ et $y_0=n$.

\begin{enumerate}
\item  Expliciter les  exécutions  du programme  ci-dessus sur  l'entier
  15. (On  donnera en particulier les valeurs  successives des variables
  $x$, $y$ et $z$.)

\item Démontrer la terminaison du programme.
\item Justifier la correction du programme.
\item
  \begin{enumerate}
  \item Prouver l'inégalité suivante:
$$y_k-x_k \leqslant \frac{y_0-x_0-1}{2^k}+1$$
\item En déduire une majoration de la complexité du programme.
  \end{enumerate}
\item Réécrire la fonction \verb+isqrt+ en utilisant de la récursivité.

\end{enumerate}



\end{enumerate}

  \end{exercice}



  \begin{exercice}[Nombres d'Armstrong (e3a 2008)]
Un nombre  d'\textsc{Armstrong} est un  nombre qui est égal  à la somme
des cubes des  chiffres de son écriture en base 10;  par exemple 153 est
un  nombre  d'\textsc{Armstrong}  puisque $153=1^3+5^3+3^3$.  Écrire  un
programme qui calcule tous  les nombres d'\textsc{Armstrong} de trois ou
quatre chiffres.
    
  \end{exercice}


  \begin{exercice}[Nombres parfaits (e3a 2007)]
Soit $n$ un entier naturel. On dit que $n$ est un nombre parfait si $2n$
est  la  somme des  entiers  naturels  diviseurs  de $n$.  Par  exemple,
l'entier 6 est un nombre parfait puisque $2\cdot 6=12=6+3+2+1$.

Écrire un programme qui détermine la liste des nombres parfaits $n$ tels
que $n \leqslant \numprint{9999}$.
  \end{exercice}



  \begin{exercice}[Persistance (e3a 2007)]
Un entier naturel $n$ étant  donné, on calcule le produit \verb+prod(n)+
de  ses chiffres  dans  son écriture  en  base 10  puis  le produit  des
chiffres  de  \verb+prod(n)+ et  on  recommence  ainsi l'application  de
\verb+prod+ jusqu'à obtenir  un chiffre entre 0 et  9. Le nombre minimal
de fois  où on applique \verb+prod+  pour transformer $n$  en un chiffre
entre 0 et 9 est appelé  la \textit{persistance} de $n$. Par exemple, la
persistance  de  9 est  égale  à  0,  celle de  97  est  égale à  3  car
\verb+prod+$(97)=9\cdot     7=63$,     \verb+prod+$(63)=6\cdot    3=18$,
\verb+prod+$(18)=1\cdot 8=8$. et celle  de $\numprint{9575}$ est égale à
5.

Écrire  un  programme  qui  calcule  le plus  petit  entier  naturel  de
persistance 5.
  \end{exercice}


\end{listeexercices}


\vfill

\eject
\section{DES SOLUTIONS}


\begin{listeexercices}

\pasc


  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_1;

TYPE Reel = SINGLE;
     Entier=LONGWORD;
VAR k : Entier;

FUNCTION terme ( n: Entier) : Reel;
BEGIN
  terme:=1/(n*n*n)
  END;

FUNCTION som_cr(p:Entier):Reel;
 VAR s:Reel;
    n:Entier;
BEGIN
 s:=0;
 FOR n:=1 TO p DO s:=s+terme(n);
 Som_cr:=s;
END;

FUNCTION som_dec(p:Entier):Reel;
 VAR s:Reel;
    n:Entier;
BEGIN
 s:=0;
 FOR n:=p DOWNTO 1 DO s:=s+terme(n);
 Som_dec:=s;
END;

BEGIN
  WRITELN('Entrez le terme max : ');
  READLN(k);
  WRITELN('Somme_croissante(',k,') = ',som_cr(k));
  WRITELN('Somme_decroissante(',k,') = ',som_dec(k));
  READLN
END.                                                    
    \end{lstlisting}
  \end{exercice}



  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_2_a;

VAR a:LONGWORD;

PROCEDURE  Syracuse(a:LONGWORD);
VAR u : LONGWORD;
BEGIN
  u:=a;
  WHILE u<>1 DO
    BEGIN
      WRITE(u:5);
      IF ODD(u)
         THEN u:=3*u+1
         ELSE u:=u DIV 2;
    END;
  WRITELN(1:5)
END;

BEGIN
 WRITE('Entrez le premier terme : ');
 READLN(a);
 Syracuse(a);
 READLN
END.                               
    \end{lstlisting}


    \begin{lstlisting}[caption={}]
PROGRAM exo1_2_b;

VAR nmax,a,n : WORD;

FUNCTION  Premier_Syracuse(a:LONGWORD):WORD;
VAR u : LONGWORD;
    n : WORD;
BEGIN
  n:=0;
  u:=a;
  WHILE u<>1 DO
    BEGIN
      n:=n+1;
      IF ODD(u)
         THEN u:=3*u+1
         ELSE u:=u DIV 2;
    END;
  Premier_Syracuse:=n
END;

BEGIN
 nmax:=0;
 FOR a:=1 TO 10000 DO
   BEGIN
     n:=Premier_Syracuse(a);
     IF n>=nmax THEN
       BEGIN
         nmax:=n;
         WRITELN(a,'->',n)
       END;
   END;
 READLN
END.                                               
    \end{lstlisting}


  \end{exercice}



  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_3;

CONST Nmax=15;
TYPE Entier=LONGWORD;
VAR nl : Entier; {nb de lignes}
     i : Entier; {indice de ligne}
     j : Entier; {indice de colonne}
     T : ARRAY[0..Nmax-1,0..Nmax-1] OF Entier; {Le tableau contenant le triangle}


BEGIN
  WRITE('Indiquez le nombre de lignes  : ');
  READLN(nl);
  WRITELN;
  WRITELN;
  T[0,0]:=1;
  WRITELN(T[0,0]:5);
  FOR i:=1 TO nl-1 DO
    BEGIN
      T[i,i]:=1;
      T[i,0]:=1;
      WRITE(T[i,0]:5);
      FOR j:=1 TO i-1 DO
        BEGIN
          T[i,j]:=T[i-1,j]+T[i-1,j-1];
          WRITE(T[i,j]:5);
        END;
      WRITELN(T[i,i]:5);
    END;
  READLN
END.
    \end{lstlisting}



    \begin{lstlisting}[caption={}]
PROGRAM exo1_3_b;

CONST Nmax=65;
TYPE Entier=LONGWORD;
VAR nl : Entier; {nb de lignes}
     i : Entier; {indice de ligne}
     j : Entier; {indice de colonne}
     T : ARRAY[0..Nmax-1,0..Nmax-1] OF Entier; {Le tableau contenant le triangle}


BEGIN
  WRITE('Indiquez le nombre de lignes  : ');
  READLN(nl);
  WRITELN;
  WRITELN;
  T[0,0]:=1;
  WRITELN('*');
  FOR i:=1 TO nl-1 DO
    BEGIN
      T[i,i]:=1;
      T[i,0]:=1;
      WRITE('*');
      FOR j:=1 TO i-1 DO
        BEGIN
          T[i,j]:=T[i-1,j]+T[i-1,j-1];
          IF ODD(T[i,j])
            THEN WRITE('*')
            ELSE WRITE(' ')
        END;
      WRITELN('*');
    END;
  READLN
END.                                          
    \end{lstlisting}


  \end{exercice}




  \begin{exercice}


    \begin{lstlisting}[caption={}]
PROGRAM exo1_4;

CONST Nmax=1000000;
TYPE tableau = ARRAY[1..Nmax]  OF LONGWORD;
VAR N,k,naff:LONGWORD;
    raye : tableau;

PROCEDURE erato;
VAR i,k    : LONGWORD;
BEGIN
  FOR i:=1 TO Nmax DO raye[i]:=i;
  raye[1]:=0;
  i:=2;
  WHILE i*i<=Nmax DO
    BEGIN
      IF raye[i]>=1 THEN
        BEGIN
         FOR k:=2 TO Nmax DIV i DO
          raye[i*k]:=0
        END;
      i:=i+1
    END;
END;

BEGIN
  naff:=0;
  WRITE('Entrez l entier maximum : ');
  READLN(N);
  erato;
  WRITELN;
  WRITELN('Les nombres premiers inferieurs a ',N,' sont :');
  WRITELN;
  FOR k:=1 TO N DO
    BEGIN
      IF raye[k]>0 THEN
        BEGIN
         WRITE(k:5);
         naff:=naff+1;
         IF (naff MOD 15 = 0) THEN WRITELN
        END;
    END;
WRITELN;
WRITELN;
WRITELN;
WRITELN('Il y a ',naff,' nombres premiers inferieurs a ',N);
READLN
END. 
    \end{lstlisting}

  \end{exercice}
 
%1.5

 \begin{exercice}
   \begin{lstlisting}[caption={}]
PROGRAM exo1_5;

USES crt;

VAR n,i : WORD;
    A,B,C : STRING;

PROCEDURE  deplace(x,y:STRING);
BEGIN
  i:=i+1;
  WRITE('Deplacez le disque en ',x,' sur le piquet ',y);
  READLN
END;

PROCEDURE hanoi(n:WORD;A,B,C:STRING);
BEGIN
  IF n=1
    THEN
     deplace(A,C)
    ELSE
     BEGIN
      hanoi(n-1,A,C,B);
      deplace(A,C);
      hanoi(n-1,B,A,C);
     END
END;

BEGIN
  i:=0;
  A:='A';B:='B';C:='C';
  WRITE('Combien de disques : ');
  READLN(n);
  hanoi(n,A,B,C);
  WRITELN('Et voila ! Les disques ont ete deplaces en ',i,' coups.');
  READLN
END. 
   \end{lstlisting}
  \end{exercice}

%1.6


  \begin{exercice}

En impératif:

    \begin{lstlisting}[caption={}]
PROGRAM exo1_6a;

CONST NbChifMax = 63;

VAR n : QWORD; {Nombre a convertir}
    quotient : QWORD;
    reste : QWORD;
    b : BYTE; {base}
    conv : ARRAY[1..NbChifMax] OF BYTE; {nombre converti sous forme de liste}
    NbChif : BYTE; {Nombre effectif de chiffres}
    i : WORD; {indice}

BEGIN
  {--- lecture des donnees ---}
  WRITE('Entrez le nombre a convertir : ');
  READLN(n);
  WRITE('ENtrez la base voulue (entre 2 et 10) : ');
  READLN(b);
  {--- conversion ---}
  NbChif:=1;
  reste:= n MOD b;
  quotient:= n DIV b;
  conv[NbChif]:=reste;
  WHILE quotient>0 DO
     BEGIN
      reste:=quotient MOD b;
      quotient:=quotient DIV b;
      NbChif:=NbChif+1;
      conv[NbChif]:=reste;
     END;
  {--- resultat ---}
  WRITE(n, ' en base ',b,' : ');
  FOR i:=NbChif DOWNTO 1 DO
    WRITE(conv[i]:2);
  READLN
END. 
    \end{lstlisting}

Autre version  en utilisant des chaînes:

\begin{lstlisting}[caption={}]
PROGRAM exo1_6a_bis;

VAR n : QWORD; {Nombre a convertir}
    quotient : QWORD;
    reste : QWORD;
    b : BYTE; {base}
    conv : STRING; {nombre converti sous forme de chaine}

BEGIN
  {--- lecture des donnees ---}
  WRITE('Entrez le nombre a convertir : ');
  READLN(n);
  WRITE('ENtrez la base voulue (entre 2 et 10) : ');
  READLN(b);
  {--- conversion ---}
  reste:= n MOD b;
  quotient:= n DIV b;
  conv:=CHR(ORD('0')+reste);
  WHILE quotient > 0 DO
     BEGIN
      reste:=quotient MOD b;
      quotient:=quotient DIV b;
      conv:=CHR(ORD('0')+reste)+conv
     END;
  {--- resultat ---}
  WRITELN;
  WRITE(n, ' en base ',b,' : ',conv);
  READLN
END.                           
\end{lstlisting}


En récursif :

\begin{lstlisting}[caption={}]
PROGRAM exo1_6b;

VAR n : QWORD; {Nombre a convertir}
    b : BYTE; {base}

FUNCTION conv(n:QWORD;b:BYTE):STRING;
 BEGIN
  IF n<2 THEN conv:=CHR(ORD('0')+n)
  {on rajoute ORD('0') pour obtenir le bon code ASCII}
  ELSE conv:=conv(n DIV b,b)+CHR(ORD('0')+n MOD b);
 END;

BEGIN
  {--- lecture des donnees ---}
  WRITE('Entrez le nombre a convertir : ');
  READLN(n);
  WRITE('Entrez la base voulue (entre 2 et 10) : ');
  READLN(b);
  {--- resultat ---}
  WRITE(n, ' en base ',b,' : ',conv(n,b));
  READLN
END.             
\end{lstlisting}


  \end{exercice}

  \begin{exercice}
    Problèmes de terminaison.
  \end{exercice}

  \begin{exercice}

Sans multiplication:

    \begin{lstlisting}[caption={}]
PROGRAM exo1_8b;

VAR n:LONGWORD;
    k:LONGINT;


FUNCTION pasc(n:LONGWORD;k:LONGINT):QWORD;
BEGIN
  IF (k<0) OR (k>n)
  THEN pasc:=0
  ELSE
   BEGIN
     IF (k=0) OR (k=n)
     THEN pasc:=1
     ELSE pasc:=( (n-k+1)*pasc(n,k-1) ) DIV k
   END;
END;


BEGIN
  WRITE('Entrez un entier naturel : ');
  READLN(n);
  WRITE('Entrez un entier : ');
  READLN(k);
  WRITELN(k,' parmi ',n,' vaut ',pasc(n,k));
  READLN
END.                                    
    \end{lstlisting}


Avec multiplication:

    \begin{lstlisting}[caption={}]
PROGRAM exo1_8b;

VAR n:LONGWORD;
    k:LONGINT;


FUNCTION pasc(n:LONGWORD;k:LONGINT):QWORD;
BEGIN
  IF (k<0) OR (k>n)
  THEN pasc:=0
  ELSE
   BEGIN
     IF (k=0) OR (k=n)
     THEN pasc:=1
     ELSE pasc:=( (n-k+1)*pasc(n,k-1) ) DIV k
   END;
END;


BEGIN
  WRITE('Entrez un entier naturel : ');
  READLN(n);
  WRITE('Entrez un entier : ');
  READLN(k);
  WRITELN(k,' parmi ',n,' vaut ',pasc(n,k));
  READLN
END.                                    
    \end{lstlisting}

Le tableau:

    \begin{lstlisting}[caption={}]
PROGRAM exo1_8c;

CONST n=15;

VAR k : WORD;
    tpasc:ARRAY[0..n] OF QWORD;


BEGIN
  tpasc[0]:=1;
  tpasc[n]:=1;

  FOR k:=1 TO (n DIV 2) DO
  BEGIN
   tpasc[k]:=( (n-k+1)*tpasc[k-1] ) DIV k;
   tpasc[n-k]:=tpasc[k]
  END;

END.                   
    \end{lstlisting}

  \end{exercice}



  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_9a;

VAR n,s:QWORD;

FUNCTION isqrt_naif(n:QWORD):QWORD;
  VAR s:QWORD;
  BEGIN
    s:=0;
    WHILE (s*s)<=n DO
     s:=s+1;
    isqrt_naif:=s-1
  END;

BEGIN
  WRITE('Entrez un entier naturel : ');
  READLN(n);
  s:=isqrt_naif(n);
  WRITELN('Le plus grand entier cherche est : ',s);
  WRITE('En effet, ',s,'^2=',s*s,'<=',n);
  WRITE(' mais (',s,'+1)^2=',(s+1)*(s+1),'>',n);
  READLN
END.                  
    \end{lstlisting}


Version récursive:

\begin{lstlisting}[caption={}]
PROGRAM exo1_9c;

VAR n,s:LONGINT;

FUNCTION isqrt_temp(x,y,n:LONGINT):LONGINT;
  BEGIN
    IF (y-x<=1) THEN
       isqrt_temp:=x
    ELSE
      BEGIN
       IF ((x+y) DIV 2)*((x+y) DIV 2) > n THEN
         isqrt_temp:=isqrt_temp(x,(x+y) DIV 2,n)
       ELSE
         isqrt_temp:=isqrt_temp((x+y) DIV 2,y,n)
      END;
  END;


FUNCTION isqrt(n:LONGINT):LONGINT;
 BEGIN
 isqrt:=isqrt_temp(1,n,n);
 END;

BEGIN
  WRITE('Entrez un entier naturel : ');
  READLN(n);
  s:=isqrt(n);
  WRITELN('Le plus grand entier cherche est : ',s);
  WRITE('En effet, ',s,'^2=',s*s,'<=',n);
  WRITE(' mais (',s,'+1)^2=',(s+1)*(s+1),'>',n);
  READLN
END.                                               
\end{lstlisting}

  \end{exercice}








  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_10;

VAR l,sc,k,i:WORD;
    sn:STRING;

FUNCTION cube(n:WORD):WORD;
 BEGIN
  cube:=n*n*n;
 END;

FUNCTION test(n:WORD):BOOLEAN;
   BEGIN
     STR(n,sn);
     l:=LENGTH(sn);
     sc:=0;
     FOR k:=1 TO l DO
       sc:=sc+cube(ORD(sn[k])-ORD('0'));
     IF sc=n THEN test:=TRUE
     ELSE test:=FALSE
   END;

BEGIN
  FOR i:=100 TO 9999 DO
    IF test(i) THEN WRITELN(i);
  READLN
END.                                     
    \end{lstlisting}
  \end{exercice}


  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_11;

VAR n,s,k,fin,i:QWORD;

FUNCTION test(n:WORD):BOOLEAN;
BEGIN
  s:=1;
  fin:=n;
  FOR k:=2 TO fin-1 DO
    BEGIN
      IF n MOD k=0 THEN
        BEGIN
         fin:=n MOD k;
         IF k=fin THEN s:=s+k
         ELSE s:=s+k+n MOD k
        END;
    END;
  IF s=n THEN test:=TRUE
  ELSE test:=FALSE
END;

BEGIN
FOR i:=1 TO 9999 DO
  BEGIN
    IF test(i) THEN WRITELN(i)
  END;
READLN
END.                          
    \end{lstlisting}
  \end{exercice}


  \begin{exercice}
    \begin{lstlisting}[caption={}]
PROGRAM exo1_12;

VAR l,pc,k,i:WORD;
    sn:STRING;


FUNCTION prod(n:WORD):WORD;
   BEGIN
     STR(n,sn);
     l:=LENGTH(sn);
     pc:=1;
     FOR k:=1 TO l DO
       pc:=pc*(ORD(sn[k])-ORD('0'));
   prod:=pc
   END;


FUNCTION persi(n:WORD):WORD;
BEGIN
  IF prod(n)<10 THEN persi:=1
  ELSE persi:=1+persi(prod(n))
END;


BEGIN
  i:=1;
  WHILE persi(i)<5 DO i:=i+1;
  WRITELN(i);
  READLN
END.                   
    \end{lstlisting}
  \end{exercice}

\end{listeexercices}


\Pasc
\modenormal % restaure les définitions de sections, sous-sections, etc;



%%% Local Variables: 
%%% TeX-master: "PolyInfo10"
%%% End: 
