\documentclass[a4paper,11pt]{article}

\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}
%\usepackage{fullpage}
\usepackage{multicol}
%\usepackage{picinpar}
%\setlength{\textheight}{24.1cm}
%\setlength{\textwidth}{19 cm}
%\evensidemargin 0cm
%\oddsidemargin  0cm
%\topmargin 0cm
%\textheight 23cm
%\leftmargin 5cm
%\textwidth 15cm

%\flushbottom
%\parindent 1em
%\hoffset -0.5in
%\oddsidemargin 0pt
%\evensidemargin 0pt
%\marginparsep 10pt
\usepackage{epsfig}

%\newcommand{\elem}[1]{\bigskip \noindent {\bf #1}}
\newcounter{exercice}
\newcommand{\exo}{\stepcounter{exercice} \bigskip \noindent {\bf 
Exercice \theexercice . } }
%\newcommand{\td}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TD). } }
%\newcommand{\tp}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TP). } }
%\newcommand{\tptd}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TP-TD). } }
%\newcounter{abclist}
%\newenvironment{abc}{\begin{list}{(\alph{abclist})}{\usecounter{abclist}}}
%{\end{list}}
%\newcommand{\Feuille}[1] {\hfill  {\Large Feuille de TD / TP
%n$^o$\,#1} \hfill IF122
%\vskip 1mm}
%\newcommand{\titre}[1] {\vskip 10mm{\Huge\hfill #1\hspace*{\fill}}
%\vskip 10mm}

%\def\R{\mbox{I\hspace{-.15em}R}}



%\def\dangermarge{\noindent\hbox to
%  0pt{\hskip-\parindent\dbend\hfill}\ignorespaces}


%\pagestyle{empty}

%\newtheorem{rmq}{Remarque}
%\newcommand{\bs}{\symbol{92}}

% Titre
\title{Controle Continu IF122}
\date{}
\author{}
\pagestyle{empty}



\begin{document}

\maketitle
\vspace{-2cm}


{\bf Les documents sont interdits.  La dur\'ee de l'\'epreuve est de
1h50. Le bar\`eme est donn\'e \`a titre indicatif. Bonne chance.}\\



%\Feuille{}

%\titre{}

\bigskip


\exo {\bf Pointeurs} (10 minutes, 4 points)\\

On consid\`ere le programme suivant, qui comporte quelque lignes en
commentaire : {\small
\begin{verbatim}
#include <iostream>
//void toto( ... x, ... y){
//  **x = *y;
//  }
int main(){
 int i=2;
 int j=12;
 int *pi= &i;
 int *ln= new int, e[]={3,1,7,9,14};
 
 pi = ln; 
 *ln = 4;
 cout << *pi << " , " << *ln << endl;
 *pi=j+1;
 pi=&i;
 cout << *pi << " , " << *ln << endl;
 ln=e;
 cout << *(ln+*pi) << " , " << *ln + *pi << endl;

 // toto ( & pi, e);
 // cout << e[0] << endl;
  return 0;
}
\end{verbatim}
}

\begin{enumerate}
 \item Qu'affiche t'il ? Justifier rapidement chaque \'etape de votre
 r\'eponse.
 \item Ce programme comporte une erreur, laquelle ?
 \item On veut d\'ecommenter les lignes, quel type doit on donner aux
 arguments de {\bf toto} ? Que produit le dernier affichage ?
\end{enumerate}

\exo {\bf R\'ecursion} (20 minutes) (4 points)\\

Un esprit tordu a \'ecrit une partie du code suivant :
{\small
\begin{verbatim}
void affiche(int T[],int n) // procedure qui affiche les n elements du tableau
                            // n est suppose < dimension du tableau T 

// procedure bizarre
void proc (int T[],int n, int c){   // n est < dim de T
int i;
if (c<=0) affiche(T,n);
 else {
   for (i=1;i<=n;i++){
   T[c-1]=i;
   proc(T,n,c-1);
   }
 }
}
\end{verbatim}
}

\begin{enumerate}
 \item Ecrivez le code pour la procedure affiche. En it\'eratif, puis
 en r\'ecursif.
 \item Qu'est ce qui est affich\'e lors de l'ex\'ecution de {\bf
 proc(T,2,2)} ? Il est demand\'e de justifier avec pr\'ecaution votre
 r\'eponse, par exemple en dessinant un arbre associ\'e \`a
 l'ex\'ecution.
\end{enumerate}

\exo {\bf Liste} - (Presque question de cours  $< 20$ minutes) (4 points)\\
 
Une {\bf liste circulaire} se d\'efinit presque comme une liste
chain\'ee : elle est compos\'ee d'une liste de cellules chain\'ees
entre elles, sauf que ce qui pourrait \^etre le dernier \'el\'ement de
cette liste a pour successeur le premier \'el\'ement. Voici un exemple
:\\

\begin{center}\epsffile{exemple.eps}\end{center}

Il \'etait facile de parcourir une liste chain\'ee, puisque sa fin
\'etait marqu\'ee par NULL. Il faudra maintenant trouver une
alternative.\\

\begin{enumerate}
 \item Ecrivez les types n\'ecessaires pour une liste d'entiers
 circulaire.
 \item Ecrivez une proc\'edure qui affiche une liste d'entier
 circulaire.
\end{enumerate}



\exo {\bf Probl\`eme : Structure de donn\'ees - Mod\'elisation} (1h00)
(8 points)\\

On presente ici le {\bf mancala} : ce jeu se joue \`a deux joueurs,
face \`a face, avec un plateau entre eux (voir figure). Le plateau est
compos\'e de 2 lignes de 6 cases, initialement chacune des cases
contient 4 graines, la ligne la plus proche d'un joueur est son camp.

\begin{center}\epsffile{awale-board.eps}\end{center}


Chacun \`a son tour un joueur va prendre toutes les graines d'une des
cases de son camp, et va les distribuer dans le sens inverse des
aiguilles d'une montre, en partant de la case suivante de celle qu'il
\`a vid\'e.

Sauf que pendant la redistibution des graines, lorsqu'il passe d'une
case de son camps \`a une case du camps adverse, il engrange
d\'efinitivement l'une des graines en se servant parmis celles qui lui
reste \`a distribuer, puis il poursuit la distribution.

Sym\'etriquement si pendant la distribution il doit passer d'une case
du camps adverse \`a une de son camp, alors l'adversaire engrange
l'une de ces graines.

Le jeu s'arr\^ete lorsqu'un joueur ne peut plus jouer. On fait alors
pour chaque joueur la somme des graines qu'il a mis de cot\'e, avec
celles qui lui reste dans son camp. Le gagnant est celui qui en a le
plus.


Un exemple de phase de jeu : si le joueur 1, joue la case marqu\'ee
par une fleche, alors apr\`es la distribution, il aura mis une graine
de cot\'e, et laissera le plateau suivant pour le joueur 2 :

\begin{center}\epsffile{awale-un-coup.eps}\end{center}


\begin{enumerate}
 \item A votre convenance, d\'efinissez un type de donn\'ees qui
 permette de mod\'eliser \`a la fois l'\'etat du plateau, les gains
 engrang\'es, et le tour de jeu. {\bf Attention}, comme il y a de
 nombreuses solutions, vous devrez d\'efendre votre choix et bien
 expliquer \`a quoi correspondent votre (ou vos) types. (2 points)

 \item Ecrire une fonction {\bf reset} qui permettra de commencer avec
 un jeu dans sa configuration initiale. (1 point)

 \item Ecrire une fonction {\bf test\_fin} qui permet de savoir si le
 jeu est fini ou non. (1 point)

\item Ecrire une fonction {\bf qui\_gagne} qui retourne le numero du
joueur gagnant lorsque le jeu est termin\'e, $-1$ si on ne sais pas
encore, et $0$ en cas d'egalit\'e. (1 point)

\item Ecrire une proc\'edure {\bf joue}, avec deux arguments :
l'\'etat du jeu, et un moyen d'identifier le coup propos\'e, qui a
pour effet de changer l'\'etat en fonction du coup. (2 points)

\item Donner un programme complet. (1 point)

\end{enumerate}


\end{document}
