%% LyX 1.2 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[french]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\usepackage{color}
\usepackage{graphicx}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\date{}

\usepackage{babel}
\makeatother
\begin{document}

\title{TD/TP n°4 ~{\small (IF122)} \\
Programmation de fonctions récursives}
\medskip{}

\maketitle
\begin{center}\vspace{-1cm}\includegraphics[  scale=0.25]{allumettes}\end{center}


\section*{Le jeu des allumettes (Nim ou jeu de Marienbad)}

Le jeu se joue à deux. Plusieurs allumettes (représentée par des 1)
sont disposées sur 21 emplacement.

\medskip{}
\begin{center}\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
\texttt{\textcolor{green}{\scriptsize 0}}&
\texttt{\textcolor{green}{\scriptsize 1}}&
\texttt{\textcolor{green}{\scriptsize 2}}&
\texttt{\textcolor{green}{\scriptsize 3}}&
\texttt{\textcolor{green}{\scriptsize 4}}&
\texttt{\textcolor{green}{\scriptsize 5}}&
\texttt{\textcolor{green}{\scriptsize 6}}&
\texttt{\textcolor{green}{\scriptsize 7}}&
\texttt{\textcolor{green}{\scriptsize 8}}&
\texttt{\textcolor{green}{\scriptsize 9}}&
\texttt{\textcolor{green}{\scriptsize 10}}&
\texttt{\textcolor{green}{\scriptsize 11}}&
\texttt{\textcolor{green}{\scriptsize 12}}&
\texttt{\textcolor{green}{\scriptsize 13}}&
\texttt{\textcolor{green}{\scriptsize 14}}&
\texttt{\textcolor{green}{\scriptsize 15}}&
\texttt{\textcolor{green}{\scriptsize 16}}&
\texttt{\textcolor{green}{\scriptsize 17}}&
\texttt{\textcolor{green}{\scriptsize 18}}&
\texttt{\textcolor{green}{\scriptsize 19}}&
\texttt{\textcolor{green}{\scriptsize 20}}\\
\hline 
1&
&
&
1&
1&
1&
1&
&
&
&
1&
1&
&
&
&
1&
1&
&
1&
1&
1\\
\hline
\end{tabular}\end{center}
\medskip{}

A chaque tour vous pouvez retirer une, deux ou trois allumettes se
situant dans des cases consécutives. Le but du jeu est de faire retirer
la dernière allumette par son adversaire. Autrement dit, celui qui
ramasse la dernière allumette perd.

\medskip{}
\noindent Toute position du jeu peut être représentée par la structure
suivante~:

\begin{lyxcode}
typedef~struct~position~\{~

~~int~damier~{[}21{]};~~~~//~damier{[}0..20{]},~0~=>~vide,~1~=>~allumette~

~~int~player;~~~~~~~~~//~0~=>~ordi,~1~=>~humain

\};~
\end{lyxcode}
\medskip{}
Par ailleurs, le coup d'un joueur peut être représenté par la structure
suivante~:

\begin{lyxcode}
typedef~struct~coup~\{~~~

~~int~pos;~~~~~~~~~~~//~0..20~position~de~la~première~case~concernée~~~

~~int~nb;~~~~~~~~~~~~//~1..3~~nombre~d'allumettes~retirées

\};~
\end{lyxcode}
\medskip{}
Par exemple, le coup par lequel on enlève les deux allumettes des
cases 10 et 11 de la position ci-dessus, sera codé par une variable
\texttt{c} de type \texttt{coup} telle que \texttt{c.pos=10} et \texttt{c.nb=2}. 


\subsection*{Exercice 1}

Écrire une fonction \textbf{récursive} \texttt{bool coup\_possible(position
p, coup c)} qui vérifie si le coup c est possible dans la position
p donnée (il faut qu'il y ait assez d'allumettes à enlever que le
coup le demande). En ce qui concerne le caractère récursif du problème,
pensez que vérifier la possibilité d'enlever \texttt{n} allumettes
voisines, signifie vérifier de pouvoir en enlever une, puis de pouvoir
enlever les \texttt{n-1} voisines...


\subsection*{Exercice 2}

Écrire une fonction \textbf{récursive} \texttt{position mouvement
(position p, coup c)} qui retourne la nouvelle position du jeu, après
le coup c dans la position p (on peut supposer que le coup soit possible).
Il s'agit, en d'autres termes, d'effacer des allumettes (mettre à
0 des cases du damier). \`A nouveau, si on doit en effacer \texttt{n},
on peut toujours commencer par en effacer une, pour ensuite effacer
les \texttt{n-1} suivantes... Suggestion : ne pas oublier aussi de
changer de main (les joueurs s'alternent).


\subsection*{Exercice 3}

Écrire une fonction \textbf{récursive} \texttt{coup entrer\_coup (position
p)} qui demande à l'utilisateur d'entrer les deux valeurs définissant
son coup \texttt{(pos,nb)} \emph{tant que} le coup n'est pas un coup
\emph{possible} dans la position \texttt{p} donnée.


\subsection*{Exercice 4}

Une position p est \emph{terminale} lorsque il n'y a plus d'allumettes.
Autrement dit, lorsque toutes les valeurs du damier \texttt{p.damier{[}{]}}
sont à zéro. La fonction suivante permet de réaliser ce test~:

\begin{lyxcode}
bool~terminale~(position~p)~\{~

int~i~=~0;~

while~((i<=20)~\&\&~(p.damier{[}i{]}==0))~i++;

return~(i>20);~

\}~
\end{lyxcode}
Écrire une version équivalente de la fonction ci-dessus s'appuyant
sur un procédé \textbf{récursif} et non pas sur une boucle \texttt{while}.


\subsection*{Exercice 5}

Il est possible de déterminer si une position p du jeu est \emph{gagnante}
pour le joueur qui a la main (\texttt{p.player}), par un raisonnement
\textbf{récursif}. En effet, si la position est terminale le joueur
en question a gagné, puisque au tour précédent, son adversaire a enlevé
la dernière allumette. En revanche, si la position n'est pas terminale,
alors il suffit d'explorer tout les coups possibles~: si on trouve
un coup conduisant à une position \texttt{p'} perdante (non \emph{gagnante}...)
pour son adversaire, la position \texttt{p} est \emph{gagnante}, sinon
elle est perdante. Suivant cette idée, écrire une fonction récursive~:

\begin{lyxcode}
bool~gagnante~(position~p)
\end{lyxcode}

\subsection*{Exercice 6}

Supposer à présent d'avoir à disposition~: 

\begin{itemize}
\medskip{}
\item une procédure d'affichage d'une position~: \texttt{void affiche(position
p)} (très simple à écrire en TP), produisant une sortie de ce genre~: 
\end{itemize}
\bigskip{}
\texttt{\scriptsize ~~~~~~~~~~~~~~~~+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+ }{\scriptsize \par}

\noindent \texttt{\scriptsize ~~~~~~~~~~~~~~~~| 0|
1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|19|20|}{\scriptsize \par}

\noindent \texttt{\scriptsize ~~~~~~~~~~~~~~~~+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+ }{\scriptsize \par}

\noindent \texttt{\scriptsize ~~~~~~~~~~~~~~~~| 0|
1| 1| 1| 0| 1| 1| 0| 1| 1| 0| 0| 1| 0| 0| 0| 0| 1| 1| 0| 1|}{\scriptsize \par}

\noindent \texttt{\scriptsize ~~~~~~~~~~~~~~~~+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+-{}-+}{\scriptsize \par}

\noindent \texttt{\scriptsize ~~~~~~~~~~~~~~~~Player
: 0 }{\scriptsize \par}

\begin{itemize}
\bigskip{}
\item une fonction qui calcule le meilleur coup pour l'ordinateur~: \texttt{coup
ordi\_malin (position p)} (très simple à écrire en TP, en utilisant
\texttt{gagnante()})
\end{itemize}
\medskip{}
Écrire alors une procédure \textbf{récursive}~: 

\begin{lyxcode}
void~boucle\_jeu(position~p)
\end{lyxcode}
qui réalise la boucle d'interaction du jeu, c'est-à-dire la boucle
où la position courante est affichée et l'utilisateur est sollicité
pour entrer son coup, lorsque c'est à lui de jouer, ou bien la fonction
\texttt{ordi\_malin()} est appelée, lorsque c'est au tour de la machine.
Cela jusqu'à la fin du match.
\end{document}