#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 (i > j) ? i : j; } /************************************************************************/ /* Retourne la plus grande valeur parmi i, j et k */ int max3(int i, int j, int k) { return max2(max2(i, j), k); } /************************************************************************/ /* Alloue dynamiquement la memoire permettant de stocker n disques. Retourne un pointeur vers l'espace alloue. */ int* creeSocle(int nbDisques) { int* s = malloc((nbDisques + 1)*sizeof(int)); if (s == NULL) exit(0); *s = 0; return s; } /************************************************************************/ /* Place nbDisques disques dans le socle s. */ void initSocle(int* s, int nbDisques) { int i; for(i = 1 ; i <= nbDisques ; i++) *(s + i) = nbDisques - i + 1; *s = nbDisques; } /************************************************************************/ /* Initialise les pointeurs de s et place nnDisques disques dans le premier socle. */ void creeSocles(int** s, int nbDisques) { *s = creeSocle(nbDisques); *(s + 1) = creeSocle(nbDisques); *(s + 2) = creeSocle(nbDisques); initSocle(*s, nbDisques); } /************************************************************************/ /* Affiche les 3 socles. */ void afficheSocles(int** s) { int max = max3(**s, **(s + 1), **(s + 2)); int i; for (i = max ; i > 0 ; i--) { if (**s >= i) printf("%3d ", *(*s + i)); else printf(" "); if (**(s + 1) >= i) printf("%3d ", *(*(s+1) + i)); else printf(" "); if (**(s + 2) >= i) printf("%3d ", *(*(s+2) + i)); printf("\n"); } printf("------------\n"); } /************************************************************************/ /* Libere les trois tableaux alloues dynamiquement. */ void libereSocles(int** s) { int i; for(i = 0 ; i < 3 ; i++) free(*(s + i)); } /************************************************************************/ /* Deplace le disque se trouvant au sommet du socle socleSource sur le sommet du socle socleDestination. */ void deplaceDisque(int* socleSource, int* socleDestination) { *(socleDestination + *socleDestination + 1) = *(socleSource + *socleSource); (*socleDestination)++; (*socleSource)--; } /************************************************************************/ /* 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) { if (n > 0) { deplaceDisques(n-1, s, sFrom, sTo, sVia); deplaceDisque(*(s + sFrom), *(s + sTo)); afficheSocles(s); deplaceDisques(n-1, s, sVia, sFrom, 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; }