\chapterimage{cartoon-pi}

\chapter{Premiers pas}

\section{Généralités}

\Pasc
\subsection{Algorithme et programme}

\begin{algo}
\FUNC{algorithme breton}{
\pfarg{masse m : entier}}{gâteau délicieux}
\DECLVAR{beurre,sucre,farine,\oe uf}{entier}
\STATE{beurre\recoit{} m/4}
\STATE{sucre\recoit{} m/4}
\STATE{farine\recoit{} m/4}
\STATE{\oe uf\recoit{} m/4}
\ENDVAR
\BEGIN
 \STATE{Couper le beurre en petits moreaux}
 \STATE{ Le mettre à fondre doucement au bain-marie de préférence.}
\STATE{Dès qu'il est fondu arrêter. }
\STATE{Laisser  refroidir mais attention  : le  beurre doit  être encore}
\STATE{liquide !}
\STATE{ Il ne doit pas redevenir solide.}
\STATE{ Mettre le four à préchauffer à 160 degrés (th 5).}
\STATE{ Mettre les \oe ufs entiers avec le sucre dans un saladier.}
\STATE{Battre longuement le mélange pour qu'il blanchisse}
\STATE{ et devienne bien mousseux.}
\STATE{ Y ajouter le beurre fondu ET FROID.}
\STATE{ Rajouter progressivement à l'appareil la farine}
\STATE{ en l'incorporant
  bien.}
\STATE{Cela doit donner une pâte élastique et un peu épaisse.}
\STATE{ Verser la préparation dans un moule à manqué }
\STATE{ou à cake bien beurré.}
\STATE{ Laisser cuire environ une heure. }
\STATE{Il faut surveiller le gâteau
 régulièrement.}

\WHILE{ Le dessus du gâteau n'est pas blond foncé}
\STATE{Continuez la cuisson}
\ENDWHILE
\IF{ Il semble brunir trop vite}
\STATE{ il faut baisser un peu le four}
\STATE{Il faut mettre une feuille d'aluminium sur le dessus.}
\ENDIF
\IF{lorsqu'une pique plantée en son milieu ressort sèche}
\STATE{le gâteau est cuit }
\ELSE
\STATE{Continuez la cuisson.}
\ENDIF
\STATE{Retirez le gâteau}
\END
\end{algo}


\ill{Un algorithme est une description  rigoureuse en un nombre fini d'étapes
de la résolution d'un problème.

La  notion  d'algorithme  existe   depuis  bien  avant  l'existence  des
ordinateurs et  même bien avant  la naissance du mot  lui-même puisqu'il
est tiré du nom du célèbre mathématicien persan \begin{otherlanguage}{farsi}
أبو عبد الله محمد بن موسى الخوارزمي
\end{otherlanguage} ou si vous préférez 
Abu  'Abdallah Muhammad  ibn  Musa al-Khwarizmi  qui  vécut au  IX\up{e}
siècle de  notre ère, c'est-à-dire près  de 3000 ans  après les premiers
algorithmes de calcul connus mis au point en Mésopotamie.}{al-khwarizmi}

Vous  utilisez  depuis  longtemps  des  algorithmes,  à  la  manière  de
M. Jourdain, sans toujours le savoir, par exemple lorsque vous lisez une
recette de cuisine, lorsque vous recherchez un mot dans le dictionnaire,
lorsque vous effectuez une addition posée.

Cependant, cette année, nous  nous contenterons d'algorithmes destinés à
être  utilisés  par un  ordinateur.  Nous  introduirons  donc un  langage
algorithmique  le moins  ambiguë possible  et le  plus standard  afin de
pouvoir mettre en \oe uvre ces algorithmes sur n'importe quelle machine.

Même si  nos algorithmes  doivent être indépendants  de tout  langage de
programmation, il sera  enrichissant de les tester \og  en vrai\fg{} sur
machine. Nous serons  donc amenés à parler à la  machine. Pour cela nous
utiliserons un langage servant d'interface  entre la machine et nous car
tout  être humain normalement  constitué ne  peut décemment  entamer une
longue conversation avec un ordinateur en langage machine. 

Au
programme de MP, nous avons le  choix entre PASCAL et CAML. C'est PASCAL
qui a  été choisi  dans notre lycée.  Cependant, lors  de l'enseignement
commun du  premier trimestre, nous  nous réservons le droit  de proposer
quelques algorithmes en Maple.


\subsection{Spécification}

Les deux phrases suivantes ont  un sens pour nous\cite{habrias}:

\begin{itemize}

\item   \textit{On doit porter un casque sur une moto.}


\item 

\textit{On doit porter les animaux sur les escaliers mécaniques.}
\end{itemize}

On utilise deux  fois \textit{on doit porter} mais le  sens n'est pas le
même:

\begin{itemize}

\item
Il n'est  bien sûr pas obligatoire  d'avoir un chien dans  les bras pour
pouvoir utiliser un escalier mécanique. Il faudrait donc plutôt dire:\og
dans  le  cas   où  vous  avez  un  animal,   portez-le  sur  l'escalier
mécanique. Si vous n'en avez pas, vous pouvez prendre l'escalier sans contrainte\fg{}.

\item Si on n'a pas de casque sur  soi, on ne peut pas s'en passer pour monter
sur une  moto, comme on  peut se passer  d'avoir un chien avec  soi pour
monter sur  un escalier  mécanique. Il faudrait  plutôt dire:\og  il est
obligatoire d'avoir toujours un casque pour pouvoir monter sur une moto.\fg{}
\end{itemize}


Il   faudra  donc   être  très   précis  et   non  ambigus   dans  notre
formulation.  C'est  pourquoi  nous  préférerons un  langage  formel  au
langage naturel.

Enfin, spécifier, ce n'est pas dire  comment sont effectués les calculs mais ce
qu'ils calculent.



\begin{exemple}
Spécifions une fonction qui  a pour données  un nombre en
  base dix et qui a pour résultat son écriture en base deux.
\end{exemple}

Précisons un peu: 

\begin{itemize}
\item La donnée  est un nombre entier positif écrit en
  base dix (c'est la \textit{précondition}). 
\item Le résultat  est une liste d'entiers appartenant  à $\{0;1\}$ dans
  l'ordre décroissant  des puissances de deux associées.  On convient de
  commencer par  la plus  grande puissance dont  le coefficient  est non
  nul (c'est la \textit{postcondition}).
\end{itemize}

Par exemple, si on entre 11 on obtiendra $[1,0,1,1]$.

En effet, $11=1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+1\cdot 2^0$.

 On ne  sait pas encore  \textit{comment} calculer le résultat  mais on
  sait  déjà \textsc{ce  que calcule}  cette  fonction et  on peut  donc
  l'intégrer dans des calculs plus complexes.


\section{Une galerie d'exemples}


\subsection{Posons le problème}

Avant  d'être  capable  d'écrire  des  algorithmes  corrects,  observons
quelques exemples afin de nous donner une idée de la tâche à accomplir.


\begin{exemple}
  Étant  donné un  entier relatif  $a$  et un
entier naturel $n$, on voudrait obtenir $a^n$ qui sera un entier relatif.
\end{exemple}

\subsection{Spécifions le problème}

 \verb+puissance(a:entier;n:entier positif):entier+

\verb+puissance(a,n) renvoie a à la puissance n+


\subsection{Premier algorithme : fonction récursive}


\begin{algo}
\FUNC{puissance}{%
\pfarg{a}{entier} ; \pfarg{n}{entier positif}}{entier}
\COMMENT{Ceci est un commentaire non évalué par la machine}
\COMMENT{puissance(a,n) renvoie a à la puissance n}
\COMMENT{C'est un algorithme récursif}
\BEGIN
\IF{n=0}
\STATE{1}
\ELSE
\STATE{a*puissance(a,n-1)}
\ENDIF
\END 
\end{algo}






\begin{recherche}
\begin{itemize}
  \item Que fait cet algorithme?
\item Peut-on le prouver?
\item Comment caractériser son efficacité?
\end{itemize}
\end{recherche}

Traduction possible en Pascal:



\begin{lstlisting}[caption={}]
FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
 BEGIN
  IF n=0
  THEN Puissance:=1
  ELSE Puissance:=a*Puissance(a,n-1);
 END;
\end{lstlisting}



Mais Pascal ne  fonctionne pas en mode interactif.  Il faut donc inclure
cette fonction dans un programme.


\begin{lstlisting}[]
PROGRAM Puissance_rec;
VAR a:INTEGER; n:INTEGER;

 FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
  BEGIN
   IF n=0
   THEN Puissance:=1
   ELSE Puissance:=a*Puissance(a,n-1);
  END;

BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  WRITE(a,'^',n,' = ',Puissance(a,n));
  READLN;
END.                     
\end{lstlisting}
  

et cela donne:

\begin{boxedverbatim}
  Entrer a : 2
  Entrer n : 5

  2^5 = 32
\end{boxedverbatim}

Oui mais...On  n'a pas obéit à  notre spécification: le  cas $n$ négatif
n'a pas été traité. 


\begin{lstlisting}[]
PROGRAM Puissance_rec;
VAR a:INTEGER; n:INTEGER;

 FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
  BEGIN
   IF n=0
   THEN Puissance:=1
   ELSE Puissance:=a*Puissance(a,n-1);
  END;

BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  IF n<0 
  THEN WRITE('L exposant doit etre positif')
  ELSE WRITE(a,'^',n,' = ',Puissance(a,n));
  READLN;
END.                     
\end{lstlisting}

Dans un autre langage comme Caml,  l'idée est la même mais la manière de
l'implanter et de l'utiliser diffèrent:
\caml
\begin{lstlisting}[caption={}]
# exception Exposant_negatif;;


# let rec puissance(a,n)=
    if n<0 
    then raise Exposant_negatif
    else 
      if n==0 
      then 1
      else a*puissance(a,n-1);; 
\end{lstlisting}

% Caml répond directement:

% \begin{lstlisting}[caption={}]
% # exception Exposant_negatif;;


% # let rec puissance(a,n)=
%     if n<0 
%     then raise Exposant_negatif
%     else 
%       if n==0 
%       then 1
%       else a*puissance(a,n-1);; 
%   val puissance : int * int -> int = <fun>

% # puissance(2,5);;
% - : int = 32
% \end{lstlisting}

Ou en Maple:

\maple

\begin{lstlisting}[caption={}]
> puissance:=proc(a,n)
    if n<0 then RETURN(`exposant negatif !!`)
    elif n=0
    then 1
    else a*puissance(a,n-1)
    fi
  end:
\end{lstlisting}


Ou en Python:
\sage

\begin{lstlisting}[caption={}]
>>> def puissance(a,n):
...    if n<0:
...       return("exposant negatif")
...    elif n==0:
...       return(1)
...    else:
...       return(a*puissance(a,n-1))
\end{lstlisting}

Ou en XCAS:
\xc
\begin{lstlisting}[caption={}]
puissance(a,n):={
 si n<0 alors retourne("exposant negatif !!")
        sinon si n==0 alors retourne(1)
              sinon retourne(a*puissance(a,n-1))
              fsi
 fsi
}
\end{lstlisting}

\Pasc




\subsection{Deuxième algorithme : boucle \og pour\fg{}}


\begin{algo}
\FUNC{puissance}{%
\pfarg{a}{entier} ; \pfarg{n}{entier positif}}{entier}
\COMMENT{puissance(a,n) renvoie a à la puissance n}
\COMMENT{C'est un algorithme impératif utilisant une boucle pour}
\VAR
\DECLVAR{temp,k}{entier}
\ENDVAR
\BEGIN
\STATE{temp \recoit{} 1}
\FOR{k}{1}{n}\COMMENT{On ne rentre dans la boucle que si k>=1}
\STATE{temp \recoit{} temp*a}
\ENDFOR
\RETURN{temp}
\END 
\end{algo}


\begin{recherche}
\begin{itemize}
\item Que fait cet algorithme?
\item Qu'est-ce qui le différencie du précédent?
\item Peut-on le prouver?
\item Comment caractériser son efficacité?
\end{itemize}
\end{recherche}





En Pascal:

\begin{lstlisting}[caption={}]
PROGRAM Puissance_it;
VAR a:INTEGER; n:INTEGER;

FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
VAR temp:INTEGER; k:INTEGER;
 BEGIN
  temp:=1;
  FOR k:=1 TO n DO temp:=temp*a;
  Puiss:=temp;
 END;


BEGIN {programme principal}
  WRITE('Entrer a : ');READLN(a);
  WRITE('Entrer n : ');READLN(n);
  WRITELN;
  IF n<0 
  THEN WRITE('L exposant doit etre positif')
  ELSE WRITE(a,'^',n,' = ',Puissance(a,n));
  READLN;
END.                   
\end{lstlisting}


On remarque que, en Pascal, que  la fonction de  calcul de la  puissance soit
récursive  ou itérative,  la  manière de  l'utiliser  dans le  programme
principal est la même.



\subsection{Troisième algorithme : boucle \og tant que\fg{}}


\begin{algo}
\FUNC{puissance}{%
\pfarg{a}{entier} ; \pfarg{n}{entier positif}}{entier}
\COMMENT{puissance(a,n) renvoie a à la puissance n}
\COMMENT{C'est un algorithme impératif utilisant une boucle tant que}
\VAR
\DECLVAR{temp,k}{entier}
\ENDVAR
\BEGIN
\STATE{temp \recoit{} 1}
\STATE{k \recoit{} n}
\WHILE{k>0}\COMMENT{On ne rentre dans la boucle que si k>0}
\STATE{k \recoit{} k-1}
\STATE{temp \recoit{} a*temp}
\ENDWHILE
\RETURN{temp}
\END 
\end{algo}


En Pascal:

\begin{lstlisting}[caption={}]
PROGRAM Puissance_tq;
VAR a:INTEGER; n:INTEGER;

FUNCTION Puissance(a:INTEGER;n:INTEGER):INTEGER;
VAR temp:INTEGER; k:INTEGER;
 BEGIN
  temp:=1;
  k:=n;
  WHILE k>0  DO
    BEGIN
    k:=k-1;
    temp:=temp*a;
    END;
  Puiss:=temp;
 END;

BEGIN {programme principal habituel}
END.                  
\end{lstlisting}

\subsection{Exponentiation logarithmique}


Le principe est simple:

\[
\left\{
\begin{array}{lcll}
a^0&=&1&\\
a^n&=&\left(a^2\right)^{\frac{n}{2}}&,\text{si  }  n  \text{  est  pair
  et }n>0\\
a^n&=&a\times\left(a^2\right)^{\frac{n-1}{2}}&,\text{si  }  n  \text{  est  impair}
\end{array}
\right.
\]


\begin{recherche}
Écrivez  un  algorithme  utilisant  ces relations  de  récurrence.  Qu'y
gagne-t-on?
\end{recherche}


\section{Quelques types prédéfinis}

Les  variables,  les  constantes,  les  arguments  introduits  dans  les
algorithmes peuvent être de types  différents. Tous les langages ont des
types prédéfinis à peu près communs.


\subsection{Les entiers}

Un  entier naturel  est  un entier  positif  ou nul.  Le  choix à  faire
(c'est-à-dire  le  nombre  de  bits\footnote{Le  mot  «  bit  »  est  la
  contraction des  mots anglais binary  digit, qui signifient  « chiffre
  binaire »,  avec un jeu de  mot sur bit, «  morceau ». Il  ne faut pas
  confondre avec  le mot \og byte\fg{}, en  français \og multiplet\fg{},
  qui désigne un assemblage de bits, en général 8 (un octet).} à utiliser) dépend de la fourchette des
nombres  que  l'on  désire  utiliser.  Pour coder  des  nombres  entiers
naturels compris  entre 0 et 255, il  nous suffira de 8  bits (un octet)
car  $2^8=256$.  D'une  manière  générale  un codage  sur  $n$  bits  pourra
permettre de représenter des nombres entiers naturels compris entre 0 et
$2^{n-1}$.  Les  processeurs   disponibles  actuellement  proposent  des
codages  sur 32 ou  64 bits.  Cependant, les  logiciels ne  tiennent pas
toujours compte des  64 bits et vous avez  beau disposer d'un processeur
64 bits, il sera utilisé comme  s'il était de type 32 bits (notamment si
le système d'exploitation est microsoft-windows...).

Pour représenter un  nombre entier naturel après avoir  défini le nombre
de bits sur  lequel on le code,  il suffit de ranger chaque  bit dans la
cellule binaire correspondant  à son poids binaire de  la droite vers la
gauche, puis on « remplit » les bits non utilisés par des zéros. 

\medskip

Pour les  entiers relatifs, le bit  situé à l'extrême gauche  (le bit de
poids fort), représentera le signe: 0  pour un nombre positif, 1 pour un
nombre négatif. Cela restreint donc l'étendue des nombres disponibles.

Un entier  relatif positif  est donc codé  comme un entier  naturel mais
avec un 0 à gauche.


Pour les entiers  négatifs, on utilise une petite  ruse: le complément à
2 que nous étudierons à titre d'exercice.

Ainsi,  sur   les  ordinateurs  qui  sont  à   notre  disposition,  tout
introduction  d'un   entier  dépassant  $2^{31}-1=\numprint{2147483647}$
engendrera une erreur.



\subsection{Les flottants}

La norme IEEE définit la façon de coder un nombre réel.
Cette norme se  propose de coder le nombre sur 32  bits et définit trois
composantes : 

\begin{itemize}
\item le  signe est  représenté par un  seul bit,  le bit de  poids fort
  (celui le plus à gauche);
\item l'exposant est codé sur les 8 bits consécutifs au signe;
\item la mantisse, c'est-à-dire le nombre \og sans la virgule\fg{}, sur les 23 bits restants.
\end{itemize}

   

La précision des  nombres réels est approchée. Elle  dépend du nombre de
positions décimales, suivant le type de réel elle sera au moins:

\begin{itemize}
\item de 6 chiffres après la virgule pour un système 32 bits;
\item de 15 chiffres après la virgule pour un système 64 bits.
\end{itemize}


Ces  limitations peuvent  causer quelques  surprises. Par  exemple, vous
pouvez tester sur Maple:

\maple
\begin{lstlisting}
> 100000+0.0000002;
\end{lstlisting}
\Pasc

\begin{boxedverbatim}
  100000
\end{boxedverbatim}


\begin{remarque}
Ces  problèmes   d'implémentation  des  entiers  et   des  flottants  ne
concernent pas l'algorithmique mais la 
programmation dans un  certain langage, sur un certain  système. On n'en
tiendra donc pas forcément compte. 
\end{remarque}


\subsection{Les caractères et chaînes de caractères}


Le type \og caractère\fg{} permet de stocker le code d'un
caractère, c'est-à-dire  un nombre entier. Une chaîne  de caractères est
une  suite ordonnée de  caractères.  La  représentation d'une  chaîne de
caractères dépend d'un système à un autre. 

\subsection{Les booléens}
Avant  d'étudier  les  structures  conditionnelles, il  nous  faut  nous
habituer aux tests, aux booléens et  à leurs opérateurs, qui ne sont pas
d'un usage aussi naturel que les types flottants et entiers.

 \begin{itemize}
    \item Une variable de type booléen n'a que deux valeurs possibles: VRAI ou
FAUX.
\item Ces  booléens sont en  particulier les valeurs retournées  par les
  opérateurs  de comparaison:  \verb+=+, \verb+<+,  \verb+<=+, \verb+>+,
  \verb+>=+, \verb+<>+.
\item  Ils   ont  en   général  4  opérateurs:   \verb+ET+,  \verb+OU+,
  \verb+OUEX+, \verb+NON+.
  \end{itemize}


  \begin{recherche}
    
 

Par exemple, quelle sera la réponse à:

\begin{itemize}
\item $3>2$ ET $2>2$?
\item $3>2$ ET $2 \geqslant 2$?
\item $3>2$ OU $2>2$?
\item $3>2$ OU $2 \geqslant 2$?
\item $3>2$ OUEX $2 \geqslant 2$?
\item $3>2$ OUEX $2>2$?
\item NON $2>2$?
\item NON $3>2$?
\end{itemize}

 \end{recherche}




\section{Les structures conditionnelles}

Elles  sont   communes  aux  deux   types  de  programmation   que  nous
étudierons. C'est le fameux SI...ALORS...SINON...


Voici un bel algorithme:


\begin{algo}
\FUNC{zorg}{%
\pfarg{a,b,c}{entier}}{caractère}
\BEGIN
\IF{a<>b}
\IF{a+1=b}
\RETURN{'aarrgh'}
\ELSE
\IF{c<>7}
\RETURN{'glurp'}
\ELSE
\RETURN{'pas glop'}
\ENDIF
\ENDIF
\ELSE
\RETURN{'eviv bulgroz'}
\END 
\end{algo}

\begin{recherche}
Que répond 
\begin{itemize}
  \item \verb+zorg(4,5,7)+?
\item \verb+zorg(4,5,8)+?
\item \verb+zorg(4,6,7)+?
\end{itemize}
\end{recherche}



\section{La programmation impérative: au plus près de la machine}


\subsection{L'affectation}


L'instruction représentée par:


\begin{algo}
\STATE{a \recoit{} 2}
\end{algo}

qui se lit \og a reçoit  2\fg{} réserve (affecte) une zone de la mémoire
de l'ordinateur qui portera l'étiquette a et qui contiendra 2.


\begin{recherche}
  
Donnez le contenu de a et b après la suite d'affectations suivante:

\begin{algo}
\STATE{a \recoit{} 1}
\STATE{b \recoit{} 2}
\STATE{a \recoit{} a+b}
\STATE{b \recoit{} a-b}
\STATE{a \recoit{} a-b}
\end{algo}
\end{recherche}



Un algorithme impératif va  donc modifier chronologiquement l'état de la
mémoire. Les  valeurs des variables vont sans  cesse évoluer. Cependant,
la plupart  du temps, les notations des  structures itératives utilisées
n'expriment pas  clairement l'état des  variables. Il faudra  donc, pour
bien  maîtriser  l'algorithme,  le  commenter  pour  décrire  les  états
parcourus par le système.



\begin{DANGER}
On veillera à ne pas  modifier les arguments d'une fonction avec quelque
chose du style:
\begin{algo}
\FUNC{non}{%
\pfarg{a,b,c}{entier}}{entier}
\STATE{a\recoit{}a+1}
\end{algo}

Il faut  introduire une variable locale  prenant au départ  la valeur de
l'argument puis la modifier:

\begin{algo}
\FUNC{oui}{%
\pfarg{a,b,c}{entier}}{entier}
\VAR
\DECLVAR{temp}{entier}
\ENDVAR
\STATE{temp\recoit{}a}
\STATE{temp\recoit{}temp+1}
\end{algo}

\end{DANGER}

\subsection{Structures itératives}

\subsubsection{Tant que}

\begin{exemple}
Soit  deux entiers  naturels $n$  et $N$  tels que  $n \leqslant  N$. On
voudrait calculer la somme des entiers de $n$ à $N$.
\end{exemple}

Les  notations mathématiques peuvent  ici nous  guider. En  effet, cette
somme $S(n,N)$ s'écrit:

$$S(n,N)=\displaystyle\sum_{k=n}^{k=N}k=n+(n+1)+(n+2)+\cdots+(N-1)+N$$


\begin{algo}
\FUNC{somme}{%
\pfarg{n,N}{entier}}{entier}
\COMMENT{On doit avoir n<=N. On  obtient la somme des entiers successifs
  de n à N compris}
\COMMENT{Nous  allons créer  une variable  provisoire qui  contiendra la
  somme en construction ainsi que l'entier provisoire qui va être itéré.}
\VAR
\DECLVAR{Stemp,ktemp}
\ENDVAR
\BEGIN
\STATE{Stemp\recoit{} 0}
\STATE{ktemp \recoit{} n}
\COMMENT{On choisit  d'initialiser la somme à 0  et l'indice d'itération
  à n.}
\WHILE{ktemp <= N}
\COMMENT{On entre dans la boucle jusqu'à la valeur N comprise}
\STATE{Stemp\recoit{} Stemp+ktemp}
\COMMENT{À l'état initial on commence donc par rajouter n à 0}
\STATE{ktemp\recoit{} ktemp+1}
\end{algo}

\begin{algo}[continue]
\COMMENT{ktemp est incrémenté après la somme.}
\COMMENT{  À  la dernière  étape,
  ktemp vaut N,}
\COMMENT{ est rajouté à Stemp puis ktemp reçoit N+1}
\COMMENT{ et  on sort
  donc de la boucle.}
\COMMENT{ Dans l'état final  on a donc la  somme des entiers
  de n à N.}
\ENDWHILE
\RETURN{Stemp}
\END
\end{algo}


Avec Maple:

\maple

\begin{lstlisting}[caption={}]
> Somme:=proc(n,N)
   local Stemp,ktemp;
   Stemp:=0;
   ktemp:=n;

   while ktemp<=N do
     Stemp:=Stemp+ktemp;
     ktemp:=ktemp+1;
   od;

   RETURN(Stemp)
  end:
\end{lstlisting}



Vérifions que notre algorithme fait bien ce qu'on attend de lui.


La   propriété   $\PR(\verb+ktemp+)$:   \og   \verb+Stemp+$=S(n,$\verb+ktemp+)   et
\verb+ktemp+$\leqslant N$\fg{} est l'\textit{invariant de boucle}.

Au départ,  on a bien $\PR(n)$: \verb+Stemp+$=S(n,n)=n$  et $n \leqslant
N$.

À  chaque fin  d'occurrence de  la boucle,  cette propriété  reste vraie
ainsi qu'en sortie.



\begin{recherche}
On modifie légèrement l'ordre des instructions de cet algorithme:

\begin{algo}
\STATE{ktemp\recoit{} ktemp+1}
\STATE{Stemp\recoit{} Stemp+ktemp}
\end{algo}

Y a-t-il d'autres choses à modifier?
\end{recherche}

% Il  existe  une  variante  POUR...VARIANT DE...À...FAIRE  mais  dont  le
% contrôle est plus délicat. Nous la laisserons de côté pour l'instant.

\subsubsection{Pour}

En anglais, c'est \og for\fg{} et sur MAPLE c'est:

\maple
\begin{lstlisting}
for var from debut to fin by increment do 
    instructions;
od; 
\end{lstlisting}


Par exemple~:

\begin{lstlisting}
> Somme:=proc(n::posint)
  local S,k;
  S:=0;
   for k from 1 to n by 1 do
     S:=S+k; 
   od;
 RETURN(S)
 end:
\end{lstlisting}



On peut arrêter  l'itération dès qu'une condition a  été réalisée (et se
passer du \verb+to+)~:


\begin{lstlisting}
> Somme:=proc(n::posint)
  local P,k;
  S:=0;
   for k from 1 while P<=n do
     S:=S+k; 
   od;
 RETURN(S)
 end:
\end{lstlisting}



\subsection{Les listes: premier contact}

\subsubsection{Généralités}

Une liste est un objet très important en informatique. Nous l'étudierons
plus  précisément après  décembre.  Sachons juste  pour l'instant  qu'il
s'agit d'un ensemble ordonné d'objets quelconques qui peuvent d'ailleurs
être des listes. 

On les note habituellement à l'aide de crochets:

\begin{algo}
\STATE{L\recoit{}[a,b,1,2,"maman",x->cos(x)]}
\end{algo}

On peut  accéder à un  élément de la  liste par son numéro  (on commence
généralement à compter à partir  de 0). Ainsi, \verb+L[0]+ est \verb+a+,
\verb+L[3]+ est \verb+2+. 


On peut extraire une sous-liste: \verb+L[1..3]+ donnera \verb+[b,1,2]+.

On   peut   \emph{concaténer}   des   listes,   c'est-à-dire   les   \og
coller\fg{}. Nous  utiliserons conventionnellement pour  représenter cet
opérateur le symbole \verb|+|.


\subsubsection{Avec MAPLE}


Les  listes  sont un  type  de  variable  particulier que  peut  manipuler
MAPLE.  Une  liste se  présente sous la  forme d'une suite  d'objets
séparés par des virgules entre crochets~:

\begin{lstlisting}
> L:=[1,2,a,g,maman,ln(5),3/2,x->3*x+2,[7,9]]
\end{lstlisting}

Cette suite est ORDONNÉE. Ses éléments sont donc numérotés.
On peut en extraire un élément particulier~:

\begin{lstlisting}
> L[5]
\end{lstlisting}


ou bien tous les éléments de la liste~:

\begin{lstlisting}
op(L)
\end{lstlisting}

ou bien une sous-liste~:

\begin{lstlisting}
> L[3..6];
\end{lstlisting}


On peut connaître la taille d'une liste~:

\begin{lstlisting}
> nops(L);
\end{lstlisting}

On peut ajouter un élément à une liste~:

\begin{lstlisting}
> L:=[op(L),nouveau]
\end{lstlisting}


On peut \emph{concaténer} deux listes~:

\begin{lstlisting}
> L1:=[1,2,3,4];
> L2:=[a,b,c];
> L:=[op(L1),op(L2)]
\end{lstlisting}



La liste vide se note~:

\begin{lstlisting}
> V:=[];
> nops(V);
\end{lstlisting}

On peut  effectuer des  opérations sur  une liste car  c'est un  type de
variable comme un autre~:


\begin{lstlisting}
> S:=L1+[op(L2),d];
> P:=3*L1;
\end{lstlisting}





\section{Au plus près de l'humain: la programmation récursive}


\subsection{Qu'est-ce que c'est?}

La récursion  est un  mécanisme puissant permettant,  comme l'itération,
d'exprimer la répétition des opérations, mais de manière plus concise et
en ayant la  possibilité de se passer d'affectation  et ainsi éviter les
problèmes de surveillance de l'état de la mémoire.

Il  ne se  limite pas  au  cas des  suites numériques  définies par  une
relation de récurrence. 

Par  exemple, définissons un  caractère comme  un élément  de l'ensemble
constitué des 26 lettres de l'alphabet latin:
$\Bigl\{\; '{\rm a}',\ '{\rm b}',\cdots,\ '{\rm z}'\; \Bigr\}$

On peut donner une définition récursive d'un mot:

\textit{Un mot est soit un caractère, soit un caractère suivi d'un mot.}


Avec cette  définition, \og papa\fg{} est  un mot mais  \og père\fg{} ne
l'est pas.



\subsubsection{Une récursion concrète}


On place un certain nombre d'élèves en les classant par ordre décroissant
de taille. Le plus grand voudrait connaître sa propre taille mais chaque
élève ne peut  mesurer que son écart de taille avec  son voisin. Seul le
plus petit connaît sa taille. 

Le plus  grand mesure son  écart avec son  voisin et garde le  nombre en
mémoire.  Le voisin  fait de  même avec  son propre  voisin et  ainsi de
suite. Enfin l'avant dernier fait de même puis le plus petit lui transmet
sa taille : il peut donc calculer sa propre taille et transmet la au
suivant et ainsi  de suite~:~chacun va ainsi pouvoir  calculer sa taille
de proche en proche....



\subsubsection{Analyse rapide e d'un algorithme récursif}

Il n'est pas  trop compliqué de comprendre   que l'entier suivant $n$
est égal à $1+$ l'entier suivant $n-1$.

Maintenant,  il faudrait  connaître \og  la taille  du  plus petit\fg{},
c'est-à-dire une \emph{condition terminale}. Si on ne s'intéresse qu'aux
entiers naturels, le plus petit sera 0 et on fixe que le successeur de 0
est 1.

On peut alors écrire un algorithme ainsi~:

\begin{algo}
\FUNC{successeur}{%
\pfarg{n}{entier naturel}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\RETURN{1+successeur(n-1)}
\ENDIF
\END
\end{algo}

Par exemple sur Maple:

\maple

\begin{lstlisting}[caption={}]
> successeur:=proc(n)
    if n=0 then RETURN(1)
    else RETURN(1+successeur(n-1))
    fi
  end:
\end{lstlisting}


Que  se passe-t-il  dans  le  c\oe ur  de  l'ordinateur lorsqu'on  entre
\verb+successeur(3)+~?


\begin{itemize}


\item On entre comme argument 3~;

\item Comme 3  n'est pas  égal à 0,  alors\verb+successeur(3)+ est  stocké en
mémoire et vaut

\verb/1+successeur(2)/~;


\item Comme 2 n'est pas égal à 0, alors\verb+successeur(2)+ est stocké en
mémoire et  vaut

\verb/1+successeur(1)/~;


\item Comme 1 n'est pas égal à 0, alors\verb+successeur(1)+ est stocké en
mémoire et  vaut

\verb/1+successeur(0)/~;


\item Cette fois,\verb+successeur(0)+ est connu et vaut 1~;


\item\verb+successeur(1)+ est maintenant connu et vaut \verb/1+successeur(0)/
c'est-à-dire 2~;



\item\verb+successeur(2)+ est maintenant connu et vaut \verb/1+successeur(1)/
c'est-à-dire 3~;


\item\verb+successeur(3)+ est maintenant connu et vaut \verb/1+successeur(2)/
c'est-à-dire 4~:~c'est fini~!

\end{itemize}


C'est  assez  long  comme  cheminement  mais  ce  n'est  pas  grave  car
\emph{c'est  l'ordinateur qui  effectue  le \og  sale boulot\fg{}}~!  Il
stocke les  résultats intermédiaires  dans une \emph{pile}  et n'affiche
finalement que le résultat.

Comme il calcule  vite, ce n'est pas grave. L'élève  ou le professeur ne
s'est occupé que de la définition récursive (mathématique~!) du problème.

Maple calcule facilement\verb+successeur(543)+ mais
ensuite on dépasse les possibilités de calcul du logiciel.


Et oui, un langage impératif ne traite pas efficacement le problème de pile, 
c'est pourquoi pendant longtemps  seuls les algorithmes
impératifs ont prévalus. 

CAML est un langage fonctionnel et gère  très efficacement  la  mémoire de
l'ordinateur pour éviter sa saturation lors d'appels récursifs.


Le programme s'écrit comme en mathématique (mais en anglais...)~:


\caml

\begin{lstlisting}
# let rec successeur(k)=
  if k=0 then 1
  else 1+successeur(k-1);;  
\end{lstlisting}



Alors par exemple~:


\begin{lstlisting}
# successeur(36000);;
- : int = 36001
\end{lstlisting}

Mais


\begin{lstlisting}
# successeur(3600000);;
Stack overflow during evaluation (looping recursion?).
\end{lstlisting}


La \emph{pile} où sont stockés les résultats intermédiaires créés par la
récursion est en effet saturée.

Aujourd'hui, les langages fonctionnels  sont très efficaces et gèrent de
manière  intelligente  la  \emph{pile}. Ils le font soit automatiquement,
soit si la fonction utilise une \emph{récursion terminale}, c'est-à-dire
si l'appel récursif à la fonction n'est pas \emph{enrobé} dans une autre
fonction. 

Ici, ce  n'est pas le  cas car l'appel récursif \verb+successeur(k-1)+ est
enrobé dans la fonction $x\mapsto 1+x$.


On peut y  remédier en introduisant une fonction  intermédiaire qui sera
récursive terminale~:


\begin{lstlisting}
# let rec successeur_temp(k,resultat)=
        if k=0 then resultat
        else successeur_temp(k-1,resultat+1);;
\end{lstlisting}

puis on appelle cette fonction en prenant comme résultat de départ 1~:


\begin{lstlisting}
# let successeur_bis(k)=
  successeur_temp(k,1);;
\end{lstlisting}

Alors~:



\begin{lstlisting}
# successeur_bis(360000000);;
- : int = 360000001
\end{lstlisting}

Il n'y a donc aucun problème pour traiter 360 millions d'appels récursifs~!








\subsection{Deux  manières d'aborder  un même  problème :  les  tours de
  Hanoï} 

\subsubsection{Le principe}

Ce casse-tête a été posé  par le  mathématicien
français Édouard \textsc{Lucas} en 1883.

Le  jeu  consiste  en  une  plaquette  de bois  où  sont  plantés  trois
piquets. Au  début du jeu, $n$  disques de diamètres croissant  de bas en
haut sont placés  sur le piquet de  gauche. Le but du jeu  est de mettre
ces disques dans le même ordre sur le piquet de droite en respectant les
règles suivantes~:

\begin{itemize}
\item on ne déplace qu'un disque à la fois~;
\item on ne peut poser un disque que sur un disque de diamètre supérieur.
\end{itemize}

%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{hanoi}
\end{center}
%\end{figure}


Essayez avec 2 puis 3 disques...  Nous n'osons pas vous demander de résoudre
le problème avec 4 disques~!



\subsubsection{Non pas comment mais pourquoi~:~version récursive} 

 En  réfléchissant récursivement,  c'est enfantin~!...  Pour  définir un
 algorithme récursif, il nous
faut régler un cas simple et pouvoir simplifier un cas compliqué.


\begin{itemize}
\item \emph{cas simple}~: s'il y a zéro disque, il n'y a rien à faire~!
\item \emph{simplification d'un cas  compliqué}~: nous avons $n$ disques
  au départ  sur le premier disque  et nous savons  résoudre le problème
  pour $n-1$ disques. Appelons A, B et C les piquets de
  gauche à droite. Il suffit de déplacer les $n-1$ disques supérieurs de
  A vers B (hypothèse de récurrence) puis on déplace le plus gros disque resté sur A en C. Il ne
  reste  plus qu'à  déplacer vers  C les  $n-1$ disques  qui  étaient en
  B. (hypothèse de récurrence).
\end{itemize}

On voit bien  la récursion~:~le problème à $n$ disques  est résolu si on
sait résoudre le cas à $n-1$ disques  et on sait quoi faire quand il n'y
a plus de disques. 



On sait pourquoi  cet algorithme va réussir mais on  ne sait pas comment
s'y prendre étape par étape.

On va donc  appeler à l'aide l'ordinateur en  lui demandant d'écrire les
mouvements effectués à chaque étape.


\caml

On commence par créer une fonction qui affichera le mouvement effectué~:

\begin{lstlisting}[caption={mouvement élémentaire}]
let mvt depart arrivee=
print_string
("Deplace un disque de la tige "^depart^" vers la tige "^arrivee);
print_newline();;
\end{lstlisting}


Le programme proprement dit~:

\begin{lstlisting}[caption={résolution  récursive du problème  des tours
de Hanoï}]
let rec hanoi a b c= function
   | 0 -> ()  (*0 disque : on ne fait rien*)
   | n -> hanoi a c b (n-1); (*n-1 disques sont places dans l'ordre de a vers b*)
          mvt a c; (*on deplace le disque restant en a vers c*)
          hanoi b a c (n-1) (*n-1 disques sont places dans l'ordre de b vers c*);;
\end{lstlisting}

Les phrases entre\verb+(*+ et\verb+*)+ sont des commentaires.


Par exemple, dans le cas de 3 disques~:

\begin{lstlisting}
# hanoi "A" "B" "C" 3;;
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige A vers la tige B
Deplace un disque de la tige C vers la tige B
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige B vers la tige A
Deplace un disque de la tige B vers la tige C
Deplace un disque de la tige A vers la tige C
- : unit = ()
\end{lstlisting}

\subsubsection{Non pas pourquoi mais comment~:~version impérative}



Prenez un papier et  un crayon. Dessinez trois piquets A, C  et B et les
trois disques dans leur position initiale sur le plot A.

Déplacez alors les disques selon la méthode suivante~:

\begin{itemize}
\item  déplacez le  plus petit  disque vers  le plot  suivant  selon une
  permutation circulaire A-C-B-A ;
\item un seul des deux autres disques est déplaçable vers un seul piquet
  possible.
\end{itemize}

Réitérez (en  informatique à l'aide de boucles...)  ce mécanisme jusqu'à
ce que tous les disques soient sur C dans la bonne position.

On voit donc bien ici comment ça  marche ; il est plus délicat de savoir
pourquoi on arrivera au résultat.

Le programme est lui-même  assez compliqué à écrire~:~vous trouverez une
version en \texttt{C} (235 lignes...) à cette adresse~:

\begin{center}
  \href{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}
\end{center}








\subsection{Un exemple déjà traité en impératif}



On   définit la  partie entière  d'un réel $x$  comme étant  le plus
grand entier inférieur à $x$.



On part du fait que la  partie entière d'un nombre appartenant à $[0;1[$
est nulle.

Ensuite, on \og  descend \fg{} de $x$ vers  0 par pas de 1  si le nombre
est positif en montrant que $\lfloor x\rfloor=1+\lfloor x-1\rfloor$.

Si le nombre est négatif, on \og monte\fg{} vers 0 en montrant que $\lfloor x\rfloor=-1+\lfloor x+1\rfloor$.



\begin{algo}
\FUNC{partie\_entiere}{%
\pfarg{x}{flottant}}{entier}
\BEGIN
\IF{x>=0 et x<1}
\RETURN{0}
\ELSE
\IF{x>=0}
\RETURN{1+partie\_entiere(x-1)}
\ELSE
\RETURN{-1+partie\_entiere(x+1)}
\ENDIF
\ENDIF
\END
\end{algo}

Avec Maple:

\maple

\begin{lstlisting}
> partie_entiere:=proc(x)
    if x>=0 and x<1 then RETURN(0)
    elif x>0 then RETURN(1+partie_entiere(x-1))
    else RETURN(-1+partie_entiere(x+1))
    fi
  end: 
\end{lstlisting}



On notera que l'algorithme  récursif s'applique ici à des \textbf{réels}
et  non plus  à des  \textbf{entiers} :  on dépasse  ainsi le  cadre des
suites.   Pour  que l'algorithme  fonctionne,  on  raisonne sur  des
intervalles et non plus sur une valeur initiale. 



\vfill

\eject


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


\begin{listeexercices}

\subsection{Généralités}

  \begin{exercice}[Type booléen]
     Sans  utiliser  de structure  conditionnelle,
écrivez un algorithme, qui, lorsqu'on lui fournit les trois coefficients
d'un trinôme du second degré, renvoie VRAI si ce trinôme admet 2 racines
distinctes et FAUX sinon.
  \end{exercice}


% \begin{algo}
% \FUNC{deux\_racines}{%
% \pfarg{a,b,c}{réels}}{booléen}
% \VAR
% \DECLVAR{résultat}{booléen}
% \DECLVAR{delta}{réel}
% \ENDVAR
% \BEGIN
% \STATE{delta \recoit{} b*b-4*a*c}
% \STATE{résultat \recoit{} delta>0}
% \RETURN{résultat}
% \END 
% \end{algo}


  \begin{exercice}[Type booléen]
     Donnez  un
algorithme qui,  deux nombres étant  donnés, affiche VRAI s'ils  sont de
même signe et FAUX sinon. 
  \end{exercice}


% \begin{algo}
% \FUNC{meme\_signe}{%
% \pfarg{x,y}{réels}}{booléen}
% \VAR
% \DECLVAR{résultat}{booléen}
% \ENDVAR
% \BEGIN
% \STATE{résultat \recoit{} ((x<0) ET (y<0)) OU ((x>0) ET (y>0))}
% \RETURN{résultat}
% \END 
% \end{algo}

  \begin{exercice}[Flottants et processeur]
Sur Maple ou XCAS, observez et commentez ce que donne:

\maple
\begin{lstlisting}[caption={}]
> x:=10; y:=-5; z:=5.00000001;
> (x*y)+(x*z);
> x*(y+z);
\end{lstlisting}
\Pasc
  \end{exercice}



\subsection{Structures conditionnelles}

\begin{exercice}
  Écrivez un algorithme qui renvoie la valeur absolue d'un réel $x$.
\end{exercice}


\begin{exercice}
  Soit        un       système        $\bsys       a_{11}x+a_{12}y=b_1\\
  a_{21}x+a_{22}y=b_2\esys$.

Déterminez un algorithme  qui renvoie la solution de  ce système si elle
est unique.
\end{exercice}

  \begin{exercice}[Feu rouge]
Créez un algorithme qui renvoie le successeur de la couleur d'un feu tricolore.
  \end{exercice}




  \begin{exercice}[Mention au Bac]
 Créez un algorithme qui à une note de Bac renvoie la mention correspondante.   
  \end{exercice}

  \begin{exercice}[Remise]

On entre un montant hors taxe $ht$. On effectue une remise sur $ht$ selon la
régle suivante~:
\begin{itemize}
\item si $ht<2500$\texteuro{} alors il n'y a pas de remise~;
\item si $2500\leqslant ht<4000$\texteuro{} alors la remise est de 5\%~;
\item dans les autres cas la remise est de 8\%.
\end{itemize}

La TVA est de 19,6\%. On demande le prix TTC connaissant le prix HT.

  \end{exercice}


  \begin{exercice}[Années bissextiles]
Une année bissextile est une année dont le millésime, supérieur à 1583, est divisible par
4, sauf les limites de siècles qui ne sont pas multiples de 400.

Ainsi   \numprint{2000}  et   \numprint{2008}   sont  bissextiles   mais
\numprint{2100} et \numprint{2011} ne le sont pas.

Définissez alors un  algorithme qui reconnaît si un  millésime est celui
d'une   année   bissextile.   Vous   pourrez  utiliser   les   fonctions
\verb+quotient+ et \verb+reste+ de la division euclidienne.
  \end{exercice}

%   \begin{algo}
% \FUNC{bissextile}{%
% \pfarg{m}{entier>1583}}{booléen}
% \COMMENT{On  entre  un  millésime  sous  la  forme  d'un  nombre  entier
%   supérieur à  1583 (calendrier grégorien)  et qui renvoie vrai  ou faux
%   selon que le millésime correspond ou non à une année bissextile}
% \BEGIN
% \IF{reste(millesime,100)=0}\COMMENT{m est une frontière de siècle}
% \STATE{\RETURN(reste(millesime,400)=0)}\COMMENT{vrai si multiple de 400}
% \ELSE\COMMENT{m n'est pas une frontière de siècle}
% \STATE{\RETURN(reste(millesime,4)=0)}\COMMENT{Vrai si multiple de 4}
% \ENDIF
% \END
%   \end{algo}


\subsection{Programmation impérative}

  \begin{exercice}
Écrire un algorithme qui calcule très rapidement $x^{16}$ en n'utilisant
qu'une multiplication par ligne et des affectations.
  \end{exercice}


% \begin{algo}
% \FUNC{puissance\_16}{%
% \pfarg{x}{entier}}{entier}
% \VAR
% \DECLVAR{res}{entier}
% \ENDVAR
% \BEGIN
% \STATE{res \recoit{} x}
% \STATE{res \recoit{} res*res}
% \STATE{res \recoit{} res*res}
% \STATE{res \recoit{} res*res}
% \STATE{res \recoit{} res*res}
% \RETURN{res}
% \END 
% \end{algo}


  \begin{exercice}
    Déterminez un algorithme qui reçoit  un nombre entier de secondes et qui
renvoie quatre  entiers correspondant à sa conversion  en jours, heures,
minutes et  secondes. On pourra  utiliser une fonction \og  quo\fg{} qui
renvoie le quotient entier de la division de deux entiers.
  \end{exercice}

%  \begin{algo}
% \FUNC{conversion\_sec}{%
% \pfarg{x}{entier}}{liste de quatre entiers}
% \VAR
% \DECLVAR{j,h,m,s,temps}{entier}
% \ENDVAR
% \BEGIN
% \STATE{temps \recoit{} x}
% \STATE{j \recoit{} quo(temps,24*60*60)}
% \STATE{temps \recoit{} temps-j*(24*60*60)}
% \STATE{h \recoit{} quo(temps,60*60)}
% \STATE{temps \recoit{} temps-h*(60*60)}
% \STATE{m \recoit{} quo(temps,60)}
% \STATE{temps \recoit{} temps -m*60}
% \STATE{s \recoit{} temps}
% \RETURN{j,h,m,s}
% \END    
%   \end{algo}


  \begin{exercice}[Partie entière]
Donnez un algorithme impératif renvoyant la partie entière d'un réel $x$.
  \end{exercice}


  \begin{exercice}[Division euclidienne]
Déterminer  un algorithme  impératif  qui renvoie  le  quotient de  deux
entiers naturels non nuls $a$ et $b$.

Déterminer un  algorithme qui  renvoie le
reste entier de $a$ et $b$.
  \end{exercice}

  \begin{exercice}[Intégration numérique]
Déterminez  un algorithme impératif  qui donne  une valeur  approchée de
$\displaystyle\int_{t=a}^{t=b}f(t)\;\mathrm{d}t$   pour   une   certaine
fonction  $f$ continue  sur un  intervalle  $[a;b]$ par  la méthode  des
rectangles puis celle des trapèzes.
  \end{exercice}




  \begin{exercice}
On veut étudier la suite  de terme général $u_n=\frac{1}{n^2}$ ainsi que
la suite $v_n=\displaystyle\sum_{k=1}^{n}u_k$, avec
$n\in\bbn^*$.



Proposez un algorithme qui affiche $u_n$ et $v_n$ pour une valeur de $n$ donnée.
  \end{exercice}



\subsection{Récursion}


\begin{exercice}[Factorielle]
Écrivez un algorithme récursif qui donne $n!$ pour tout entier naturel $n$.
\end{exercice}


\begin{exercice}[Somme]
Écrivez un algorithme récursif qui calcule $\sum_{k=0}^{n}f(k)$ pour une fonction
$f$ donnée.
\end{exercice}



  \begin{exercice}[Division euclidienne]
Déterminer  un algorithme  récursif  qui renvoie  le  quotient de  deux
entiers naturels non nuls $a$ et $b$.

Déterminer un algorithme récursif qui renvoie le
reste entier de $a$ et $b$.
  \end{exercice}


  \begin{exercice}[Somme de chiffres]
Donnez un  algorithme récursif  qui calcule la  somme des  chiffres d'un
entier naturel $n$ écrit en base 10.
  \end{exercice}



  \begin{exercice}[Héron]
    
\textsc{Héron} d'Alexandrie a trouvé une méthode permettant de déterminer
une approximation de la racine  carrée d'un nombre positif vingt siècles
avant l'apparition des ordinateurs.

Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
(pourquoi~?) et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.

On  peut  montrer c'est  une  approximation  par  excès (en  développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).

On obtient  naturellement un algorithme... Donnez  une version récursive
 prenant en argument  le nombre dont on cherche la racine
carrée, une première approximation $x_0$ et une précision \verb+eps+.


  \end{exercice}



  \begin{exercice}[Décimales de e]
    

Posons $e_n=1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$

Alors on a aussi
$$e_n=1+1+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}\left(\cdots \left(\frac{1}{n-1}\left(1+\frac{1}{n}\right)\right)\right)\right)\right)$$


Un           exercice           classique           montre           que
$e-e_n \ie \frac{n+2}{n+1}\frac{1}{(n+1)!}$.

Ainsi,   pour  $n=167$,   on   obtiendra  $300$   bonnes  décimales   au
moins~:~trouvez-les~!

  \end{exercice}


%

  \begin{exercice}[Fractions continues dans Q]
    
 \begin{itemize}
  
\item Vous connaissez l'algorithme suivant~:

%\begin{minipage}{\textwidth}
\begin{eqnarray}
172&=&3\times\textcolor{0.2white}{51}+\textcolor{0.2white}{19}\\
\textcolor{0.2white}{51}&=&2\times\textcolor{0.2white}{19}+13\\
19&=&1\times13+6\\
13&=&2\times 6+1\\
6&=&6\times 1+0
\end{eqnarray}
%\end{minipage}

\item On peut donc facilement compléter  la suite d'égalité suivante~:


%\begin{minipage}{\textwidth}
$$\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+
  \frac{13}{19}}=\dots $$
%\end{minipage}

\item  Quand  tous les  numérateurs  sont  égaux à  1,  on  dit qu'on  a
  développé $\frac{172}{51}$ en
  fraction continue et pour simplifier l'écriture on note~:
$$\frac{172}{51}=[3; 2; \dots ]$$

\item Par exemple, on peut développer  $\frac{453}{54}$ en fraction continue.

\item Dans l'autre sens on peut écrire $[2; 5; 4]$ sous la forme d'une fraction irréductible.

  \end{itemize}

On suppose connus les algorithmes  donnant le reste et le quotient d'une
division euclidienne.

Écrivez un algorithme donnant le développement en fraction continue d'un
rationnel.



Écrivez ensuite un algorithme récursif qui effectue la transformation inverse.

  \end{exercice}






  \begin{exercice}[Fractions continues dans R]

En  fait,  l'étude précédente  correspond  à  un  cas particulier  d'une
définition plus générale.

Soit $x$ un  réel non entier. On construit une  suite entière $(z_n)$ de
la manière suivante~:


\[x=z_0+\frac{1}{x_1}\qquad          z_0=\lfloor          x\rfloor\qquad
x_1=\frac{1}{x-z_0}\]

puis, tant que $x_k$ n'est pas entier~:


\[x_k=z_k+\frac{1}{x_{k+1}}\qquad          z_k=\lfloor          x_k\rfloor\qquad
x_{k+1}=\frac{1}{x_k-z_k}\]


Le  développement de  $x$ en  fractions  continues est  alors donné  par
$[z_0,z_1,z_2,\dots]$, cette liste pouvant être infinie.
    

Écrivez un  algorithme récursif qui donne $n$  chiffres du développement
en fraction continue d'un nombre $x$ donné.
  \end{exercice}


  \begin{exercice}[Dichotomie]
    

Pour résoudre une équation  du type $f(x)=0$, on recherche graphiquement
un intervalle $[a,b]$ où la fonction semble changer de signe.

On note ensuite $m$ le milieu du segment $[a,b]$. On évalue le signe de $f(m)$.

Si c'est  le même  que celui  de $f(a)$ on  remplace $a$  par $m$  et on
recommence.  Sinon, c'est $b$  qu'on remplace  et on  recommence jusqu'à
obtenir la précision voulue.

Écrivez  un algorithme récursif  qui prend  comme argument  une fonction
$f$, les bornes $a$ et $b$ d'un intervalle et une précision $eps$.

On  remarquera  ici que  la  récursion  se  fait sans  faire  intervenir
d'entier~:~le test d'arrêt est effectué sur la précision du calcul.

  \end{exercice}

  \begin{exercice}
On  définit  deux fonction  \verb+tete+  et  \verb+queue+ qui  renvoient
respectivement le premier  élément d'une liste et la  liste privée de sa
tête.


La syntaxe dépend des langages.

Sur Maple cela donne:
\maple
\begin{lstlisting}[caption={}]
> tete:=proc(L)
   RETURN(L[1])
  end:
\end{lstlisting}


\begin{lstlisting}[caption={}]
> queue:=proc(L)
   if nops(L)=1 then RETURN([])
   else RETURN(L[2..nops(L)])
   fi
  end:
\end{lstlisting}



Écrivez à  présent une fonction  récursive qui renvoie le  maximum d'une
liste de nombres.

  \end{exercice}


  \begin{exercice}[Palindrome]
Écrivez un algorithme récursif qui vérifie si une liste est un palindrome.
  \end{exercice}








  \begin{exercice}[Nombres parfaits]

Un nombre parfait  est un nombre entier $n$  strictement supérieur à $1$
qui est égal à la somme de ses diviseurs (sauf $n$ bien sûr~!).

\begin{enumerate}
\item Il y en a un caché entre 1 et 10: trouvez-le...
\item Écrivez un algorithme récursif qui donne la liste des diviseurs
  d'un entier autres que lui-même.
\item  Écrivez un  algorithme qui  calcule la  somme des  éléments d'une
  liste.
\item  Écrivez un  algorithme  qui  détermine si  un  nombre entier  est
  parfait.
\item Écrivez un algorithme récursif qui donne la liste des nombres
parfaits entre 1 et un nombre $n$ donné.
\end{enumerate}

  \end{exercice}



  \begin{exercice}[Décomposition en base 2]

Une  méthode  pour  obtenir  l'écriture   en  base  2  d'un  nombre  est
d'effectuer des divisions successives. Par exemple pour 11~:

\begin{center}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{11}{2}\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{5}{2}
\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{2}{2}
\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{1}{2}

\end{center}

\begin{align*}
11 &=\Bigl(2\times5+1\Bigr)
\\ &=\Bigl(2\times\bigl(2\times2+1\bigr)+1\Bigr)
\\ &=\Bigl(2\times\bigl(2\times(2\times 1)+1\bigr)+1\Bigr)
\\ &=\Bigl(2\times (2^2+1)+1\Bigr)
\\ &=2^3+2+1
\\ &=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0 
\end{align*}



L'écriture de  11 en base  2 est donc  1011~:~c'est la liste  des restes
obtenus mais dans l'ordre inverse.


La méthode est facilement généralisable.  


Écrivez un algorithme récursif qui donne la décomposition d'un entier en
base 2 sous forme d'une liste.
  \end{exercice}






  \begin{exercice}[Algorithme de Hörner]

Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.




On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. En fait il y a au maximum $2\times$degré
de P opérations (voire moins avec les zéros).



On définit  un polynôme par la  donnée de ses  coefficients dans l'ordre
décroissant des exposants des monômes.

Déterminez  un   algorithme  récursif  qui  prend   comme  argument  les
coefficients  d'un polynôme P  et un  nombre $x$  et qui  calcule $P(x)$
suivant le schéma de Hörner.
  \end{exercice}



\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc;



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