Tour de Hanoi

Bonjour à tous !
J'ai un problème avec un exercice bien connu en C : le jeu des tours de Hanoi.
Le principe est simple :
On dispose de trois socles. L'un de ces socles contient n anneaux, rangés par taille décroissante. Le but est de déplacer ces n anneaux du premier socle (socle A) sur le socle C, en s'aidant d'un socle intermédiaire noté B. Les règles de déplacement des anneaux sont simples : un seul anneau peut-être déplacé à la fois, et un anneau peut être posé que sur un autre anneau de plus grande taille.

Dans mon exercice, les socles sont matérialisés par des piles. Voici la structure :

Code:

---

1 2 3 4 5 6

typedef struct maillon { int v; struct maillon* suiv; }Maillon;   typedef Maillon* Pile;

---

On commence par remplir la pile A avec le nombre d'anneaux voulu :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pile Remplir (void) { int n,i; Pile A; A=pilenouv();   printf("Entrez le nombre d\'anneaux : "); scanf("%d",&n);   for (i=1;i<=n;i++) { A=empiler(A,i); }   return A; }

---

Ensuite, on a une fonction nommé Hanoi, qui utilise la récursivité pour résoudre le problème :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

void Hanoi (Pile A, Pile B, Pile C, int n) { if (n==1) { C=empiler(C,tete(A)); A=depiler(A); }   else { Hanoi (A,C,B,n-1);   B=empiler(B,tete(A)); A=depiler(A);   Hanoi (B,A,C,n-1); } }

---

Voici la main :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int main (void) {   Pile A,B,C;   A=Remplir(); B=pilenouv(); C=pilenouv();   Hanoi(A,B,C,longueur(A));   return 0;   }

---

Et si besoin est, voici la liste des fonctions appelés par les fonctions Hanoi et Remplir :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

Pile pilenouv (void) { return NULL; }   Pile empiler (Pile p, int data) { Pile sauv=p;   p=(Pile)malloc(sizeof(Maillon)); if (p==NULL) {printf("Erreur d\'allocation memoire ... !\n");exit(1);}   p->v=data; p->suiv=sauv;   return p; }   Pile depiler (Pile p) { Pile tete=p;   if (vide(p)) {printf("On ne peut depiler une pile vide ... \n");exit(1);}   p=p->suiv; free(tete); return p; }   int longueur (Pile p) { int l=0;   while (p!=NULL) { p=p->suiv; ++l; }   return l; }

---

Premièrement, je ne suis pas du tout sûr que cet algorithme soit bon. Il compile sans soucis, mais je sais pas comment m'y prendre pour qu'à l'écran, on obtienne les différentes étapes. Par exemples, pour n=2, je voudrais que le programme affiche :

Operation 1 : je prends l'anneau de A et je le mets sur B
Operation 2 : je prends l'anneau de A et je le mets sur C
Opération 3 : je prends l'anneau de B et je le mets sur C
FIN.

Quelqu'un peut-il m'aider à finir ce programme ?

Merci d'avance, et n'hésitez pas à demander plus de détails !

Citation:

---

Envoyé par Stonkeep

Bonjour à tous !
J'ai un problème avec un exercice bien connu en C : le jeu des tours de Hanoi.

---

Bonjour. Voici quelques remarques sur la forme et le fond :

Citation:

---

Code:

---

1 2 3 4 5 6

typedef struct maillon { int v; struct maillon* suiv; }Maillon;   typedef Maillon* Pile;

---

---

C'est correct en soi mais ce n'est que très rarement une bonne idée de masquer le pointeur sur « Maillon » dans un nouveau nom de type. Cependant, beaucoup de cours sont construits comme ça. Je suppose que c'est imposé par ton prof'.

Citation:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pile Remplir (void) { int n,i; Pile A; A=pilenouv();   printf("Entrez le nombre d\'anneaux : "); scanf("%d",&n);   for (i=1;i<=n;i++) { A=empiler(A,i); }   return A; }

---

---

Attention : en incrémentant i à chaque tour de boucle, tu empiles chaque disque sur un disque plus petit que lui ! Il faut partir de n et décrémenter tant que i est supérieure à zéro.

D'autre part, il aurait été plus propre de passer la hauteur n de ta pile en tant qu'argument de ta fonction, et laisser le soin à ta fonction main d'interroger l'utilisateur avec scanf.

Citation:

---

Ensuite, on a une fonction nommé Hanoi, qui utilise la récursivité pour résoudre le problème :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

...   else { Hanoi (A,C,B,n-1);   B=empiler(B,tete(A)); A=depiler(A);   Hanoi (B,A,C,n-1); } }

---

---

Ça, en revanche, c'est incorrect. Les opérations d'empilement et de dépilement doivent être identiques à celles du cas précédent. À dire vrai, ce doit en fait être les mêmes ! En général, ce sont les appels à Hanoi() que l'on fait précéder de « if (n>1) ... ».

L'idée générale étant que lorsque l'on a plus d'un disque à déplacer, on déplace n-1 disques sur le piquet intermédaire, on déplace manuellement le dernier disque sur le piquet d'arrivée, et on rebouge les n-1 disques du piquet intermédiaire vers le piquet d'arrivée. Et comme bouger n-1 disques, c'est exactement le même problème que d'en déplacer n, et bien on rappelle deux fois la fonction hanoi() pour traiter le même problème avec un disque de moins.

Il n'y a donc pas de raison de faire deux cas parfaitement distincts lorsque n vaut 1 et lorsqu'elle est supérieure.

Citation:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Pile empiler (Pile p, int data) { Pile sauv=p;   p=(Pile)malloc(sizeof(Maillon)); if (p==NULL) {printf("Erreur d\'allocation memoire ... !\n");exit(1);}   p->v=data; p->suiv=sauv;   return p; }

---

---

Pourquoi sauver p dans une variable locale pour l'utiliser ensuite comme une autre variable locale ? Autant directement utiliser celle que tu as déclarée.

Citation:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Pile depiler (Pile p) { Pile tete=p;   if (vide(p)) {printf("On ne peut depiler une pile vide ... \n");exit(1);}   p=p->suiv; free(tete); return p; }

---

---

Ok, je comprends mieux pourquoi tu utilises tete() : depile renvoie la nouvelle pile. Ok.

Citation:

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

int longueur (Pile p) { int l=0;   while (p!=NULL) { p=p->suiv; ++l; }   return l; }

---

---

Citation:

---

Premièrement, je ne suis pas du tout sûr que cet algorithme soit bon. Il compile sans soucis, mais je sais pas comment m'y prendre pour qu'à l'écran, on obtienne les différentes étapes. Par exemples, pour n=2, je voudrais que le programme affiche :

Operation 1 : je prends l'anneau de A et je le mets sur B
Operation 2 : je prends l'anneau de A et je le mets sur C
Opération 3 : je prends l'anneau de B et je le mets sur C
FIN.

---

Comme dit plus haut, en principe, ton opération de déplacement ne doit avoir lieu qu'à un seul endroit. Il suffit de rajouter un printf() à cet endroit précis pour suivre automatiquement le déroulement de la séquence.

Bon courage.

Bonjour,
L'expérience m'a montré que manipuler une liste chaînée directement via un pointeur de maillon n'était pas une bonne idée. Je conseillerais plutôt ceci:

Code:

---

1 2 3 4 5 6 7 8

typedef struct maillon { int v; struct maillon* suiv; } Maillon;   typedef struct pile { struct maillon* sommet; } Pile;

---

Ensuite, toutes tes fonctions qui touchent à la pile prennent un pointeur Pile* en paramètre. :)