\documentclass[10pt]{article}

\usepackage{amsmath,amssymb,fancybox,fancyhdr,lastpage,a4,mdwlist}

\topmargin-0.5cm
\headheight20pt
\textheight23cm
\textwidth17.5cm
\oddsidemargin-1cm
\evensidemargin0cm
\parindent0pt

\def\[{[\![}
\def\]{]\!]}

\begin{document}

\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}
\renewcommand{\labelenumiii}{\roman{enumiii})}

\pagestyle{fancy}
\lhead{{\bf MPSI option informatique}}
\chead{}
\rhead{TP 2~: listes}
\lfoot{\sl Lyc\'ee Chateaubriand}
\cfoot{}
\rfoot{\thepage/\pageref{LastPage}}

\renewcommand{\footrulewidth}{0.4pt}

\section*{\'Elementaire}

Pour pouvoir tester les futures fonctions sur les listes, on va cr\'eer une liste pseudo--al\'eatoire.

Posons $m = 2^{15} - 1 = 32\,767$ et $f:k\mapsto(123\times k + 15) \mod m$. On d\'efinit une suite
(pseudo--al\'eatoire) $(u_n)$ par la donn\'ee de $u_0\in\mathbb N$ et de la r\'ecurrence $\forall n\in\mathbb
N,u_{n+1}=f(u_n)$.

Soit alors la liste $\ell(n,u_0)=[u_0;u_1;\dots;u_{n-1}]$ (de longueur $n$).

\begin{enumerate}

\item Programmer la fonction {\tt f : int -> int}.

\item En remarquant que $\ell(n,u_0)=\begin{cases}[\,]&\mbox{si }n=0\\u_0::(\ell(n-1,u_1))&\mbox{si
}n\geqslant1\end{cases}$~:

  programmer une fonction {\tt alea : int -> int -> int list} telle que l'appel {\tt
  alea n u0} renvoie $\tt\ell(n,u0)$.

  Test~: $\ell(10,1594)=[1594; 32242; 974; 21516; 25123; 10046; 23294; 14448; 7701; 29762]$

  Dans la suite on notera $\ell$ cette liste.

  (par exemple vous pouvez la d\'efinir comme variable globale avec {\tt let l = alea 10 1594;;})

\suspend{enumerate}

Pour chacune des questions \`a suivre~: pr\'evoir le type de sortie, \'ecrire la fonction puis v\'erifier le type obtenu.

\resume{enumerate}

\item \'Ecrire une fonction \texttt{map1} telle que l'appel \texttt{map1 f [x0;x1;...;xn]}\goodbreak
  retourne la liste \texttt{[f x0;f x1;...;f xn]}. Tester sur $\ell$ avec \texttt{f = fun x -> x mod 3}.

\item {\it Mise en garde~: n'utilisez pas la touche \texttt{@} de votre clavier~: elle est
  pi\'eg\'ee~!}

  \medskip

  \'Ecrire une fonction \texttt{conc} qui concat\`ene deux listes. Testez votre fonction.

\item \'Ecrire une fonction \texttt{rev1} qui inverse une liste pass\'ee en argument. Tester sur $\ell$.

\item \'Ecrire une fonction \texttt{filtre} telle que \texttt{filtre p l} retourne la liste des \'el\'ements de
  \texttt{l} qui satisfont le pr\'edicat \texttt{p : x -> bool} o\`u \texttt{x} est le type des \'el\'ements de
  \texttt{l}.

  Tester avec \texttt{p} d\'efinit par \texttt{let p x = x mod 2 = 1}~: vous devez obtenir la liste des \'el\'ements
  impairs de $\ell$ (il y a 2 \'el\'ements impairs dans $\ell$).

\suspend{enumerate}

C'est bon, vous pouvez \`a nouveau utiliser la touche \texttt{@}.

\section*{\texttt{'a} de Fibonacci}

On se donne un type g\'en\'erique {\tt'a} ainsi que deux valeurs {\tt f0} et {\tt f1} de type {\tt'a}.

Soit une fonction {\tt$\gamma$ : 'a -> 'a -> 'a}.

On d\'efinit alors une suite $(f_n)$ de valeurs de type {\tt'a} par la r\'ecurrence~:
$$\forall n\in\mathbb N,f_n=
\begin{cases}
  {\tt f0}&\mbox{si }n=0\\
  {\tt f1}&\mbox{si }n=1\\
  \gamma(f_{n-1},f_{n-2})&\mbox{si }n\geqslant2
\end{cases}$$

\medskip

\underline{Exemple}~: si {\tt'a} est le type {\tt int}, si $\tt f0=0$, si $\tt f1=1$ et si $\forall a,b\in\mathbb
N,\gamma(a,b)=a+b$ (et donc $\forall n\geqslant2,f_n=f_{n-1}+f_{n-2}$) on retrouve la suite de Fibonacci {\it
  usuelle}.

\resume{enumerate}

\item \'Ecrire la fonction {\tt fibogen : ('a -> 'a -> 'a) -> 'a -> 'a -> int -> 'a} telle que l'appel de {\tt
  fibogen $\gamma$ f0 f1 n} renvoie $f_n$.

\item Suite de Fibonacci usuelle

  \begin{enumerate}

  \item Syntaxe pr\'efix\'ee de l'addition

    Taper et \'evaluer \texttt{(+);;}. Interpr\'eter le r\'esultat. \\
    Tester \texttt{(+) 7 8}.

  \item En d\'eduire une fonction {\tt fibo\_usuel : int -> int} qui calcule le $n$--i\`eme terme de la suite de
    Fibonacci usuelle. Votre fonction {\tt fibo\_usuel} ne doit contenir aucun appel r\'ecursif, elle doit se
    contenter de faire un seul appel \`a la fonction {\tt fibogen} (qui elle est r\'ecursive).

    Test~: le terme d'indice 12 de la suite de Fibonacci usuelle est 144.

  \end{enumerate}

\item On d\'efinit une suite de cha\^ines $(w_n)$ par~:
\begin{tabular}{|c|l|}\hline
   $w_0$ & \tt"b"\\\hline
   $w_1$ & \tt"a"\\\hline
   $w_2$ & \tt"ab"\\\hline
   $w_3$ & \tt"aba"\\\hline
   $w_4$ & \tt"abaab"\\\hline
  $w_5$ & \tt"abaababa"\\\hline
  \dots&\dots\\\hline
\end{tabular}

En utilisant judicieusement {\tt fibogen}, \'ecrire une fonction {\tt fiboword} qui calcule $w_n$~:\goodbreak
{\tt fiboword : int -> string}

\item La fonction {\tt fibolist}

  On d\'efinit une suite de listes d'entiers $(l_n)$ par~:
  \begin{tabular}{|c|l|}\hline
   $l_0$ & \tt[1]\\\hline
   $l_1$ & \tt[0]\\\hline
   $l_2$ & \tt[0;1]\\\hline
   $l_3$ & \tt[0;1;0]\\\hline
   $l_4$ & \tt[0;1;0;0;1]\\\hline
   $l_5$ & \tt[0;1;0;0;1;0;1;0]\\\hline
  \dots&\dots\\\hline
\end{tabular}

En utilisant judicieusement {\tt fibogen}, \'ecrire une fonction {\tt fibolist} qui calcule $l_n$~:\goodbreak
{\tt fibolist : int -> int list}

\item \'Ecrire une fonction \texttt{nb\_occ} qui d\'etermine le nombre d'occurrences d'un \'el\'ement d'une liste du
  deuxi\`eme exemple.

  V\'erifier pour quelques valeurs de $\tt n$ que \texttt{nb\_occ 0 (fibolist n) = fibo\_usuel n}.

  S'il vous reste du temps~: d\'emontrer cette propri\'et\'e.

\item

  \begin{enumerate}

  \item \'Ecrire une fonction \texttt{tronque} telle que \texttt{tronque n $\ell$} retourne $\ell$ priv\'ee de ses
    {\tt n} derniers \'el\'ements.

  \item V\'erifier que pour tout $i\in\[3,8\]$, $l_i$ priv\'ee de ses deux derniers \'el\'ements est un palindrome
    (on pourra utiliser une fonction qui calcule le miroir d'une liste).

    S'il vous reste du temps~: d\'emontrer cette propri\'et\'e.

  \end{enumerate}

\item

  \begin{enumerate}

  \item \'Ecrire une fonction {\tt remplace : 'a -> 'a list -> 'a list -> 'a list} telle que l'appel de {\tt
    remplace x lx l} renvoie une liste dans laquelle on a remplac\'e les occurrences de {\tt x} dans {\tt l} par les
    \'el\'ements de {\tt lx}.

    Par exemple, l'appel {\tt remplace 0 [2;4] [0; 1; 0; 0; 1]} renvoie {\tt [2; 4; 1; 2; 4; 2; 4; 1]}.

  \item V\'erifier pour quelques valeurs de $n$ que si on remplace dans $l_n$ tous les $\tt0$ par {\tt[0;1]} et
    $\tt1$ par $\tt[0]$ alors on trouve $l_{n+1}$.

    S'il vous reste du temps~: d\'emontrer cette propri\'et\'e.

  \end{enumerate}

  \suspend{enumerate}

  \section*{Le codage b\^aton}

  Dans cet exercice, on codera les entiers par des listes de \texttt{() : unit}, leur nombre indiquant la valeur de
  l'entier. Ainsi \texttt{[();();();();();();();()]} code l'entier 8. En termes plus imag\'es, on repr\'esente un
  entier par une liste de petits b\^atons (ou de {\tt()}) comme en maternelle quand on apprend \`a compter.

Pour effectuer des tests, on d\'efinira~:
\begin{verbatim}
let huit = [(); (); (); (); (); (); (); ()];;
let trois = [(); (); ()];;
\end{verbatim}

  \resume{enumerate}

\item \'Ecrire une fonction \texttt{successeur : unit list -> unit list}.

\item En d\'eduire une fonction \texttt{entiers\_vers\_batons : int -> unit list}.

  \'Ecrire aussi une fonction {\tt batons\_vers\_entiers : unit list -> int}.

  Tests~:
\begin{verbatim}
# entiers_vers_batons 4;;
- : unit list = [(); (); (); ()]
# batons_vers_entiers trois;;
- : int = 3
\end{verbatim}

\item Dans toutes les questions suivantes on demande de coder les op\'erations suivantes {\it sans repasser par des
  valeurs de type} {\tt int}~: les ``entiers'' seront uniquement cod\'es par le type \texttt{unit list}.

  \begin{enumerate}

  \item On cherche \`a \'ecrire une fonction {\tt inferieur : unit list -> unit list -> bool} qui renvoie {\tt true} si
    et seulement si on a un inf\'erieur strict. Pour cela le savant Sunisoc propose de filtrer sur le {\it couple}
    {\tt (l1,l2)} form\'e par les deux param\`etres. Il vous laisse ce code \`a trous, \`a vous de compl\'eter ce
    qu'il y a derri\`ere les fl\`eches~:
\begin{verbatim}
let rec inferieur l1 l2 = match l1, l2 with
  | _, [] ->
  | [], _ ->
  | ()::q1, ()::q2 ->
;;
\end{verbatim}
Tests~:
\begin{verbatim}
# inferieur huit trois;;
- : bool = false
# inferieur trois huit;;
- : bool = true
# inferieur huit huit;;
- : bool = false
\end{verbatim}

  \item \'Ecrire une fonction \texttt{somme :  unit list -> unit list -> unit list}.

    Tests~:
\begin{verbatim}
# somme huit trois;;
- : unit list = [(); (); (); (); (); (); (); (); (); (); ()]
\end{verbatim}

  \item \'Ecrire une fonction {\tt difference : unit list -> unit list -> unit list}. Au cas o\`u la diff\'erence
    correspondrait \`a un entier n\'egatif, votre fonction renverra la liste vide.

    Tests~:
\begin{verbatim}
# difference huit trois;;
- : unit list = [(); (); (); (); ()]
# difference trois huit;;
- : unit list = []
\end{verbatim}

\item \'Ecrire une fonction \texttt{produit :  unit list -> unit list -> unit list}.

  Tests (attention~: la conversion en entiers ne se fait qu'apr\`es avoir calcul\'e le produit, pour rendre le
  r\'esultat plus lisible)~:
\begin{verbatim}
# batons_vers_entiers (produit huit trois);;
- : int = 24
\end{verbatim}

\item \'Ecrire une fonction {\tt division : unit list -> unit list -> (unit list) * (unit list)} qui renvoie sous
  forme d'un couple le quotient et le reste de la division euclidienne.

  Tests~:
\begin{verbatim}
# division huit trois;;
- : unit list * unit list = ([(); ()], [(); ()])
# division trois huit;;
- : unit list * unit list = ([], [(); (); ()])
# division trois trois;;
- : unit list * unit list = ([()], [])
\end{verbatim}

\item \'Ecrire une fonction {\tt baseb : unit list -> unit list -> unit list list} telle que l'appel de {\tt baseb l
  b} renvoie la liste des chiffres (poids faible en t\^ete) de {\tt l} et base {\tt b}.

  Test (en utilisant $25=2\times3^2+2\times3+1=\overline{221}^3$)~:
\begin{verbatim}
# baseb (entiers_vers_batons 25) trois;;
- : unit list list = [[()]; [(); ()]; [(); ()]]
\end{verbatim}

  \end{enumerate}

  \suspend{enumerate}

\section*{Avanc\'e}

\resume{enumerate}

\item On veut \'ecrire une fonction \texttt{fold\_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a} telle que pour\break
  \texttt{f : 'a -> 'b -> 'a}, on ait \texttt{fold\_left f a [x1;x2;...;xn]} retourne \texttt{f (...(f (f a x1)
    x2)...) xn}.

  \begin{enumerate}

  \item Quel est son cas de base~?

  \item \'Ecrire la fonction \texttt{fold\_left}.

  \end{enumerate}

\item En d\'eduire des fonctions (tr\`es simples, avec seulement un appel de {\tt fold\_left}) calculant~:

  \begin{enumerate}

  \item la somme des termes d'une liste d'entiers

  \item le produit des termes d'une liste d'entiers

  \item le maximum des termes d'une liste d'entiers

  \end{enumerate}

\item \'Ecrire une fonction \texttt{flatten} de type \texttt{'a list list -> 'a list} telle que \texttt{flatten l}
  retourne la concat\'ena\-tion des \'el\'ements de \texttt{l}.

  Par exemple, \texttt{flatten [[1;2];[3];[];[4;5]] = [1;2;3;4;5]}.

\item \'Ecrire \`a l'aide de \texttt{fold\_left} une fonction {\tt reverse : 'a list -> 'a list} qui renverse une
  liste.

\item \'Ecrire une fonction \texttt{fold\_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a} telle
  que \texttt{fold\_left2 g a [x1;x2;...;xn] [y1;y2;...;yn]} retourne \texttt{g (g ... (g (g a x1 y1) x2 y2) ...) xn
    yn} o\`u les \texttt{xi} sont de type \texttt{'b}, les \texttt{yi} sont de type \texttt{'c} et \texttt{g : 'a
    -> 'b -> 'c -> 'a}.

  En d\'eduire une fonction qui v\'erifie qu'une liste est un palindrome. On pourra utiliser \texttt{reverse}.

  \suspend{enumerate}

  \section*{P\'al Erd\H{o}s}

P\'al Erd\H{o}s mort en 1996 \`a l'\^age de 83 ans est tr\`es connu pour ses probl\`emes sur la th\'eorie des nombres
dont voici l'un d'eux~:

\begin{quote}
Quelle est la taille maximale d'un sous-ensemble de nombres entiers $a_1,\cdots a_k$ choisis parmi les entiers
$1,2,\cdots,n$ tels que $a_i + a_j$ ne soit jamais un carr\'e parfait ($i$ et $j$ quelconques y compris $i=j$)~?

Par exemple si $n=7$ alors $\{1,4,6,7\}$ est l'un des sous-ensembles recherch\'es.
\end{quote}

\resume{enumerate}

\item Donner la r\'eponse pour $n = 20$. Combien il y a-t-il de solutions~?

  \end{enumerate}

  \end{document}