\documentclass[10pt,a4paper]{article}
\usepackage{ifxetex}
\usepackage[T1]{fontenc}
\usepackage[mathletters]{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[french]{babel}
\usepackage{geometry}
\usepackage[enonce]{examClem}
%\usepackage[correction]{exam}

\usepackage{epsf,amsmath,amssymb,graphicx,realboxes}
\newcommand\scr{}
\usepackage[boldsans]{ccfonts}
\usepackage[mathcal,mathbf]{euler}
\usepackage{siunitx,textcomp}

\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
%\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\input{patch-tkz-graph}
\usepackage{tikz-qtree}

\newcommand{\ve}[1]{\overrightarrow{#1}}


\renewcommand{\algocommentfont}{\small\ttfamily\itshape}



\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}} 



\newcommand{\illt}[4]{\begin{minipage}[t]{#3\linewidth}\vspace{0cm}#1\end{minipage}\hspace{0.5cm}\begin{minipage}[t]{#4\linewidth}\vspace{-0.25cm}
\hspace{5.5cm} \begin{flushright}\includegraphics[width=\linewidth]{#2}\end{flushright}\end{minipage}}

\newcommand{\ch}{\operatorname{ch}}
\newcommand{\sh}{\operatorname{sh}}
%\newcommand{\cos}{\operatorname{cos}}
%\newcommand{\ln}{\operatorname{ln}}
%\newcommand{\exp}{\operatorname{exp}}
\newcommand{\E}{{\operatorname e}}

\usepackage{listing}

\lstset{
 language=sage,
        escapeinside={(*@}{@*)},
        %numbers=left,
        basicstyle={\small\ttfamily},
        commentstyle={\small\itshape\color{pink!60!black}},
        keywordstyle={\ttfamily\bfseries\fontfamily{ul9}\selectfont\color{black!60!blue}},
        stringstyle={\small\ttfamily\color{gray!50!black}\itshape},
        breaklines=true,
        breakatwhitespace=true,
        showtabs=False,
        showspaces=False,
        showstringspaces=False,
        extendedchars=true,
        %aboveskip=1em,
        %belowskip=1em,
        rulecolor=\color{gray},
        %rulesepcolor=\color{gray},
        %frame=trBL,
        frame=single,
        frameround=tttt,
        framerule=0.3pt,
        framesep=4pt,
        belowcaptionskip=2.1pt,
title={{\setlength{\fboxsep}{1pt}\fcolorbox{gray}{gray!10}{\sffamily\scriptsize
      \textcolor{gray!10}{\_}Python \textcolor{gray!10}{\_}}}}}


%transposee
\usepackage{fouridx}
\newcommand*{\transp}[1]{\fourIdx{{\rm t}}{}{}{}{#1}}
\newcommand\tr{\vphantom{}^{\rm t}}

\newcommand{\dd}{\text{ d}}


\paper{DS-IPT1} % <- do not include FC, FT etc
%\version{0}                     % <- for multiple choice exams
\title{Devoir Surveillé}
\time{cent vingt minutes} % <- number of hours: default is three
\semester{Premier semestre}
\annee{2014-2015} % <- default is the current year

%\campus{City}
\note{\small \bfseries Vous justifierez vos réponses
    avec le  plus grand  soin. N'oubliez pas  qu'il serait  maladroit de
    copier sur  votre voisin(e) qui  a, de toute façon,  écrit n'importe
    quoi. Aucune calculatrice ni tout autre engin  relié
    à un quelconque réseau n'est autorisé.\\
    Vous choisirez  UN des  deux sujets proposés  en indiquant  clairement votre
    choix en début de copie.\\
    Votre note dépendra en grande partie de la clarté de votre rédaction.
    Vos  codes doivent  être correctement  indentés, commentés,  présentés. Vous
    choisirez des noms de variables évocateurs. Vous utiliserez le langage Python.}
    %N'oubliez pas que c'est compilator qui corrigera votre script...}
\begin{document} 

\pythonc

\begin{exercice}[X / ENS Cachan / ESPCI - 2013]
\subsection*{Points fixes de fonctions à domaine fini}
Dans ce problème, on s'intéresse aux points  fixes des fonctions $f : E\to E$ où
E est un ensemble fini. 

On désigne  par $E_n$ l'ensemble $\bigl\{0,1,...,n-1\bigr\}$.  On représente une
fonction  $f :  E_n\to E_n$  par un  tableau \Colorbox{blue!10}{\lstinline{t}}  de taille  $n$ tel  que
$f(x)=$ \Colorbox{blue!10}{\lstinline{t[x]}} pour tout $x$ de $E_n$.


Par exemple, $f_0$ qui à $x\in E_{10}$ associe $2x+1[10]$ est
représentée par:
  \begin{tabular}[h]{|*{10}{c|}}
    \hline
    1&3&5&7&9&1&3&5&7&9\\
    \hline
  \end{tabular}.



On note $f^k$ l'itérée $k$-ième de $f$.


\subsection*{Partie I. Recherche de point fixe: cas général}

\begin{enumerate}
\item  Écrire  une fonction  \Colorbox{blue!10}{\lstinline{admet_point_fixe(t)}}
  qui prend en argument  un tableau \Colorbox{blue!10}{\lstinline{t}} et renvoie
  \Colorbox{blue!10}{\lstinline{True}}   si   la    fonction   représentée   par
  \Colorbox{blue!10}{\lstinline{t}}     admet      un     point      fixe     et
  \Colorbox{blue!10}{\lstinline{False}} sinon.

  Par  exemple, avec  le tableau  de  la fonction  $f_0$ donnée  en exemple,  la
  fonction renverra \Colorbox{blue!10}{\lstinline{True}}.


\item Écrire une fonction \Colorbox{blue!10}{\lstinline{nb_points_fixes(t)}} qui
  prend en  argument un tableau \Colorbox{blue!10}{\lstinline{t}}  et renvoie le
  nombre      de     points      fixes      de      $f$     représentée      par
  \Colorbox{blue!10}{\lstinline{t}}.


\item  Écrire  une  fonction  \Colorbox{blue!10}{\lstinline{itere(t,x,k)}}  qui
  prend  en premier  argument un  tableau \Colorbox{blue!10}{\lstinline{t}},  en
  second un  entier de $E_n$  et en troisième un  entier naturel $k$  et renvoie
  $f^k(x)$.

\item                   Écrire                   une                   fonction
  \Colorbox{blue!10}{\lstinline{nb_points_fixes_iteres(t,k)}}   qui   prend   en
  argument  un tableau  \Colorbox{blue!10}{\lstinline{t}}, en  second un  entier
  naturel $k$ et renvoie le nombre de points fixes de $k$.

\medskip

Un élément  $z$ de  $E_n$ est  dit \textit{attracteur principal}  de $f$  si, et
seulement si, $z$ est un point fixe de  $f$ et pour tout $x$ de $E_n$, il existe
un entier $k \geqslant 0$ tel que $f^k(x)=z$.

Afin  d'illustrer  cette  notion,  on  pourra vérifier  que  la  fonction  $f_1$
représentée par le tableau suivant admet 2 comme attracteur principal:
  \begin{tabular}[h]{|*{7}{c|}}
    \hline
    5&5&2&2&0&2&2\\
    \hline
  \end{tabular}


En revanche, on notera que la  fonction $f_0$ donnée en introduction n'admet pas
d'attracteur principal.


\medskip


\item Écrire une fonction \Colorbox{blue!10}{\lstinline{liste_points_fixes(t)}} qui
  renvoie la liste des points fixes de $f$ représentée par \Colorbox{blue!10}{\lstinline{t}}.

Écrire                   ensuite                  une                   fonction
\Colorbox{blue!10}{\lstinline{admet_attracteur_principal(t)}}   qui   prend   en
argument    un    tableau     \Colorbox{blue!10}{\lstinline{t}}    et    renvoie
\Colorbox{blue!10}{\lstinline{True}} si, et seulement  si, la fonction $f$ admet
un attracteur principal et \Colorbox{blue!10}{\lstinline{False}} sinon.


\medskip

Le \textit{temps de convergence}  de $f$ en $x\in E_n$ est  le plus petit entier
$k \geqslant 0$ tel que $f^k(x)$ soit un point fixe de $f$.

Pour  la fonction  $f_1$,  le temps  de convergence  en 4  est 3  car
$f_1(4)=0$, $f_1^2(4)=5$, $f_1^3(4)=2$ et 2 est un point fixe.


\medskip

\item                   Écrire                   une                   fonction
  \Colorbox{blue!10}{\lstinline{temps_de_convergence(t,x)}} qui prend en premier
  argument un tableau \Colorbox{blue!10}{\lstinline{t}} représentant une fonction
  $f$ et en second un entier $x$ de $E_n$ et qui renvoie le temps de convergence
  de $f$ en $x$.

\item                   Écrire                   une                   fonction
  \Colorbox{blue!10}{\lstinline{temps_de_convergence_max(t)}}   qui   prend   en
  argument   un   tableau   \Colorbox{blue!10}{\lstinline{t}}  de   taille   $n$
  représentant une fonction  $f$ et renvoie le maximum des  temps de convergence
  de ses éléments.  \textbf{On impose un temps de calcul  LINÉAIRE} en la taille
  $n$ du tableau. 

  \textit{Joker}:  on pourra  utiliser  le principe  de \textit{mémoïsation}  en
  introduisant un dictionnaire  dont les clés sont les éléments  de $E_n$ et les
  valeurs leur temps de convergence. 

  \textit{Rappel}: en Python,  la syntaxe de construction  des dictionnaires est
  \Colorbox{blue!10}{\lstinline|{clé:valeur}|}                                et
  \Colorbox{blue!10}{\lstinline{dic[clé]}} renvoie  la valeur associée à  la clé
  \Colorbox{blue!10}{\lstinline{clé}}.

\item Justifier que la complexité de cette fonction est en $O(n)$.



\subsection*{Partie II. Recherche efficace de points fixes.}

Toute  fonction    \Colorbox{blue!10}{\lstinline{point_fixe(t)}}  retournant  un
point fixe d'une fonction arbitraire est de complexité au mieux linéaire.
On  s'intéresse maintenant  à des  améliorations possibles  de cette  complexité
lorsque la fonction considérée possède certaines propriétés spécifiques.


\subsubsection*{Premier cas}

On considère le cas d'une \textbf{fonction croissante} de $E_n$ dans $E_n$.


\item Écrire un  prédicat \Colorbox{blue!10}{\lstinline{est_croissante(t)}} avec
  \Colorbox{blue!10}{\lstinline{t}} un tableau associé à une fonction $f:E_n\to E_n$.

On impose un temps de calcul  de complexité \lstinline{linéaire} en la taille du
tableau. 
On justifiera cette complexité.


\item  Écrire  une fonction  \Colorbox{blue!10}{\lstinline{point_fixe(t)}}  
  avec \Colorbox{blue!10}{\lstinline{t}} représentant
  une fonction croissante $f:E_n\to E_n$. Cette fonction retourne un entier $x$ de $E_n$ tel
  que $f(x)=x$. 

  On impose un temps de calcul de complexité \textbf{logarithmique}.

\item  Démontrer que  la fonction  termine et  justifier que  sa complexité  est
  logarithmique.


\subsubsection*{Deuxième cas}

Soit $\preceq$  une relation d'ordre  (pas forcément totale...) sur  un ensemble
E. Une fonction $f:E\to E$ est \textit{croissante  au sens de } $\preceq$ si, et
seulement si, pour tous $x$ et $y$ de E:
$x \preceq y \Longrightarrow f(x)\preceq f(y)$.

On dit qu'un élément $m$ de E est un \textit{plus petit élément} de E au sens de
$\preceq$ si, et seulement si, pour tout $x$ de E, $m\preceq x$.


\textbf{On admet}  que pour  tout ensemble  fini E  muni d'une  relation d'ordre
$\preceq$ et qui admet un plus petit  élément au sens de $\preceq$, il existe un
entier naturel $k$ tel que $f^k(m)$ est un point fixe de $f$ dans E.


\item Soit E  un ensemble fini quelconque muni d'une  relation d'ordre $\preceq$
  et admettant un plus  petit élément $m$ au sens de  $\preceq$. Soit $f:E\to E$
  une fonction croissante au sens de $\preceq$ et soit $k$ un entier naturel tel
  que $f^k(m)$ soit un point fixe de $f$ dans E. 

Démontrer qur $f^k(m)$  est en fait le plus  petit point fixe de $f$  au sens de
$\preceq$.


\medskip

Nous nous intéressons maintenant à un choix particulier d'ordre $\preceq$ appelé
\textit{ordre de  divisibilité} et noté $|$.  On note $a|b$ la  relation d'ordre
\og $a$ divise $b$\fg{} sur les entiers positifs.


Par exemple, la fonction représentée par le tableau ci-dessous est croissante au
sens de l'ordre de divisibilité:




\begin{center}
  \begin{tabular}[h]{|*{10}{c|}}
    \hline
    0&2&4&6&4&8&0&2&0&6\\
    \hline
  \end{tabular}
\end{center}


On  remarque que,  par  la question  précédente, toute  fonction  de $E_n$  dans
lui-même, croissante  au sens de  la divisibilité, a un  plus petit point  fixe au
sens de la divisibilité.

On étend la  définition du PGCD à des entiers  naturels quelconques en convenant
de définir le PGCD d'un entier $x \geqslant 0$ et de 0 comme valant $x$.

\item  Soit $f$  une fonction  de  $E_n$ dans  $E_n$  croissante au  sens de  la
  divisiblité   et  notons   $x_1,...,x_m$  les   points  fixes   de  $f$   dans
  $E_n$. Montrer que le plus petit point  fixe de $f$ au sens de la divisibilité
  est exactement le PGCD de $x_1,...,x_m$.


\item Écrire  une fonction \Colorbox{blue!10}{\lstinline{pgcd_points_fixes(t)}}
  qui prend en  argument un tableau représentant une fonction  croissante au sens
  de la divisibilité et renvoie le PGCD de ses points fixes.
  On  impose un  temps  de calcul  \textbf{logarithmique} en  $n$.


\item Justifiez que la fonction précédente est de complexité $O(\log(n))$.




\end{enumerate}





\end{exercice}



\vfill

\eject


\begin{exercice}


 \subsection*{Banque PT}

  \begin{enumerate}
  \item    Soit   un    entier   naturel    non   nul    $n$   et    une   liste
    \Colorbox{blue!10}{\lstinline{t}} de  longueur $n$ dont les  termes valent 0
    ou 1.
 Le but de  cette question est de  trouver le nombre maximal de  0 contigus dans
 \Colorbox{blue!10}{\lstinline{t}} . Par exemple, le nombre de zéros contigus de
 la liste \Colorbox{blue!10}{\lstinline{t1}} suivante vaut 4:


\begin{center}
  \begin{tabular}[h]{|*{16}{c|}}
    \hline
    \Colorbox{blue!10}{\lstinline{i}}&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\
    \hline
    \Colorbox{blue!10}{\lstinline{t1[i]}}&0&1&1&1&0&0&0&1&0&1&1&0&0&0&0\\
    \hline
  \end{tabular}
\end{center}

\begin{enumerate}
\item   Écrire  une   fonction  \Colorbox{blue!10}{\lstinline{nombreZeros(t,i)}}
  prenant en paramètres une  liste \Colorbox{blue!10}{\lstinline{t}} de longueur
  $n$ et un indice $i$ compris entre 0 et $n-1$ et renvoyant:

$$
\begin{cases}
  0, \ \text{si } \mathtt{t[i]} = 1\\
  \text{le nombre de zéros  consécutifs dans \texttt{t} à
    partir de \texttt{t[i]} inclus, si } \mathtt{t[i] = 0}
\end{cases}
$$

\item  Comment  obtenir  le  nombre   maximal  de  zéros  contigus  d'une  liste
  \Colorbox{blue!10}{\lstinline{t}}      connaissant      la      liste      des
  \Colorbox{blue!10}{\lstinline{nombreZeros(t,i)}} pour $0 \leqslant i \leqslant
  n-1$?

  En  déduire   une  fonction  \Colorbox{blue!10}{\lstinline{nombreZerosMax(t)}}
  renvoyant    le    nombre    maximal     de    0    contigus    d'une    liste
  \Colorbox{blue!10}{\lstinline{t}}   non  vide.   On   utilisera  la   fonction
  \Colorbox{blue!10}{\lstinline{nombreZeros}}.

\item      Quelle      est      la      complexité      de      la      fonction
  \Colorbox{blue!10}{\lstinline{nombreZerosMax}}   construite   à  la   question
  précédente?

\item     Trouver     un     moyen     simple,     toujours     en     employant
  \Colorbox{blue!10}{\lstinline{nombreZeros}},  d'obtenir   un  algorithme  plus
  performant.

  


\end{enumerate}



\item Soit N un entier naturel non nul. On cherche à trier une liste L d'entiers
  naturels strictement inférieurs à N.

  \begin{enumerate}
  \item Écrire  une fonction \Colorbox{blue!10}{\lstinline{comptage}}d'arguments
    L et  N, renvoyant une  liste P dont le  $k$-ième élément désigne  le nombre
    d'occurences de l'entier $k$ dans la liste L.
  \item    Utiliser   la    liste    P   pour    en    déduire   une    fonction
    \Colorbox{blue!10}{\lstinline{tri}}, d'arguments L et  N, renvoyant la liste
    L triée dans l'ordre croissant.
  \item Donner  la trace de la  fonction \Colorbox{blue!10}{\lstinline{tri}} sur
    une liste de 10 entiers inférieurs ou égaux à 5.

    Comment effecteur ce test sur machine.
  \item Quelle est la complexité temporelle  de cet algorithme? La comparer à la
    complexité d'un tri par insertion ou d'un tri fusion.
  \end{enumerate}




\subsection*{Mines/Ponts}


\subsubsection*{Présentation des milieux granulaires}

Le sable c’est cool,  y’en a dans les dunes et on peut  faire des sabliers avec.
Le sable,  ça fait des tas  et on peut  essayer de simuler l’évolution  d’un tas
numériquement.   (Ceci condense  l'introduction donnée  dans le  vrai sujet  sur
toute une page...)


\subsubsection*{Calcul de la forme d’un tas par automates cellulaires}

L’objet  de cette  partie est  la  simulation numérique  par un  modèle de  type
automate cellulaire. Un  automate cellulaire se présente  généralement sous la
forme d’un quadrillage  dont chaque case peut  être occupée ou vide.  Un grain y
est symbolisé  par une case occupée.  La configuration des cases,  qu’on appelle
état de l’automate, évolue au cours du temps selon certaines règles très simples
permettant de  reproduire des  comportements extrêmement complexes.  La physique
n’intervient pas directement mais les  règles d’évolution sont choisies de façon
à reproduire au  mieux les  lois naturelles.  Dans ce  qui suit,  nous allons
simuler la formation d’un demi-tas de sable  situé à droite de l’axe de symétrie
vertical en appliquant les règles énoncées ci-après.



%\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{Capture}
%\caption{Exemple d'évolution de l'automate cellulaire à implémenter}
\end{center}
%\end{figure}

La représentation graphique est une image en deux dimensions mais l’automate est
à une  dimension car  on considère  le tas comme  un ensemble  de piles  dont la
hauteur  future  dépend  uniquement  des  piles  adjacentes  :  une  cellule  de
l’automate cellulaire,  c’est une pile. Le  tas est complètement défini  avec un
tableau (ou  une liste)  unidimensionnel qui  permet de  stocker la  hauteur des
différentes  piles.   Une  tour de  hauteur  $h$  est  une  pile de  cases  pleines
consécutives  dont $h$  voisines de  droite sont  vides. Si  $h >  1$, on  détermine
arbitrairement le nombre $n$  de grains du sommet de la tour  qui vont tomber avec
l’expression Python :

\begin{center}
  \Colorbox{blue!10}{\lstinline{int( ( h + 2.0 )/2 * random() ) + 1}}
\end{center}

Dans l’exemple  figure 1,  lors du  passage de l’état  1 à  l’état 2,  le hasard
introduit par la  fonction \Colorbox{blue!10}{\lstinline{random()}} (qui renvoie
de manière aléatoire un flottant
dans  l’intervalle semi-ouvert  [0.0, 1.0[)  fait que  toute la  tour se  décale
apparemment vers la  droite. Ensuite, pour le  passage à l’état 3  seul un grain
sur les trois possibles  tombe. L’état 3 est stable, plus  aucun grain ne tombe.

\begin{enumerate}

\item Quel est le type de l’expression 
\Colorbox{blue!10}{\lstinline{int( ( h + 2.0 ) / 2 * random() ) + 1}}?

Déterminer un encadrement de sa valeur, sachant que $h > 1$.

\item Écrire
une  fonction  nommée  \Colorbox{blue!10}{\lstinline{calcul_n }}  qui  prend  la
hauteur d'une pile
  comme argument et qui renvoie le nombre de grains qui vont tomber sur la pile
suivante. 

 Il  est rappelé  que le  (demi-)tas est  complètement défini  avec un
tableau (ou  une liste) unidimensionnel qui  permet de stocker  la hauteur des
différentes  piles.  Au   départ  le  support  est  vide  et   on  vient  déposer
périodiquement un  grain sur  la première  pile (à  gauche) qui  correspondra au
sommet du demi-tas. Le  support peut recevoir P piles et  à son extrémité droite
il  n’y a  rien, les  grains tombent  et sont  perdus. La  pile $P  + 1$  est donc
toujours vide.  


\item Définir  la fonction \Colorbox{blue!10}{\lstinline{ initialisation}} prenant  un
entier P  en paramètre et  renvoyant une liste contenant  P piles de  hauteur 0.


\item Définir une fonction \Colorbox{blue!10}{\lstinline{actualise }} prenant comme paramètres une liste
\Colorbox{blue!10}{\lstinline{piles}}           et           un           entier
\Colorbox{blue!10}{\lstinline{perdus}} qui va parcourir les piles de gauche à droite et les
faire  évoluer  en  utilisant  les   règles,  fonctions  et  variables  définies
précédemment. Cette fonction doit renvoyer  un couple formé d’une nouvelle liste
décrivant la situation du tas de sable  après ces opérations ainsi que du nombre
de grains  perdus (en prenant  en compte ceux qui  seront tombés de  la dernière
pile P ).


Il est  rappelé que Python permet  de renvoyer un couple  de valeurs A et  B par
l’instruction \Colorbox{blue!10}{\lstinline{return A, B}}. 
On pourra,  dans les questions suivantes, utiliser la
fonction  \Colorbox{blue!10}{\lstinline{actualise}} par  un  appel  de la  forme
suivante:

\begin{center}
 \Colorbox{blue!10}{\lstinline{ (nouveau_tas,nouveaux_perdus) = actualise(ancien_tas, anciens_perdus) }} 
\end{center}
 



\item Écrire le
bloc d’instructions  du programme principal  qui permet  d’ajouter 1 grain  à la
première pile après chaque dizaine d’exécutions  de la fonction \Colorbox{blue!10}{\lstinline{actualise}} et qui
s’arrêtera lorsqu’au  moins 1000 grains seront  sortis du support. Le  nombre de
piles  (taille   du  support  P   )  sera   demandé  à  l’utilisateur   lors  de
l’exécution. Vous  utiliserez les fonctions et  variables définies précédemment.

  \end{enumerate}




  
\end{exercice}



\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
