\chapterimage{structure}

\chapter{Structures de données I}
\Pasc


\section{Enregistrements}

\subsection{Une classe de rationnels}

Avant de rentrer dans le vif  du sujet, nous allons nous familiariser un
peu avec la  notion d'enregistrement (\lstinline+RECORD+ en Pascal  dont on a
parlé à la section \vref{record}) qui
s'apparente un  peu à la  notion de \textit{classe} de  la programmation
orientée objet (POO).

Nous   allons   donc   créer   une  classe   d'objet   assez   familiers
mathématiquement parlant: les rationnels. Sur Pascal, on crée un nouveau
\lstinline+TYPE+:


\begin{lstlisting}[caption={}]
TYPE
 Rationnel=RECORD
  Num, Den : INT64;
  END; 
\end{lstlisting}


Si \lstinline+r+  est de type  \lstinline+Rationnel+, alors \lstinline+r.Num+  sera son
dénominateur de type \lstinline+INT64+ et \lstinline+r.Den+ son dénominateur.

On  peut alors imaginer  une procédure  qui lit  un rationnel  entré par
l'utilisateur.   On  découvre  la   procédure  \lstinline+HALT+   qui  permet
d'interrompre un  programme en cours d'exécution et  possède un argument
facultatif (du type \lstinline+WORD+) correspondant à un code de sortie.

\begin{lstlisting}[caption={}]
PROCEDURE EntrerR(VAR r:Rationnel);
BEGIN
 WRITELN('Vous allez entrer un rationnel');
 WRITE('Numerateur   : '); READLN(r.Num);
 WRITE('Denominateur : '); READLN(r.Den);
 IF r.Den=0 THEN
  BEGIN
   WRITELN('Le denominateur doit etre non nul !.');
   HALT;
  END;
END;        
\end{lstlisting}




On va  essayer de  faire un  peu plus moderne  (si, si,  c'est possible,
même avec Pascal...)  en créant une procédure qui nous permette d'écrire
un rationnel sous  la forme \og a/b \fg{} en  faisant de la manipulation
de chaînes de caractères à l'aide des fonctions \lstinline+POS+, \lstinline+COPY+,
\lstinline+VAL+ (voir la section \vref{string}).


\begin{lstlisting}[caption={}]
PROCEDURE EntrerR2(VAR rat:Rationnel);
VAR
 R,N,D:STRING;
 p,code_err:WORD;
BEGIN
 READLN(R);{on entre le nombre sous la forme a/b }
 p:=POS('/',R); { on repere le / }
 IF p<>0 THEN { si ce / existe bien }
  BEGIN
   D:=COPY(R,p+1,LENGTH(R)-p); { on repere le denominateur }
   N:=COPY(R,1,p-1); { et le numerateur }
  END
 ELSE
   BEGIN
     N:=R;
     D:='' { on peut entrer un entier sans / }
   END;
 VAL(N,rat.Num,code_err); {on transforme la chaine N en nombre}
 IF (code_err=0) THEN {si la conversion s''est bien passee}
  IF D<>'' THEN VAL(D,rat.Den,code_err) ELSE rat.Den:=1;
  {on distingue les entiers des non entiers}
 IF code_err<>0 THEN {si l'une des conversions s'est mal passee}
  BEGIN
   WRITELN('Erreur d''ecriture');
   READLN;
   HALT
  END;
 IF rat.Den=0 THEN {on ne divise pas par zero !}
  BEGIN
   WRITELN('Denominateur nul');
   READLN;
   HALT
  END;
END;                    
\end{lstlisting}



On demande aussi à Pascal d'afficher le rationnel de manière conviviale:

\begin{lstlisting}[caption={}]
PROCEDURE Afficher(r:Rationnel);
BEGIN
 WRITELN(r.Num,'/',r.Den);
END;   
\end{lstlisting}

Maintenant,  à  vous de  jouer:  créez  des  fonctions qui  simplifient,
additionnent,   soustraient,  multiplient,   divisent,  élèvent   à  une
puissance entière des rationnels.


\subsection{Méthode de \textsc{Héron}}


Nous    avons    déjà     étudié    l'algorithme    de    \textsc{Héron}
\vpageref{heron}.  Utilisez-le   pour  obtenir  des  approximations
rationnelles d'irrationnels à l'aide des outils précédemment introduits.


\subsection{Fractions continues}\label{fractions_continues}

 \begin{itemize}
  
\item Vous connaissez l'algorithme suivant~:

\begin{eqnarray*}
172&=&3\times\textcolor{black!70}{51}+\textcolor{black!40}{19}\\
\textcolor{black!70}{51}&=&2\times\textcolor{black!40}{19}+13\\
19&=&1\times13+6\\
13&=&2\times 6+1\\
6&=&6\times 1+0
\end{eqnarray*}

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

\[\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+\frac{13}{19}}=\dots     \]

\end{itemize}

 \textbf{ Pratique du développement}\\
\begin{itemize}

\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}


Nous voudrions utiliser Pascal  pour obtenir de tels développements mais
il  nous faudrait  pouvoir travailler  sur des  listes qui  seront notre
premier  exemple de  \textit{structures ordonnées}  mais avant,  il nous
faut découvrir un nouvel outil...


\section{Pointeurs et pointés}

Une fois n'est  pas coutume, nous allons parler  un peu technique. Quand
vous déclarer une  variable sur Pascal, elle est  forcément d'un certain
type. Selon ce type, Pascal va réserver un espace mémoire d'une certaine
taille. Or le compilateur ne va pas accepter des variables lui demandant
trop  d'espace   mémoire.  Une  astuce   est  donc  de  passer   par  un
\textit{pointeur} qui  est une  variable qui contient  l'adresse mémoire
d'une autre variable déjà stockée.  Ainsi, à la compilation, un pointeur
ne fera pas grincer la machine car la taille d'un pointeur est de quatre
octets, quelque soit la variable pointé. 

C'est un peu  comme quand vous écrivez l'adresse de  votre maison sur un
bout de papier: vous pouvez ainsi, en quelque sorte, mettre votre maison
dans une  enveloppe sans que le  facteur n'ai a  porter plusieurs tonnes
de parpaings...


Cela permet  une gestion \textit{dynamique} de la  mémoire: par exemple,
jusqu'à  maintenant, on a  utilisé des  sortes de  listes sous  forme de
tableau dont il fallait déclarer à l'avance la taille, ce qui correspond
à une gestion \textit{statique} de  la mémoire et conduit à une mauvaise
utilisation de la mémoire.

Par  exemple, si vous  cherchez à  définir la  liste des  diviseurs d'un
entier, vous ne savez pas a priori quelle sera sa taille: celle-ci varie
dynamiquement au cours de l'exécution du programme.


Avec les  pointeurs, seuls ceux-ci se  voient allouer de  la mémoire (et
très peu: 4 octets) pour toute la durée de l'exécution du programme. 

Nommons commodément \lstinline+p+ le pointeur. La variable pointée sera alors
désignée par  \lstinline+p^+. Pour pouvoir  l'utiliser, il faut  lui réserver
dynamiquement de  la mémoire en  tapant \lstinline+NEW(p)+. Dès qu'on  n'en a
plus  besoin,   on  peut   libérer  la  place   en  mémoire   en  tapant
\lstinline+DISPOSE(p)+.

On peut donc  allouer et vider de la mémoire à  une variable pointée par
un même pointeur.

On définit deux pointeurs.
Que donne les quatre séquences d'instructions suivantes:


\begin{lstlisting}[caption={}]
VAR a,b : ^INTEGER;

BEGIN
NEW(a); a^:=1; b:=a; WRITELN(b^);
NEW(a);NEW(b); a^:=1; b:=a; WRITELN(b^);
NEW(a); a^:=2; b:=a; DISPOSE(a); WRITELN(b^);
NEW(a); a^:=1; b:=a; b^:=2; WRITELN(a^);
READLN
END.             
\end{lstlisting}






\section{Listes chaînées définies récursivement}


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

Récursivement, une liste c'est tout  simple: c'est soit le vide, soit un
élément suivi d'une liste, ce qui s'écrit de manière standard:

\begin{center}
\begin{verbatim}
Liste = Nil + Élément x Liste
\end{verbatim}
\end{center}

le  \lstinline+x+  renvoyant  au   produit  cartésien  et  \lstinline+Nil+  (  \og
\textit{ Not In List}\fg{}) représentatnt une liste vide.

\subsection{Comment?}

Une liste sera représentée par un pointeur vers un premier chaînon constitué
d'un élément (la tête) et d'une liste (la queue):


\begin{lstlisting}[caption={}]
TYPE
   Element = INTEGER;
   Liste = ^Chainon;

   Chainon = RECORD
     tete  : Element;
     queue : Liste;
   END;
\end{lstlisting}

Cette  construction correspond  bien  à la  définition récursive  donnée
précédemment.


\subsection{Outils de base}


Il est temps  de construire quelques outils qui  nous seront fort utiles
par la suite.

\begin{lstlisting}
FUNCTION Queue(L:Liste):Liste;
BEGIN
 Queue:=L^.queue;
END;


FUNCTION Tete(L:Liste):Element;
BEGIN
 Tete:=L^.tete;
END;


FUNCTION Est_Vide(L:Liste):BOOLEAN;
BEGIN
 Est_Vide:=(L=NIL);
END;
\end{lstlisting}

Ensuite, on veut ajouter un élément à une liste \og par la tête\fg{}:

\begin{lstlisting}
FUNCTION Colle_en_tete(e:Element; L:Liste):Liste;
VAR L2:Liste;
BEGIN
 NEW(L2);
 L2^.tete:=e;
 L2^.queue:=L;
 Colle_en_tete:=L2;
END;                 
\end{lstlisting}


Pour concaténer deux listes, la première étant à droite:

\begin{lstlisting}[caption={}]
FUNCTION Concat(L1,L2:Liste):Liste;
  BEGIN
    IF L1 = NIL THEN
     Concat:=L2
    ELSE
     Concat:=Colle_en_tete(L1^.tete,Concat(L1^.queue,L2))
  END;       
\end{lstlisting}


Pour ajouter un élément \og par la queue\fg{}:


\begin{lstlisting}[caption={}]
FUNCTION Colle_en_queue(e:Element; L:Liste):Liste;
VAR L2:Liste;
BEGIN
 NEW(L2);
 L2^.tete:=e;
 L2^.queue:=NIL;
 Colle_en_queue:=Concat(L,L2)
END;  
\end{lstlisting}


On aura également besoin de créer des listes:


\begin{lstlisting}[caption={}]
FUNCTION Cree:Liste;
{ on fait rentrer les valeurs par la gauche }
VAR
 L:Liste;
 e:Element;
BEGIN
 L:=NIL;
 REPEAT
  WRITE('Rentrer une valeur : '); READLN(e);
  IF e>=0 THEN L:=Colle_en_queue(e,L);
 UNTIL e<0;
 Cree:=L;
END;           
\end{lstlisting}

On  veut  pouvoir  afficher  les  listes.   Par  commodité  ici,  on  ne
travaillera qu'avec des entiers 
positifs:  le signal  de fin  de liste  sera donc  l'entrée  d'un nombre
négatif... Voici comment afficher les listes de la gauche vers la droite:

\begin{lstlisting}
PROCEDURE Affiche(L:Liste);
BEGIN
 IF Est_Vide(L) THEN WRITELN
 ELSE
  BEGIN
   WRITE(Tete(L):5); { pour espacer les elements }
   Affiche(Queue(L));
  END;
END;           
\end{lstlisting}

Pour calculer leur longueur:

\begin{lstlisting}[caption={}]
FUNCTION Longueur(L:Liste):Integer;
BEGIN
 IF Est_Vide(L) THEN Longueur:=0
 ELSE Longueur:=1+Longueur(Queue(L));
END;  
\end{lstlisting}

Pour extraire le  $i$-eme élément d'une liste en  commençant à compter à
partir de 1:

\begin{lstlisting}[caption={}]
FUNCTION ieme(L:Liste;pos:INTEGER):Element;
BEGIN
  IF pos=1 THEN ieme:= L^.tete
  ELSE ieme:=ieme(L^.queue,pos-1)
END;    
\end{lstlisting}


Testons en vrai:


\begin{lstlisting}[caption={}]
VAR L1,L2,L:Liste;
    i : INTEGER;

BEGIN
 L1:=Cree;
 Affiche(L1);
 WRITELN;
 WRITELN(' La longueur de la liste est : ',Longueur(L1));
 L2:=Cree;
 Affiche(L2);
 WRITELN;
 WRITELN(' La longueur de la liste est : ',Longueur(L2));
 L:=Concat(L1,L2);
 WRITELN(' La liste concatenee est : ');
 Affiche(L);
 WRITELN;
 WRITELN(' La longueur de la liste concatenee est : ',Longueur(L));
 WRITELN(' Entrez un entier positif ');
 READLN(i);
 IF i<= Longueur(Concat(L1,L2)) THEN
    WRITELN('Le ',i,'eme element de la liste concatenee est : ',ieme(L,i))
 ELSE
    WRITELN('Cet entier est trop grand');
 WRITE('Appuyer sur Entree pour terminer.');
 READLN;
END.  
\end{lstlisting}


Par exemple:

\begin{Verbatim}
Rentrer une valeur : 1
Rentrer une valeur : 2
Rentrer une valeur : 3
Rentrer une valeur : 4
Rentrer une valeur : 5
Rentrer une valeur : 6
Rentrer une valeur : -1
    1    2    3    4    5    6

 La longueur de la liste est : 6
Rentrer une valeur : 7
Rentrer une valeur : 8
Rentrer une valeur : 9
Rentrer une valeur : -1
    7    8    9

 La longueur de la liste est : 3
 La liste concatenee est : 
    1    2    3    4    5    6    7    8    9

 La longueur de la liste concatenee est : 9
 Entrez un entier positif 
3
Le 3eme element de la liste concatenee est : 3
Appuyer sur Entree pour terminer.
\end{Verbatim}



\subsection{Fractions continues}


Revenons à  notre problème de  développement de rationnels  en fractions
continues (cf section \vref{fractions_continues}).



\begin{lstlisting}[caption={}]
FUNCTION inverseFC(r:Rationnel):Rationnel;
  VAR ir:Rationnel;
  BEGIN
  ir.Num:=r.Den;
  ir.Den:=r.Num MOD r.Den;
  inverseFC:= ir
  END;


FUNCTION fc(r:Rationnel):Liste;
 BEGIN
  IF r.Den=0 THEN
    fc:= NIL
  ELSE
    fc:=Colle_en_tete(r.Num DIV r.Den , fc(inverseFC(r)))
 END;

VAR r:Rationnel;

BEGIN
 WRITE('Entrer un rationnel : '); EntrerR2(r);
 WRITELN;
 WRITELN('Le developpement en fraction continue de ',r.Num,'/',r.Den ,' est : ');
 Affiche(fc(r));
 WRITE('Appuyer sur Entree pour terminer.');
 READLN
END.
\end{lstlisting}


Ce qui donne:

\begin{Verbatim}
Entrer un rationnel : 172/51
Le developpement en fraction continue de 172/51 est : 
    3    2    1    2    6
Appuyer sur Entree pour terminer.
\end{Verbatim}







\section{Listes chaînées définies itérativement}
\subsection{Principe}

Cette fois, on définit une liste à partir de son premier élément, de
son  nombre d'éléments  et de  pointeur  qui permet  de progresser  d'un
élément au suivant. C'est plus lourd à utiliser.

\begin{lstlisting}[caption={}]
TYPE 
  Elem = INTEGER;
  Pointeur = ^Maillon;
  Maillon = RECORD
    element : Elem;
    suivant : Pointeur;
    END;
  Liste = RECORD
    taille : WORD;
    premier : Pointeur;
  END;
\end{lstlisting}

\subsection{Outils de base}

Comme pour le type récursif, on va construire un certain nombre d'outils
de base.


\subsubsection{Liste vide}


\begin{lstlisting}[caption={}]
PROCEDURE
\end{lstlisting}



\section{Piles}

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

C'est une liste mais qui a des accès limités comme une pile d'assiettes:
on ne  peut y accéder  que par  le sommet, que  ce soit pour  ajouter ou
supprimer une assiette ou regarder son motif.

On utilisera le même type que pour les listes définies récursivement.

On n'utilisera que les fonctions:
\begin{itemize}
\item \verb+Empiler(e:Element ; p:Pile):Pile+ qui ajoute une assiette;
\item \verb+Depiler(p:Pile):Piles;)+ qui enlève l'assiette du sommet;
\item \verb+Sommet(p:Pile):Element;)+ qui regarde le motif de l'assiette
  visible au sommet.
\end{itemize}


On  définira un  type \verb+Pile+  adapté  du type  \verb+List+ mais  en
changeant les noms:

\begin{lstlisting}[caption={}]
TYPE
Element = STRING;
Pile = ^Assiette;
Assiette = RECORD
  motif : Element;
  dessous : Pile;
END;   
\end{lstlisting}


\subsection{Outils}

Nous aurons besoin de construire...deux constructeurs:

\begin{itemize}
\item une pile vide:

\begin{lstlisting}[caption={}]
FUNCTION PileVide : Pile;
BEGIN
 PileVide:=NIL
END;
\end{lstlisting}

\item une pile en ajoutant un élément à une pile déjà existante:

\begin{lstlisting}[caption={}]
FUNCTION  Empliler(e:Element ; p:Pile):Pile;
VAR plate : Pile;
BEGIN
 NEW(plate);
 plate^.motif := e;
 plate^.dessous := p;
 Empiler:=plate
END;       
\end{lstlisting}

\end{itemize}

On aura besoin d'un prédicat testant si une liste est vide:


\begin{lstlisting}
FUNCTION EstVide(p:Pile):BOOLEAN;
BEGIN
 EstVide:=(p=NIL)
END;    
\end{lstlisting}


Une fonction retournant le sommet de la pile:

\begin{lstlisting}[caption={}]
FUNCTION Sommet(p:Pile):Element;
BEGIN
 IF p=NIL THEN {On traite l'erreur}
   BEGIN
     WRITELN('Pile vide');
     HALT
   END
 ELSE Sommet:=p^.motif
END;     
\end{lstlisting}



Une fonction enlevant le sommet:

\begin{lstlisting}[caption={}]
FUNCTION Depiler(p:Pile):Pile;
BEGIN
 Depiler:=p^.dessous;
END;
\end{lstlisting}

Pour  le traitement purement  \og Pascalien\fg{},  on aura  besoin d'une
procédure affichant une pile:


\begin{lstlisting}
PROCEDURE Affiche(p:Pile);
VAR ptemp:Pile;
BEGIN
 ptemp:=p;
 WHILE  NOT EstVide(ptemp) DO
  BEGIN
   WRITELN(Sommet(ptemp));
   ptemp:=Depiler(ptemp);
  END;
END;  
\end{lstlisting}


et créant une pile (attention à l'ordre!):

\begin{lstlisting}[caption={}]
FUNCTION Cree:Pile;
VAR
 P:Pile;
 e:Element;
BEGIN
 P:=PileVide;
 WHILE e<>'Stop' DO
  BEGIN
  WRITE('Rentrer une valeur ou un operateur : '); READLN(e);
  P:=Empiler(e,P);
  END;
  Cree:=Depiler(P)
END;      
\end{lstlisting}





\subsection{Évaluation d'une expression arithmétique postfixée}

Commençons par  un cas  simple: on multiplie  ou additionne  des nombres
positifs et  nous allons implémenter ces opérations  de manière linéaire
donc sans utiliser de parenthèses.

Par exemple, 5 4 3 + * donne 35.

Comme les nombres et les opérateurs sont apparemment de types différents,
on va utiliser des chaînes de caractères.

On lit  maintenant une pile et  on empile les valeurs  en effectuant des
opérations sur les  deux derniers nombres empilés dès  qu'arrive en tête
de pile une opération binaire et on empile le résultat.



\begin{lstlisting}[caption={}]
FUNCTION polonais(pol:Pile):Pile;
VAR pile_nb,pile_tmp:Pile;
    nb,nb1,nb2,indic : Integer;
    unite,ch : STRING;

BEGIN
 pile_nb:=PileVide;
 pile_tmp:=pol;
 WHILE (NOT EstVide(pile_tmp)) DO
  BEGIN
   unite:=Sommet(pile_tmp);
   VAL(unite,nb,indic);
   CASE indic OF
     0 : pile_nb:=Empiler(unite,pile_nb)
     ELSE
      BEGIN
        VAL(Sommet(pile_nb),nb2,indic);
        pile_nb:=Depiler(pile_nb);
        VAL(Sommet(pile_nb),nb1,indic);
        pile_nb:=Depiler(pile_nb);
        CASE unite[1] OF
          '+' : BEGIN
                 STR(nb1+nb2,ch);
                 pile_nb:=Empiler(ch,pile_nb);
                END;
          '*' : BEGIN
                 STR(nb1*nb2,ch);
                 pile_nb:=Empiler(ch,pile_nb);
                END;
        END;
      END;
   END;
   pile_tmp:=Depiler(pile_tmp);
  END;
polonais:=pile_nb;
END;                 
\end{lstlisting}



Par exemple, en reprenant l'exemple donné plus haut:

\begin{lstlisting}[caption={}]
VAR P,Pol:Pile;

BEGIN
P:=Cree;
Affiche(P);
READLN;
WRITELN('Le resultat de l''operation est : ');
Pol:=polonais(P);
Affiche(Pol);
READLN
END.         
\end{lstlisting}

donne:

\begin{Verbatim}
Rentrer une valeur ou un operateur : *
Rentrer une valeur ou un operateur : +
Rentrer une valeur ou un operateur : 3
Rentrer une valeur ou un operateur : 4
Rentrer une valeur ou un operateur : 5
Rentrer une valeur ou un operateur : Stop
5
4
3
+
*

Le resultat de l'operation est : 
35
\end{Verbatim}

\vfill

\eject


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


\begin{listeexercices}

  \begin{exercice}[Manipulations de listes chaînées définies récursivement]
    \begin{enumerate}
    \item Déterminer:
      \begin{lstlisting}[caption={}]
Retourne(L:Liste):Liste;
      \end{lstlisting}

qui écrit une liste
      à l'envers.
\item Déterminer: 


  \begin{lstlisting}[caption={}]
Appartient(e:Element;L:Liste):BOOLEAN;
  \end{lstlisting}

   qui
  vérifie si un élément appartient à une liste.
\item Déterminer: 

  \begin{lstlisting}[caption={}]
Rechercher(e:Element;L:Liste):WORD;
  \end{lstlisting}

    qui
  détermine  le rang  de la  première apparition  d'un élément  dans une
  liste. Renvoie $-1$ si l'élément n'appartient pas à la liste.
\item Déterminer: 

  \begin{lstlisting}[caption={}]
Extraire(d,f:WORD; L:Liste):Liste;
  \end{lstlisting}

 qui extrait
  la  sous-liste  des  éléments  de  \lstinline+L+ compris  entre  les  rangs
  \lstinline+d+ et \lstinline+f+ compris.

\item Déterminer:

  \begin{lstlisting}[caption={}]
InsererMilieu(e:Element;pos:WORD;L:Liste):Liste;
  \end{lstlisting}

qui insère  un élément \lstinline+e+ à  la position \lstinline+pos+  dans la liste
\lstinline+L+.

\item Déterminer:

  \begin{lstlisting}[caption={}]
Filtre(L:Liste):Liste;
  \end{lstlisting}

qui filtre les éléments d'une  liste selon un certain test. Par exemple,
on écrira le filtre pour le test \lstinline+.>3+.

\item Déterminer:

  \begin{lstlisting}[caption={}]
Supprimer(pos:WORD ; L:Liste):Liste;
  \end{lstlisting}

qui supprime l'élément de rang \lstinline+pos+ de la liste \lstinline+L+.
    \end{enumerate}
  \end{exercice}







  \begin{exercice}[Liste des diviseurs]
Déterminer une fonction qui donne la liste des diviseurs d'un entier. On
gardera en mémoire que les diviseurs vont souvent par deux...
  \end{exercice}



  \begin{exercice}[Liste des nombres parfaits]
Un  nombre parfait  est  un nombre  égal  à la  somme  de ses  diviseurs
(distincts de lui-même...).

Déterminer  une  fonction  qui  donne  la  liste  des  nombres  parfaits
inférieurs à un entier $n$ donné.
  \end{exercice}








  \begin{exercice}[Crible d'Ératosthène récursif]
    \begin{enumerate}
    \item Créer une fonction récursive qui écrit la liste des entiers compris
      entre les entiers $a$ et $b$.
\item Créer une fonction récursive qui retire les multiples d'un entier $n$ dans
  une liste $L$.
\item Créer  finalement une fonction  récursive qui dresse la  liste des
  entiers premiers inférieurs à $n$ selon le principe du crible d'Ératosthène.
    \end{enumerate}
  \end{exercice}




  \begin{exercice}[Décomposition en facteurs premiers récursive]
En utilisant \verb+crible+, créer une  fonction qui renvoie la liste des
facteurs de sa décomposition en produit de facteurs premiers.
  \end{exercice}


  \begin{exercice}[Changement de base récursif]
Déterminer une fonction qui donne la liste des chiffres de l'écriture en
base $b$  (avec $2 \leqslant b  \leqslant 10$) d'un entier  $n$ écrit en
base 10.
  \end{exercice}


  \begin{exercice}[Épreuve de l'X, 2004]
Il    s'agit    de     chercher    le    premier    problème    intitulé
\textit{Sélection}. Pour  le deuxième, il faudra  attendre l'an prochain
et l'étude des arbres.
\href{http://www.imprimerie.polytechnique.fr/EnLignes/Files/04\_Info\_MPInfo\_4h.pdf}{http://www.imprimerie.polytechnique.fr/\\
  EnLignes/Files/04\_Info\_MPInfo\_4h.pdf}
  \end{exercice}


\end{listeexercices}






\vfill

\eject
\section{DES SOLUTIONS}


\begin{listeexercices}


  \begin{exercice}[Manipulations de listes chaînées définies récursivement]
    \begin{enumerate}
    \item Une solution:
      \begin{lstlisting}[caption={}]
FUNCTION Retourne(L:Liste):Liste;
BEGIN
  IF Est_Vide(L) THEN
     Retourne:=NIL
  ELSE
     Retourne:=Concat(Retourne(Queue(L)),Colle_en_tete(Tete(L),NIL))
END;    
      \end{lstlisting}

et une autre:

\begin{lstlisting}[caption={}]
FUNCTION Retourne2(L:Liste):Liste;
BEGIN
  IF Est_Vide(L) THEN
     Retourne2:=NIL
  ELSE
     Retourne2:=Colle_en_queue(Tete(L),Retourne2(Queue(L)))
END;       
\end{lstlisting}

\item Testons si un élément appartient à une liste récursivement:

  \begin{lstlisting}[caption={}]
FUNCTION Appartient(e:Element;L:Liste):BOOLEAN;
BEGIN
 IF Est_Vide(L) THEN Appartient:=FALSE
 ELSE IF Tete(L)=e THEN Appartient:=TRUE
      ELSE Appartient:=Appartient(e,Queue(L))
END;            
  \end{lstlisting}

\item On utilise \lstinline+Appartient+:
\begin{lstlisting}
FUNCTION Rechercher(e:Element;L:Liste):SHORTINT;
BEGIN
 IF Appartient(e,L) THEN
     IF Tete(L)=e THEN Rechercher:=1
     ELSE Rechercher:=1+Rechercher(e,Queue(L))
 ELSE Rechercher:= -1
END;            
\end{lstlisting}

\item Une version récursive:

  \begin{lstlisting}[caption={}]
FUNCTION Extraire(d,f:WORD; L:Liste):Liste;
  BEGIN
   IF d>f THEN Extraire:=NIL
   ELSE Extraire:=Colle_en_tete(ieme(L,d),Extraire(d+1,f,L))
  END;   
  \end{lstlisting}


\item En utilisant les fonctions précédentes:

  \begin{lstlisting}[caption={}]
FUNCTION InsererMilieu(e:Element;pos:WORD;L:Liste):Liste;
BEGIN
 IF pos=1 THEN InsererMilieu:=Colle_en_tete(e,L)
 ELSE
 InsererMilieu:=Concat(Concat(Extraire(1,pos-1,L),Colle_en_tete(e,NIL)),Extraire(pos,longueur(L),L))
END;    
  \end{lstlisting}

\item Pour le test \lstinline+.>3+:

  \begin{lstlisting}[caption={}]
FUNCTION Filtre(L:Liste):Liste;
BEGIN
 IF Est_Vide(L) THEN Filtre:=L
 ELSE
   IF Tete(L) > 3 THEN
         Filtre:=Colle_en_tete(Tete(L),Filtre(Queue(L)))
   ELSE
         Filtre:=Filtre(Queue(L))
END;                
  \end{lstlisting}

\item Toujours récursivement:

  \begin{lstlisting}[caption={}]
FUNCTION Supprimer(pos:WORD ; L:Liste):Liste;
BEGIN
 IF (pos >=1) AND (pos <= Longueur(L)) THEN
  IF pos=1 THEN Supprimer:=Queue(L)
  ELSE Supprimer:=Colle_en_tete(Tete(L),Supprimer(pos-1,Queue(L)))
 ELSE Supprimer:=L
END;        
  \end{lstlisting}
 
    \end{enumerate}


Toutes ces fonctions peuvent être  testées sous Pascal avec le programme
principal suivant:

\begin{lstlisting}[caption={}]
VAR L1,L2,L:Liste;
    i,d,f,pos1,poss : INTEGER;
    e,e1 : Element; 

BEGIN
 L1:=Cree;
 Affiche(L1);
 WRITELN;
 WRITELN(' La longueur de la liste est : ',Longueur(L1));
 L2:=Cree;
 Affiche(L2);
 WRITELN;
 WRITELN(' La longueur de la liste est : ',Longueur(L2));
 L:=Concat(L1,L2);
 WRITELN(' La liste concatenee est : ');
 Affiche(L);
 WRITELN;
 WRITELN(' La longueur de la liste concatenee est : ',Longueur(L));
 WRITELN(' Entrez un entier positif ');
 READLN(i);
 IF i<= Longueur(Concat(L1,L2)) THEN
    WRITELN('Le ',i,'eme element de la liste concatenee est : ',ieme(L,i))
 ELSE
    WRITELN('Cet entier est trop grand');
 WRITELN;
 WRITELN(' La liste 1 a l''envers est : ');
 Affiche(Retourne(L1));
  WRITELN(' La liste 2 a l''envers est : ');
 Affiche(Retourne2(L2));
 WRITELN;
 WRITELN(' Entrer un element  :');
 READLN(e);
 IF Appartient(e,L) THEN
    BEGIN
    WRITELN(e,' appartient a la liste.');
    WRITELN('Il apparait pour la premiere fois au rang ',Rechercher(e,L))
    END
 ELSE
    BEGIN
    WRITELN(e,' n''appartient pas a la liste 1.');
    END;
 WRITELN;
 WRITELN(' Entrer le rang du premier element de la liste extraite de L1 : ');
 READLN(d);
 WRITELN(' Entrer le rang du dernier element de la liste extraite de L1 : ');
 READLN(f);
 WRITELN(' La liste extraite est : ');
 Affiche(Extraire(d,f,L1));
 WRITELN(' Entrer l''element a inserer :');
 READLN(e1);
 WRITELN('Entrer le rang d''insertion :');
 READLN(pos1);
 Affiche(InsererMilieu(e1,pos1,L));
 WRITELN('La liste L filtree est :');
 Affiche(Filtre(L));
 WRITELN('Entrer le rang a supprimer :');
 READLN(poss);
 Affiche(Supprimer(poss,L));
 WRITELN('Appuyer sur Entree pour terminer.');
 READLN;
END.                
\end{lstlisting}


Ce qui donne:

{\footnotesize
  \begin{Verbatim}
Rentrer une valeur : 5
Rentrer une valeur : 2
Rentrer une valeur : 3
Rentrer une valeur : 4
Rentrer une valeur : 6
Rentrer une valeur : 1
Rentrer une valeur : -1
    5  2  3  4  6  1
La longueur de la liste est : 6

Rentrer une valeur : 8
Rentrer une valeur : 7
Rentrer une valeur : 9
Rentrer une valeur : -1
    8  7  9
La longueur de la liste est : 3

La liste concatenee est : 
  5  2  3  4  6  1  8  7  9
La longueur de la liste concatenee est:9

Entrez un entier positif 
5
Le 5eme element de la liste concatenee est:6

La liste 1 a l'envers est : 
    1    6    4    3    2    5
La liste 2 a l'envers est : 
    9    7    8

Entrer un element  :
7
7 appartient a la liste.
Il apparait pour la premiere fois au rang 8

Entrer le rang du premier element 
de la liste extraite de L1 : 
2
Entrer le rang du dernier element 
de la liste extraite de L1 : 
5
La liste extraite est : 
    2    3    4    6

Entrer l'element a inserer :
77
Entrer le rang d'insertion :
3
5 2 77 3 4 6 1 8 7 9

La liste L filtree est :
    5    4    6    8    7    9

Entrer le rang a supprimer :
3
 5    2    4    6    1    8    7    9
  \end{Verbatim}

}

  \end{exercice}



  \begin{exercice}[Liste des diviseurs]
    \begin{lstlisting}[caption={}]
     FUNCTION ListeDiv(n:LONGWORD):Liste;
VAR L:Liste;
    k,fin:LONGWORD;
BEGIN
    L:=NIL;
    fin:=n;
    k:=1;
    WHILE k<fin DO
     BEGIN
      IF n MOD k = 0 THEN
        BEGIN
          fin:=n DIV k;
          IF k=fin THEN L:=Colle_en_tete(k,L)
          ELSE
           BEGIN
            L:=Colle_en_tete(k,L);
            L:=Colle_en_queue(n DIV k,L)
           END;
        END;
      k:=k+1
     END;
    ListeDiv:=L
END;                                   
    \end{lstlisting}
  \end{exercice}










  \begin{exercice}[Liste des nombres parfaits]
On  a  besoin  de  quelques  fonctions intermédiaires  de  plus  et  les
résultats précédents:

\begin{lstlisting}[caption={}]
FUNCTION Som_list(L:Liste):Element;
BEGIN
IF L=NIL THEN Som_list:=0
ELSE Som_list:=Tete(L)+Som_List(Queue(L))
END;

FUNCTION Parfait(n:Element):BOOLEAN;
BEGIN
 IF Som_list(ListeDiv(n))=2*n THEN Parfait:=TRUE
 ELSE Parfait:=FALSE
END;         
\end{lstlisting}


Maintenant la liste elle-même:

\begin{lstlisting}[caption={}]
FUNCTION Liste_parfait(n:Element):Liste;
BEGIN
IF n=1 THEN Liste_parfait:=NIL
ELSE IF Parfait(n) THEN
          Liste_parfait:=Colle_en_tete(n,Liste_parfait(n-1))
     ELSE Liste_parfait:=Liste_parfait(n-1)
END;        
\end{lstlisting}

Par exemple:

{\footnotesize
\begin{Verbatim}
Les nombres parfaits inferieurs
a 100000 sont : 

 8128  496   28    6
\end{Verbatim}
}
  \end{exercice}







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

   \begin{lstlisting}[caption={}]
FUNCTION inter(a,b:Element):Liste;
BEGIN
IF a>b THEN inter:=NIL
ELSE inter:=Colle_en_tete(a,inter(a+1,b))
END;


FUNCTION retmultiples(L:Liste;n:Element):Liste;
BEGIN
 IF L=NIL THEN retmultiples:=NIL
 ELSE IF Tete(L) MOD n = 0 THEN
         retmultiples:=retmultiples(Queue(L),n)
      ELSE
         retmultiples:=Colle_en_tete(Tete(L),retmultiples(Queue(L),n))
END;


FUNCTION crible(m:Element):Liste;
  FUNCTION crible_temp(L:Liste;n:Element):Liste;
    BEGIN
     IF n>m THEN crible_temp:=NIL
     ELSE IF n*n>m THEN crible_temp:=Colle_en_tete(n,crible_temp(L,n+1))
          ELSE crible_temp:=Colle_en_tete(n,retmultiples(crible_temp(L,n+1),n))
  END;
BEGIN
  crible:=crible_temp(inter(2,m),2)
END; 
   \end{lstlisting}

 \end{exercice}
 










\begin{exercice}[Décomposition en facteurs premiers récursive]
  \begin{lstlisting}[caption={}]
FUNCTION crible(m:Element):Liste;
  FUNCTION crible_temp(L:Liste;n:Element):Liste;
    BEGIN
     IF n>m THEN crible_temp:=NIL
     ELSE IF n*n>m THEN crible_temp:=Colle_en_tete(n,crible_temp(L,n+1))
          ELSE crible_temp:=Colle_en_tete(n,retmultiples(crible_temp(L,n+1),n))
  END;
  BEGIN
  crible:=crible_temp(inter(2,m),2)
END;       
  \end{lstlisting}
  \end{exercice}









  \begin{exercice}[Changement de base récursif]
    \begin{lstlisting}[caption={}]
FUNCTION base(n:Element;b:WORD):Liste;
BEGIN
 IF n<b THEN base:=Colle_en_tete(n,NIL)
 ELSE base:=Colle_en_queue(n MOD b,base(n DIV b,b))
END;   
    \end{lstlisting}
  \end{exercice}










  \begin{exercice}[X 2004]
   
    \begin{enumerate}
    \item  On montre  par  récurrence  que le  coût  en nombre  d'appels
      récursifs est $n+1$:

      \begin{lstlisting}[caption={}]
FUNCTION card(X:ensemble):INTEGER;
BEGIN
IF X=NIL THEN card:=0
ELSE card:=1+card(X^.suivant)
END; 
      \end{lstlisting}

\item C'est le même type d'appels donc le même coût:

  \begin{lstlisting}[caption={}]
FUNCTION nPetits(p:INTEGER; X:ensemble):INTEGER;
BEGIN
IF X=NIL THEN nPetits:=0
ELSE IF X^.contenu<p THEN nPetits:=1+nPetits(p,X^.suivant)
     ELSE nPetits:=nPetits(p,X^.suivant)
END;    
  \end{lstlisting}

\item Encore les mêmes complexités:
  \begin{lstlisting}[caption={}]
FUNCTION partitionP(p:INTEGER; X:ensemble):ensemble;
BEGIN
IF X=NIL THEN partitionP:=NIL
ELSE IF X^.contenu<p THEN
     partitionP:=cons(X^.contenu,partitionP(p,X^.suivant))
     ELSE partitionP:=partitionP(p,X^.suivant)
END;

FUNCTION partitionG(p:INTEGER; X:ensemble):ensemble;
BEGIN
IF X=NIL THEN partitionG:=NIL
ELSE IF X^.contenu>p THEN
     partitionG:=cons(X^.contenu,partitionG(p,X^.suivant))
     ELSE partitionG:=partitionG(p,X^.suivant)
END;                   
  \end{lstlisting}

\item On introduit des variables pour plus de lisibilité:

  \begin{lstlisting}[caption={}]
FUNCTION elementDeRang(k:INTEGER; X:ensemble):INTEGER;
VAR c:INTEGER;
    P,G:ensemble;
BEGIN
P:= partitionP(X^.contenu,X^.suivant);
G:= partitionG(X^.contenu,X^.suivant);
c:= card (P);
IF k <= c THEN
 elementDeRang:=elementDeRang(k,P)
ELSE IF k = c+1 THEN
      elementDeRang:=X^.contenu
     ELSE
      elementDeRang:=elementDeRang(k-(c+1),G)
END;      
  \end{lstlisting}

\item Dans  le cas  le plus  défavorable, il peut  y avoir  $n+1$ appels
  récursifs. À chaque appel, on
  appelle   \lstinline+partitionP+  qui   a  une   complexité  de   $c+1$  et
  \lstinline+partitionG+ qui a une complexité de $n-(c+1)$, et \lstinline+card+
  dont la complexité est de $c+1$.  Dans le pire des cas, $c$ décroît de
  $n-1$ à 0. Dans le pire des cas, la complexité peut donc être quadratique.




\item    Comme    T    est    croissante,    pour    déterminer    ${\rm
    max}\bigl\{T(i-1),T(n-i)\bigr\}$,  on va  poser  $n=2p$ ou  $n=2p+1$
  selon la parité de $n$.

Considérons par  exemple le premier  cas, l'autre se réglant  de manière
analogue.  Alors pour $1 \leqslant i
\leqslant p$, $${\rm
    max}\bigl\{T(i-1),T(n-i)\bigr\}=T(n-i)$$ et après $${\rm
    max}\bigl\{T(i-1),T(i-1)\bigr\}=T(i-1)$$

Or

\begin{eqnarray*}
\displaystyle\sum_{i=1}^{p}T(2p-i)&=&T(2p-1)+\cdots+T(2p-p)\\
&=&T(p+1-1)+\cdots+T(2p-1)
\end{eqnarray*}

donc $$\displaystyle\sum_{i=1}^{2p}{\rm
  max}\bigl\{T(i-1),T(n-i)\bigr\}=2
\displaystyle\sum_{i=p+1}^{2p}T(i-1)$$

On n'a pas d'idée  a priori pour $c$ alors essayons de  voir ce que peux
donner  l'hérédité  en gardant  un  $c$  inconnu  et en  effectuant  une
récurrence forte. 

\begin{eqnarray*}
T(n)&\leqslant & \ell n+\frac{2}{n}c \displaystyle\sum_{i=p+1}^{2p}i-1\\
&\leqslant & \ell n+\frac{2}{n}c \displaystyle\sum_{i=p}^{2p-1}i\\
&\leqslant               &               \ell n             +\frac{2}{n}c
\left(\frac{2p(2p-1)}{2}-\frac{p(p-1)}{2}\right)\\
&\leqslant & \ell n+\frac{2}{2p}c \frac{3p^2-p}{2}\\
&\leqslant & \ell n+\frac{2}{2p}c \frac{3p^2-p}{2}\\
&\leqslant & \ell n +c \frac{3p-1}{2} \\
&\leqslant & \ell n +c \frac{6p}{4} \\
&\leqslant & \ell n +c \frac{3n}{4} \\
&\leqslant & \left(\ell + \frac{3c}{4}\right) 
\end{eqnarray*}


On voudrait donc que $\ell+\frac{3c}{4}=c$ i.e. $c=4\ell$.

Sur sa copie on peut donc rédiger la récurrence forte avec $c=4\ell$.


\item On introduit des fonctions intermédiaires pour prendre des paquets
  de 5 éléments et pour créer les ensembles restant:
  \begin{lstlisting}[caption={}]
FUNCTION npremiers(X:ensemble;n:INTEGER):ensemble;
BEGIN
IF n=0 THEN npremiers:=NIL
ELSE npremiers:=cons(X^.contenu,npremiers(X^.suivant,n-1))
END;

FUNCTION nqueue(X:ensemble;n:integer):ensemble;
BEGIN
 IF n=1 THEN nqueue:=X^.suivant
 ELSE nqueue:=nqueue(X^.suivant,n-1)
END;

FUNCTION medians(X:ensemble):ensemble;
BEGIN
IF card(X)<5 THEN medians:=NIL
ELSE medians:=cons(elementDeRang(3,npremiers(X,5)),medians(nqueue(X,5)))
END;               
  \end{lstlisting}

\item On utilise \lstinline+elementDeRangBis+ pour déterminer le médian de \lstinline+Y+:

  \begin{lstlisting}[caption={}]
FUNCTION elementDeRangBis(k:INTEGER;X:ensemble):INTEGER;
VAR cy,my,cp:INTEGER;
    P,G,Y:ensemble;
BEGIN
 Y:=medians(X);
 cy:=card(Y);
 IF cy<1 THEN elementDeRangBis:=elementDeRang(k,X)
 ELSE
  BEGIN
  my:=elementDeRangBis(((cy+1) DIV 2),Y);
  P:=partitionP(my,X);
  G:=partitionG(my,X);
  cp:=card(P);
  IF k <= cp THEN
   elementDeRangBis:=elementDeRangBis(k,P)
  ELSE IF k = cp+1 THEN
        elementDeRangBis:=my
       ELSE
        elementDeRangBis:=elementDeRangBis(k-cp-1,G)
  END;
END;   
  \end{lstlisting} 

\item Le $\ell'$  introduit nous incite à rechercher  les appels dont le
  coût est au maximum $n$. Il s'agit de:
  \begin{itemize}
  \item \lstinline+Y:=medians(X);+
\item \lstinline+cy:=card(Y);+
\item \lstinline+P:=partitionP(my,X);+
\item \lstinline+G:=partitionG(my,X);+
\item \lstinline+cp:=card(P);+
  \end{itemize}

Tout ceci se retrouve dans un $\ell' n$. Il reste à s'occuper des appels
récursifs. 

Le  premier,  \lstinline|my|,  est  en
$M'(c_Y)$.  Or le  cardinal  $c_Y$ de  $Y$  est $\left\lfloor  \frac{n}{5}
\right\rfloor$ donc son coût est $M' \left(\left\lfloor  \frac{n}{5}
\right\rfloor\right)$.


Il reste  les deux  appels sur  P ou G.  On peut  supposer que  $M'$ est
croissante  comme T dans  la question  5. Il  s'agit donc  maintenant de
s'occuper de  la taille de P  et de celle  de G or celles-ci  sont liées
donc on va majorer la taille de P.

Comme $m_Y$  est le médian de Y,  il y a $  \left\lfloor \frac{ \left\lfloor
  \frac{n}{5} \right\rfloor  -1}{2}\right\rfloor$ éléments de  Y strictement
inférieurs à $m_Y$ et $\left\lfloor \frac{ \left\lfloor
  \frac{n}{5} \right\rfloor +1}{2}\right\rfloor$  éléments de  Y strictement
supérieurs à $m_Y$.

Maintenant, un élément  donné $e_Y$ de Y est le médian  de 5 éléments de
X. On s'occupe des éléments de X strictement inférieurs à $m_Y$.

Soit  $e_Y<m_Y$, alors  au  plus  cinq éléments  de  X sont  strictement
inférieurs à $m_Y$.  Si $e_Y \geqslant m_Y$, au maximum  2 éléments de X
sont strictement inférieurs à $m_Y$.

Il peut  y avoir au plus  quatre éléments de X  qui ne sont  pas pris en
compte pour la détermination des médians des groupes de 5.

Finalement:

\begin{eqnarray*}
  {\rm Card } P &\leqslant& 5 \left\lfloor \frac{ \left\lfloor
  \frac{n}{5} \right\rfloor -1}{2}\right\rfloor +2 \left\lfloor \frac{ \left\lfloor
  \frac{n}{5} \right\rfloor +1}{2}\right\rfloor+4 \\
& \leqslant& 7  \left\lfloor
\frac{n}{10}\right\rfloor + 4 
\end{eqnarray*}

Donc:

$$M'(n) \leqslant  \ell' n+  M' \left( \left\lfloor \frac{n}{5}\right\rfloor \right)
+M' \left(7  \left\lfloor
\frac{n}{10}\right\rfloor + 4 \right)$$


\medskip

Pour $c'$, on s'inspire de ce qui a été fait à la question 6.

Au brouillon, on cherche un $c'$ qui pourrait convenir:

\begin{eqnarray*}
M'(n)&\leqslant &  \ell'n+ M' \left( \left\lfloor \frac{n}{5}\right\rfloor \right)
+M' \left(7  \left\lfloor
\frac{n}{10}\right\rfloor + 4 \right)\\
M'(n)&\leqslant & \ell'n+  c'\cdot \left\lfloor \frac{n}{5}\right\rfloor 
+c' \cdot\left(7  \left\lfloor
\frac{n}{10}\right\rfloor + 4 \right)\\
M'(n)&\leqslant & \left(\ell'+\frac{9}{10}c'\right)n+4c'
\end{eqnarray*}

Il  existe $n_k$  tel que,  pour tout  $n \geqslant  n_k$,  $4 \leqslant
\frac{n}{k}$ pour un certain $k$ qu'on cherche à déterminer.

Alors  $$M'(n)  \leqslant  \left(\ell'+ \left(\frac{9}{10}+  \frac{1}{k}
  \right)c'\right)n$$

On cherche donc $k$ pour que $c'$ vérifie:

$$c'=\ell'+ \left(\frac{9}{10}+  \frac{1}{k}
  \right)c'$$


c'est-à-dire:

$$c' \left( \frac{1}{10} - \frac{1}{k} \right)=\ell'$$

Il suffit  donc que le  coefficient de $c'$  soit positif. On  prend par
exemple $k=20$, alors $$c' \geqslant 20 \ell'$$

Il faut également que $M'(n) \leqslant c'n$ pour $n \leqslant n_k$.

On montre alors sur sa copie le résultat à l'aide
d'une récurrence forte.

\item On reprend le travail effectué précédemment en adaptant, notamment
  pour le calcul de Card P:


\begin{eqnarray*}
  {\rm Card } P &\leqslant& 3 \left\lfloor \frac{ \left\lfloor
  \frac{n}{3} \right\rfloor -1}{2}\right\rfloor + \left\lfloor \frac{ \left\lfloor
  \frac{n}{3} \right\rfloor +1}{2}\right\rfloor+2 \\
& \leqslant& 4  \left\lfloor
\frac{n}{6}\right\rfloor + 2 
\end{eqnarray*}

ce qui donne finalement:

$$M'(n) \leqslant  \ell' n+  M' \left( \left\lfloor \frac{n}{3}\right\rfloor \right)
+M' \left(4  \left\lfloor
\frac{n}{6}\right\rfloor + 2 \right)$$

Si nous continuons , des problèmes surviennent:

\begin{eqnarray*}
M'(n)&\leqslant &  \ell'n+ M' \left( \left\lfloor \frac{n}{3}\right\rfloor \right)
+M' \left(4  \left\lfloor
\frac{n}{6}\right\rfloor + 2 \right)\\
M'(n)&\leqslant & \ell'n+  c'\cdot \left\lfloor \frac{n}{3}\right\rfloor 
+c' \cdot\left(2  \left\lfloor
\frac{n}{3}\right\rfloor + 2 \right)\\
M'(n)&\leqslant & \left(\ell'+c'\right)n+2c'
\end{eqnarray*}

Il  existe $n_k$  tel que,  pour tout  $n \geqslant  n_k$,  $2\leqslant
\frac{n}{k}$ pour un certain $k$ qu'on cherche à déterminer.

Alors  $$M'(n)  \leqslant  \left(\ell'+ \left(1+  \frac{1}{k}
  \right)c'\right)n$$

On cherche donc $k$ pour que $c'$ vérifie:

$$c'=\ell'+ \left(1+  \frac{1}{k}
  \right)c'$$

Aïe, ça ne marche plus! Ça ne  prouve pas pour autant que ça ne peut pas
marcher autrement...Mais comme  on demande de prouver que  le coût n'est
plus au pire linéaire, il  faudrait minorer $M'(n)$ par quelque chose de
plus coûteux.

Comme   nous   avons  une   majoration   de   $M'(n)$,   ce  n'est   pas
pratique. Cependant, en réorganisant X,  on peut s'arranger pour qu'il y
ait égalité  pour chaque $n$ en  remplaçant les \og  au maximum\fg{} par
des égalités dans notre raisonnement.


Alors,  pour se débarrasser  des parties  entières, on  peut considérer,
pour tout naturel $k$, des entiers $n \geqslant 3^k$.

Alors 


\begin{eqnarray*}
M'(n) &   \geqslant  &  \ell'    n+M'\left(    \frac{3^k}{3}\right)    +M'
\left(4\frac{\times 3^k}{6}+2\right)\\
 &  \geqslant  &  \ell'  n  +M'  \left(3^{k-1}\right)  +M'  \left(2\cdot
     3^{k-1}\right) 
\end{eqnarray*}

On peut alors montrer par récurrence  que si $n \geqslant 3^k$, on
a $M'(n) \geqslant k \ell' n$.

En effet, pour l'hérédité, on peut appliquer l'hypothèse de récurrence à
la dernière inégalité obtenue:


\begin{eqnarray*}
 M'(n)&  \geqslant  &  \ell'  n  +M'  \left(3^{k-1}\right)  +M'  \left(
     3^{k-1}\right) \\
  M'(n) & \geqslant & \ell' n+(k-1)\ell' n+(k-1)\ell' n\\
M'(n) & \geqslant & \ell' n \left(2k-1\right)\\
M'(n) & \geqslant & \ell' n k
\end{eqnarray*}


On ne  peut donc  pas trouver un  majorant de  la forme $c'n$  avec $c'$
indépendant de $n$.
    \end{enumerate}
  \end{exercice}



\end{listeexercices}

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



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