Exercice 10 - Tours de Hanoï

On dispose de $n$ disques numérotés de $1$ à $n$. Les disques peuvent être empilés sur des socles à partir du moment où tout disque repose sur un disque de numéro plus élevé. On dispose de trois socles $S_1$, $S_2$ et $S_3$, les $n$ disques sont empilés sur le socle de gauche $S_1$, ceux du milieu et de droite $S_2$ et $S_3$ sont vides. Le but est de déplacer toute la pile de disques sur le socle de droite, sachant qu'on ne peut déplacer les disques que un par un, et qu'il ne faut qu'à aucun moment, un disque numéroté $k$ se trouve sur un disque numéroté $m$ avec $m < k$ (i.e un disque plus petit). Par exemple, si $n=3$, on a

  1
  2
  3
------------
  2
  3       1
------------
  3   2   1
------------
      1
  3   2
------------
      1
      2   3
------------
  1   2   3
------------
          2
  1       3
------------
          1
          2
          3
------------

On dispose d'un sous-programme $deplaceDisque(S_i, S_j)$ qui enlève le disque se trouvant au sommet de la pile $S_i$ et la place au sommet de la pile $S_j$.

1. Trouver un algorithme récursif $deplaceDisques(n, S_{from}, S_{via}, S_{to})$ permettant de déplacer $n$ disques du socle $S_{from}$ au socle $S_{to}$ en utilisant $S_{via}$ comme socle intermédiaire.
2. Codez en C un programme qui affiche chaque étape du déplacement des $n$ disques,

Fichier source à compléter :

hanoiVide.c

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

/*
  Nous representerons les 3 socles par un tableau de 3 pointeurs.
  Chaque pointeur, de type int*, aura pour cible un tableau 
  alloue dynamiquement qui contiendra les disques. La premiere case
  contiendra le nombre de disques poses sur le socle, et les cases
  suivantes contiendront les disques, en commencant par celui qui 
  est en bas de la pile.
  
*/

/************************************************************************/

/*
  Retourne la plus grande valeur parmi i et j
*/

int max2(int i, int j)
{
  return 0;
}

/************************************************************************/

/*
  Retourne la plus grande valeur parmi i, j et k
*/

int max3(int i, int j, int k)
{
  return 0;
}

/************************************************************************/

/*
  Alloue dynamiquement la memoire permettant de stocker n disques.
  Retourne un pointeur vers l'espace alloue.
*/

int* creeSocle(int nbDisques)
{
  return NULL;
}

/************************************************************************/

/*
  Place nbDisques disques dans le socle s.
*/

void initSocle(int* s, int nbDisques)
{
}

/************************************************************************/

/*
  Initialise les pointeurs de s et place nnDisques disques
  dans le premier socle.
*/

void creeSocles(int** s, int nbDisques)
{
}

/************************************************************************/

/*
  Affiche les 3 socles.
*/

void afficheSocles(int** s)
{
}

/************************************************************************/

/*
  Libere les trois tableaux alloues dynamiquement.
*/

void libereSocles(int** s)
{
}

/************************************************************************/

/*
  Deplace le disque se trouvant au sommet du socle socleSource
  sur le sommet du socle socleDestination.
*/

void deplaceDisque(int* socleSource, int* socleDestination)
{
}

/************************************************************************/

/*
  Deplace n disques du socle sFrom vers le socle sTo en utilisant
  sVia comme espace de stockage intermediaire. Affiche toutes les 
  etapes.
*/

void deplaceDisques(int n, int** s, int sFrom, int sVia, int sTo)
{
}

/************************************************************************/

/*
  Teste le deplacement de trois disques.
*/

int main()
{
  int* s[3];
  int nbDisques = 3;
  creeSocles(s, nbDisques);
  afficheSocles(s);  
  deplaceDisques(nbDisques, s, 0, 1, 2);
  libereSocles(s);
  return 0;
}

1. Que remarquez-vous lorsque l'on prend des grandes valeurs de $n$.
2. Déterminer une relation de récurrence permettant de dénombrer le nombre d'étapes nécessaires pour déplacer $n$ disques. Résolvez-là.
3. Est-il envisageable de déplacer $100$ disques en un temps raisonnable ?