[C] explication Tour Hanoï récursive
Tony
-
Char Snipeur Messages postés 10112 Date d'inscription Statut Contributeur Dernière intervention -
Char Snipeur Messages postés 10112 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
il y a quelqu'un qui peut m'expliquer le principe de la tour d'hanoï ?
voici le programme , et merci !
#include<stdio.h>
#include<conio.h>
void tourhanoi(int n,char depart,char base,
char intermediaire,long unsigned int *occur);
int main()
{
int n,i;
long unsigned int occur=0;
printf("Entrez le nombre de disques : ");
scanf("%d",&n);
tourhanoi(n,'1','2','3',&occur);
printf("%ld déplacements\n",occur);
getch();
}
void tourhanoi(int n,char depart,char base,
char intermediaire,long unsigned int *occur){
if(n>0){
++*occur;printf("lalal %d",n);
tourhanoi(n-1,depart,intermediaire,base,occur);
printf("hah");printf("%c -> %c\n",depart,base);
tourhanoi(n-1,intermediaire,base,depart,occur);
}
}
il y a quelqu'un qui peut m'expliquer le principe de la tour d'hanoï ?
voici le programme , et merci !
#include<stdio.h>
#include<conio.h>
void tourhanoi(int n,char depart,char base,
char intermediaire,long unsigned int *occur);
int main()
{
int n,i;
long unsigned int occur=0;
printf("Entrez le nombre de disques : ");
scanf("%d",&n);
tourhanoi(n,'1','2','3',&occur);
printf("%ld déplacements\n",occur);
getch();
}
void tourhanoi(int n,char depart,char base,
char intermediaire,long unsigned int *occur){
if(n>0){
++*occur;printf("lalal %d",n);
tourhanoi(n-1,depart,intermediaire,base,occur);
printf("hah");printf("%c -> %c\n",depart,base);
tourhanoi(n-1,intermediaire,base,depart,occur);
}
}
4 réponses
-
Le but est de deplacer une pile de disque (qui vont du plus grand au plus petit) d'un endroit a un autre.
Voici une animation pour t'aider a comprendre:
https://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif
On deplace donc les disques au fur et a mesure pour depiler la pile initiale, afin d'empiler une autre pile ailleurs. (bien entendu, un plus grand disque ne peut pas aller sur un plus petit disque). -
-
-
L'algorithme est assez compliqué.
Il est récursif. Pour le comprendre part de n=1.
puis avec n=2.
et tu intervertit à chaque fois la base et l'intermédiaire. et l'intermédiare et la base. Tu fait toujours le mouvement depart ->base, mais tu interverti les différents tas.
