\documentclass[xcolor=hyperref,hyperef={naturalnames,pdfpagelabels},french]{beamer}
\usepackage{etex}
\usepackage[beamer]{preambule}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark}
\usepackage{movie15}
%\usepackage{multimedia}
\usepackage{cclicenses}
\usepackage{cclicence}

\graphicspath{{/home/moi/Lycee/2nde/2009_10/}{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Figures/figuresTS/}{/home/moi/Lycee/TDmaple/2007_8/}{/home/moi/IREM/IREM10_06_09/}}



\newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
keywordstyle =\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\caml{
\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}
\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}

\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}

\title[] % (optional, use only with long paper titles)
{Programmation récursive/impérative}

\subtitle{ Une introduction}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN  }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IREM} de Nantes}% (optional, but mostly needed)

\logo{\includegraphics[scale=0.15]{logoirem}}

\date[] % (optional, should be abbreviation of conference name)
{\today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{Programmation récursive/impérative}


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
%\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
%       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
%\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
%       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
%\begin{multicols}{2}
    \tableofcontents[currentsection]
%       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}









\begin{document}


\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
%\begin{multicols}{2} 
 \tableofcontents
%\end{multicols}
}

 
 \end{frame}


\section{Programmation impérative et affectations}

\subsection{Aspect technique}


\begin{frame}
  
La  programmation  impérative est  la  plus  répandue (Fortran,  Pascal,
C,...)  et la  plus proche  de la  machine réelle.  Son principe  est de
modifier   à   chaque   instant   l'état   de   la   mémoire   via   les
affectations.  Historiquement,  son  principe  a  été  initié  par  John
\textsc{Von Neumann} et Alan \textsc{Turing}.
\end{frame}


\begin{frame}[fragile]
  
Par exemple, lorsqu'on entre avec XCAS~:



\xc
\begin{lstlisting}
a:=2
\end{lstlisting}

cela  signifie que  la case  mémoire  portant le  petit \og  fanion\fg{}
\texttt{a} contient à cet instant la valeur 2.
\end{frame}



\begin{frame}[fragile]
  
On peut changer le contenu de cette case mémoire un peu plus tard~:

\xc
\begin{lstlisting}
a:=4
\end{lstlisting}

\pause

et cette fois la case \texttt{a} contient la valeur 4.
\end{frame}



\begin{frame}[fragile]
  
Le  caractère  chronologique  de  ce  type  de  programmation  est  donc
primordial. Regardons la suite d'instructions suivante~:

\pause

\xc
\begin{lstlisting}[caption={attention aux affectations}]
a:=1;
b:=2;
a:=a+b; // maintenant a contient 3
b:=a-b; // maintenant b contient 3-2=1
a:=a-b; // maintenant a contient 3-1=2
\end{lstlisting}

\end{frame}



\begin{frame}
  \begin{block}{Danger}

Il faut donc être extrêmement attentif à la chronologie des instructions
données.  C'est un  exercice intéressant  en  soi mais  pas sans  danger
(c'est d'ailleurs la source de la plupart des \og bugs\fg{} en informatique).
  
\end{block}
\end{frame}


\begin{frame}[fragile]
  
Question~:~est-ce que 

\xc
\begin{lstlisting}
a:=3;
a:=a+1;
\end{lstlisting}

dit la même chose que 

\xc
\begin{lstlisting}
a:=a+1;
a:=3;
\end{lstlisting}

\end{frame}



\begin{frame}
  
La motivation première de ce type de fonctionnement a été pratique~:~les
ordinateurs  étant peu puissants,  le souci  principal du  concepteur de
programme a  longtemps été d'économiser  au maximum la mémoire.  Au lieu
d'accumuler  des   valeurs  dans  différents  endroits   de  la  mémoire
(\emph{répartition spatiale}), on les stocke  au même endroit mais à différents
moments (\emph{répartition  temporelle}). C'est le modèle des  machines à états
(machine de \textsc{Turing} et architecture de \textsc{Von Neumann}) qui
impose au programmeur  de connaître à tout instant  l'état de la mémoire
centrale. 

\end{frame}



\subsection{Exploitation mathématique possible}


\begin{frame}
  
En classe  de mathématique,  cet aspect technique  nous importe  peu. Il
nous   permet   cependant  d'illustrer   dynamiquement   la  notion   de
fonction~:

\end{frame}


\begin{frame}[fragile]
  
\xc
\begin{lstlisting}[caption={affectation et image par une fonction}]
y:=x^2+1;

x:=1;   y;   // ici y=2
x:=-5;  y;   // ici y=26
x:=1/2; y;   // ici y=5/4
\end{lstlisting}

\pause


La fonction $f~:~x\mapsto x^2+1$ dépend de la variable $x$. On affecte une certaine
valeur à  la variable ce  qui détermine la  valeur de son image. 


\end{frame}


\begin{frame}
  \begin{block}{Remarque}
Il est
toutefois  à noter qu'en  fait on  a travaillé  ici sur  des expressions
numériques et non pas des fonctions.  

\end{block}
\end{frame}




\begin{frame}[fragile]
  
On peut enchaîner des affectations~:

\xc
\begin{lstlisting}[caption={affectation et composition de fonctions}]
y:=x^2+1;
z:=y+3;

x:=1;   y; z;  /* ici y:=2 et z=5 */
x:=-5   y; z;  // ici y=26  et z=29;
x:=1/2; y; z;  // ici y=5/4 et z=17/4;
\end{lstlisting}


\pause

et illustrer ainsi la composition de fonctions.
\end{frame}





\begin{frame}
  

Avec un peu de mauvaise foi  (car le cas est simple et artificiel) mais pas tant que
ça puisque  de tels problèmes  sont source de  milliers de bugs  sur des
milliers de  programmes plus compliqués, nous allons  mettre en évidence
un problème majeur de ce genre de programmation quand on n'est pas assez
attentif.
\end{frame}

\begin{frame}[fragile]
  
On créé à un certain moment  une variable\verb+a+ à laquelle on affecte
une valeur~:
\xc
\begin{lstlisting}
a:=2;
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
  
On   introduit  plus  tard   une  procédure   (une  sorte   de  fonction
informatique des  langages impératifs) qu'on  nomme $f$ et  qui effectue
certains calculs en utilisant $a$~:

\pause

\xc
\begin{lstlisting}[caption={exemple de procédure}]
f(x):={
  a:=a+1;
  return(x+a)
}
\end{lstlisting}
\end{frame}

\begin{frame}
  

On  peut donc construire  un objet  qui \textbf{ressemble}  à une  fonction d'une
variable (mais qui  n'en est évidemment pas) et qui  à une même variable
renvoie  plusieurs valeurs.  En  effet, une  procédure
ne dépend pas  uniquement des
arguments  entrés et  donc  peut  changer de  comportement  au cours  du
programme~:~c'est ce qu'on appelle en informatique des \emph{effets de  bord}.
\end{frame}



\begin{frame}
  Certains
  langages  utilisent  le  terme  fonction  mais  nous  préférerons  \og
  procédure\fg{}   pour   ne    pas   confondre   avec   les   fonctions
  mathématiques. 
\end{frame}


\begin{frame}
  
On a en fait plutôt construit ici une fonction de deux variables~:

\[g~:~(a,x)->x+a\]

Le premier appel de $f(5)$ est en fait $g(3,5)$ et le deuxième $g(4,5)$,
etc. mais on a pu le faire en utilisant une forme qui \textbf{laisse à penser}
que $f$ est  une fonction qui renvoie une  infinité d'images différentes
d'un même nombre.
\end{frame}


\begin{frame}[fragile]
  
Informatiquement, $a$
 et $x$  jouent des rôles différents  puisque $x$ est un  argument de la
 procédure $f$ et $a$ est une variable globale donc \og extérieure\fg{}
 à  $f$ (on  dirait  un \emph{paramètre}).  D'ailleurs,  XCAS envoie  un
 avertissement pour nous le rappeler ~:

\verb+// Warning: a, declared as global variable(s) compiling f+

\end{frame}




\begin{frame}
  \begin{block}{Danger}
Il faudra donc veiller à éviter le recours à des variables globales.
  \end{block}
\end{frame}


\subsection{Programmation fonctionnelle}


\begin{frame}
  

\textbf{Les    langages   fonctionnels    bannissent    totalement   les
  affectations.} 
\pause

Ils
utilisent   des  fonctions   \emph{au  sens   mathématique   du  terme},
c'est-à-dire qu'une fonction  associe une unique valeur de  sortie à une
valeur donnée en entrée.  

\pause

Les  fonctions peuvent être testées une  par une car
\emph{elles ne  changent pas  selon le  moment où elles  sont appelées  dans le
programme.}         On         parle        de        \emph{transparence
référentielle}.

\pause


 Le programmeur  n'a donc pas besoin de  savoir dans quel
état se trouve la mémoire. C'est  le logiciel qui s'occupe de la gestion
de la mémoire.


\end{frame}


\begin{frame}
  
Historiquement, ce style de programmation est né du
$\lambda$-calcul  développé par  Alonzo \textsc{Church}  juste  avant la
publication des travaux d'Alan \textsc{Turing} qui a
  d'ailleurs été un étudiant de Church à Princeton...

\end{frame}


\begin{frame}
  
La  \textbf{récursivité} est  le  mode  habituel de  programmation  avec de  tels
langages~:~il s'agit  de fonctions qui  s'appellent elles-mêmes. Pendant
longtemps,  la  qualité des  ordinateurs  et  des langages  fonctionnels
n'était pas  suffisante et limitaient les domaines  d'application de ces
langages.

\end{frame}

\begin{frame}
  
On  utilise  également  en  programmation  fonctionnelle  des  \textit{fonctions
d'ordre  supérieur}, c'est-à-dire  des fonctions  ayant  comme arguments
d'autres fonctions~:~cela permet par  exemple de créer des fonctions qui
à une fonction dérivable associe sa fonction dérivée.


\end{frame}



\subsubsection{Une récursion concrète}




\begin{frame}
  
On place un certain nombre d'élèves en les classant par ordre décroissant
de taille. 

\pause

Le plus grand voudrait connaître sa propre taille mais chaque
élève ne peut mesurer que son écart de taille avec son voisin.

\pause

 Seul le
plus petit connaît sa taille.
\end{frame}




\begin{frame}
  
Le plus  grand mesure son  écart avec son  voisin et garde le  nombre en
mémoire. 
\pause

 Le voisin  fait de  même avec  son propre  voisin et  ainsi de
suite.
\pause

 Enfin l'avant dernier fait de même puis le plus petit lui transmet
sa taille : il peut donc calculer sa propre taille et transmet la au
suivant et ainsi de suite. Chacun va ainsi pouvoir calculer sa taille
de proche en proche....

\end{frame}



\subsubsection{Un premier exemple d'algorithme récursif}


\begin{frame}
  
Si nous  reprenons notre exemple précédant, nous  pouvons faire exprimer
aux élèves  que l'entier  suivant $n$ est  égal à $1+$  l'entier suivant
$n-1$ : on ne  sort pas des limites du cours de  mathématiques et on n'a
pas besoin  d'introduire des  notions d'informatique en  travaillant sur
cette notion.

\end{frame}



\begin{frame}[fragile]
  
On peut écrire un algorithme ainsi~:


\begin{minipage}{\textwidth}
\begin{algorithm}[H]
%\caption{successeur d'un entier~-~version récursive}
\eSi{$n=0$}{1}{$1+$ successeur de $n-1$}
\end{algorithm}\end{minipage}

\end{frame}



\begin{frame}
  
La  récursivité  n'est  pas  l'apanage des  langages  fonctionnels.  Par
exemple XCAS permet d'écrire des programmes récursifs.

\end{frame}

\begin{frame}[fragile]
  
En français~:


\xc
\begin{minipage}{\textwidth}
\xc
\begin{lstlisting}[caption={exemple de programme récursif}]
successeur(k):={
 si k==0 alors 1
 sinon 1+successeur(k-1)
 fsi
}:;
\end{lstlisting}\end{minipage}

\end{frame}


\begin{frame}[fragile]
  

En anglais~:

\begin{minipage}{\textwidth}
\xc
\begin{lstlisting}[caption={exemple de programme récursif en anglais}]
successeur(k):={
 if(k==0)then{1}
 else{1+successeur(k-1)}
}:;
\end{lstlisting}\end{minipage}

\end{frame}




\begin{frame}[fragile]
  
Que  se passe-t-il  dans  le  c\oe ur  de  l'ordinateur lorsqu'on  entre
\verb+successeur(3)+~?


\end{frame}



\begin{frame}[fragile]
  
\begin{itemize}


\item On entre comme argument 3~;

\item Comme 3  n'est pas  égal à 0,  alors\verb+successeur(3)+ est  stocké en
mémoire et vaut
\verb/1+successeur(2)/~;


\item Comme 2 n'est pas égal à 0, alors\verb+successeur(2)+ est stocké en
mémoire et  vaut
\verb/1+successeur(1)/~;


\item Comme 1 n'est pas égal à 0, alors\verb+successeur(1)+ est stocké en
mémoire et  vaut
\verb/1+successeur(0)/~;

\end{itemize}
\end{frame}



\begin{frame}[fragile]
  
\begin{itemize}
\item Cette fois,\verb+successeur(0)+ est connu et vaut 1~;


\item\verb+successeur(1)+ est maintenant connu et vaut \verb/1+successeur(0)/
c'est-à-dire 2~;



\item\verb+successeur(2)+ est maintenant connu et vaut \verb/1+successeur(1)/
c'est-à-dire 3~;


\item\verb+successeur(3)+ est maintenant connu et vaut \verb/1+successeur(2)/
c'est-à-dire 4~:~c'est fini~!

\end{itemize}

\end{frame}

\begin{frame}
  

C'est  assez  long  comme  cheminement  mais  ce  n'est  pas  grave  car
\emph{c'est  l'ordinateur qui  effectue  le \og  sale boulot\fg{}}~!  Il
stocke les  résultats intermédiaires  dans une \emph{pile}  et n'affiche
finalement que le résultat.


\pause

Comme il calcule  vite, ce n'est pas grave. L'élève  ou le professeur ne
s'est occupé que de la définition récursive (mathématique~!) du problème.



\end{frame}







\begin{frame}[fragile]
  

XCAS calcule facilement\verb+successeur(700)+ mais
\verb+successeur(7000)+ dépasse les possibilités de calcul du logiciel.

\pause

Et oui, un langage impératif ne traite pas efficacement le problème de pile, 
c'est pourquoi pendant longtemps  seuls les algorithmes
impératifs ont prévalus. 


\end{frame}




\begin{frame}
  
Utilisons  à   présent  le  langage  fonctionnel   OCAML,  développé  par
l'INRIA. Même s'il intègre  des aspects impératifs pour faciliter
l'écriture de  certains algorithmes, il  est en premier lieu  un langage
fonctionnel  qui en  particulier gère  très efficacement  la  mémoire de
l'ordinateur pour éviter sa saturation lors d'appels récursifs.

\end{frame}


\begin{frame}[fragile]
  
Le programme s'écrit comme en mathématique (mais en anglais...)~:


\caml

\begin{lstlisting}[caption={successeur d'un entier}]
# let rec successeur(k)=
  if k=0 then 1
  else 1+successeur(k-1);;  
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  
Alors par exemple~:
\caml
\begin{lstlisting}
# successeur(36000);;
- : int = 36001
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  
Mais
\caml
\begin{lstlisting}
# successeur(3600000);;
Stack overflow during evaluation (looping recursion?).
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  
La \emph{pile} où sont stockés les résultats intermédiaires créés par la
récursion est en effet saturée.

\pause

Aujourd'hui, les langages fonctionnels  sont très efficaces et gèrent de
manière  intelligente  la  \emph{pile}. Ils le font soit automatiquement,
soit si la fonction utilise une \emph{récursion terminale}, c'est-à-dire
si l'appel récursif à la fonction n'est pas \emph{enrobé} dans une autre
fonction. 

\pause

Ici, ce  n'est pas le  cas car l'appel récursif \verb+successeur(k-1)+ est
enrobé dans la fonction $x\mapsto 1+x$.
\end{frame}




\begin{frame}
  
{\large \bf Dans un premier temps,  on peut laisser de côté ce problème
de récursion terminale au lycée et se contenter de travailler sur de petits
entiers.  Ainsi, on peut  choisir de  travailler avec  OCAML ou  XCAS par
exemple, même si ce dernier n'est pas un langage fonctionnel.}

\end{frame}





\subsection{Un premier exemple de fonction d'ordre supérieur}



\begin{frame}
  
Définissons  une fonction qui  à deux  fonctions $f$  et $g$  associe sa
composée $f\circ g$~:

\end{frame}

\begin{frame}[fragile]
  \caml
\begin{lstlisting}[caption={composition de fonction}]
# let compose=function
   (f,g) -> function x->f(g(x));;
\end{lstlisting}

\pause

OCAML devine le type des objets introduits en répondant~:

\begin{lstlisting}
val compose : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b = <fun>
\end{lstlisting}



\end{frame}


\begin{frame}
  On peut schématiser ce qu'a compris OCAML~:

\[f~:~'a\mapsto  'b \qquad  g~:~'c\mapsto 'a\qquad  f\circ g~:~'c\mapsto
'b\]
\end{frame}


\begin{frame}[fragile]
  
Créons deux fonctions numériques~:
\caml
\begin{lstlisting}[caption={création de fonctions simples}]
# let carre = function
      x -> x*x;;

# let double = function
     x -> 2*x;;
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
\caml
Composons-les~:

\begin{lstlisting}
# compose(double,carre)(2);;
- : int = 8
# compose(carre,double)(2);;
- : int = 16
\end{lstlisting}

En effet, le double du carré de 2  est 8 alors que le carré du double de
2 vaut 16...

\end{frame}









\begin{frame}[fragile]
            
              On peut faire la même chose avec XCAS~:

\xc

\begin{lstlisting}[caption={composée de fonctions avec XCAS}]
compose(f,g):={
  x->f(g(x))
}
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
             \xc
              
\begin{lstlisting}
compose(x->x^2,x->2*x)(2)
\end{lstlisting}

\end{frame}










\section{Deux manières d'aborder un même problème}

\subsection{Les tours de Hano\"i}

\subsubsection{Le principe}


\begin{frame}
  
Ce casse-tête a été posé  par le  mathématicien
français Édouard \textsc{Lucas} en 1883.

Le  jeu  consiste  en  une  plaquette  de bois  où  sont  plantés  trois
piquets. 

\begin{itemize}
\item on ne déplace qu'un disque à la fois~;
\item on ne peut poser un disque que sur un disque de diamètre supérieur.
\end{itemize}

\end{frame}









\begin{frame}
  
\begin{figure}
\begin{center}
  \includegraphics[width=\textwidth]{hanoi}
\end{center}
\end{figure}

\end{frame}




\subsubsection{Non pas comment mais pourquoi~:~version récursive}


\begin{frame}
  
 En  réfléchissant récursivement,  c'est enfantin~!...  Pour  définir un
 algorithme récursif, il nous
faut régler un cas simple et pouvoir simplifier un cas compliqué.

\end{frame}



\begin{frame}
  
\begin{itemize}
\item \emph{cas simple}~: s'il y a zéro disque, il n'y a rien à faire~!
\item \emph{simplification d'un cas  compliqué}~: nous avons $n$ disques
  au départ  sur le premier disque  et nous savons  résoudre le problème
  pour $n-1$ disques. Appelons A, B et C les piquets de
  gauche à droite. Il suffit de déplacer les $n-1$ disques supérieurs de
  A vers B (hypothèse de récurrence) puis on déplace le plus gros disque resté sur A en C. Il ne
  reste  plus qu'à  déplacer vers  C les  $n-1$ disques  qui  étaient en
  B. (hypothèse de récurrence).
\end{itemize}

\end{frame}


\begin{frame}
  
On voit bien  la récursion~:~le problème à $n$ disques  est résolu si on
sait résoudre le cas à $n-1$ disques  et on sait quoi faire quand il n'y
a plus de disques. 

\pause

On sait pourquoi  cet algorithme va réussir mais on  ne sait pas comment
s'y prendre étape par étape.

\pause

On va donc  appeler à l'aide l'ordinateur en  lui demandant d'écrire les
mouvements effectués à chaque étape.

\end{frame}




\begin{frame}[fragile]

\caml

On commence par créer une fonction qui affichera le mouvement effectué~:

\begin{lstlisting}[caption={mouvement élémentaire}]
let mvt depart arrivee=
print_string
("Déplace un disque de la tige "^départ^" vers la tige "^arrivée);
print_newline();;
\end{lstlisting}
              
\end{frame}


\begin{frame}[fragile]
             \caml
              
Le programme proprement dit~:

\begin{lstlisting}[caption={résolution  récursive du problème  des tours
de Hanoï}]
let rec hanoi a b c= function
   | 0 -> ()  (*0 disque : on ne fait rien*)
   | n -> hanoi a c b (n-1); (*n-1 disques sont placés dans l'ordre de a vers b*)
          mvt a c; (*on déplace le disque restant en a vers c*)
          hanoi b a c (n-1) (*n-1 disques sont placés dans l'ordre de b vers c*);;
\end{lstlisting}

\end{frame}




\begin{frame}[fragile]
             \caml
              
Par exemple, dans le cas de 3 disques~:

\begin{lstlisting}
# hanoi "A" "B" "C" 3;;
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige A vers la tige B
Deplace un disque de la tige C vers la tige B
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige B vers la tige A
Deplace un disque de la tige B vers la tige C
Deplace un disque de la tige A vers la tige C
- : unit = ()
\end{lstlisting}
\end{frame}



\subsubsection{Non pas pourquoi mais comment~:~version impérative}


\begin{frame}
  

Prenez un papier et  un crayon. Dessinez trois piquets A, C  et B et les
trois disques dans leur position initiale sur le plot A.

Déplacez alors les disques selon la méthode suivante~:

\begin{itemize}
\item  déplacez le  plus petit  disque vers  le plot  suivant  selon une
  permutation circulaire A-C-B-A ;
\item un seul des deux autres disques est déplaçable vers un seul piquet
  possible.
\end{itemize}

\end{frame}


\begin{frame}
  
Réitérez (en  informatique à l'aide de boucles...)  ce mécanisme jusqu'à
ce que tous les disques soient sur C dans la bonne position.

On voit donc bien ici comment ça  marche ; il est plus délicat de savoir
pourquoi on arrivera au résultat.

Le programme est lui-même  assez compliqué à écrire~:~vous trouverez une
version en \texttt{C} (235 lignes...) à cette adresse~:

\begin{center}
  \href{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}
\end{center}


\end{frame}




\end{document}

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