L’agorithme se trouve dans un des comm dessous.
Il est excessivement simple et très court par rapport à d’autres façons de résoudre ce problème. De plus je peux jouer sur le nombre de disque, la base sur laquelle reconstruire la pyramide (1,2ou3), et enfin décider si l’on débute ou non avec une pyramide ou des disques étalés au hasard (réponse par ‘o’ ou ‘n’ de Oui ou Non à ne pas confondre avec n=nbr de disque)
x[i] représente la position du disque i (1,2ou3). Le nombre de disque est n que je rentre au début. y[i] représente sa hauteur (1 tout en bas, n au sommet). Le disque 1 est le plus large et le n le plus petit.
b[i] représente la destination 1,2ou3 du disque i.
h[i] représente la hauteur de chacune des 3 bases i (où i va donc de 1 à 3)
v[i] représente la valeur du disque supérieur pour chaque base.
i,j,l sont les indices dans mes boucles.
p représente la base sur laquelle reconstruire, le symbole ^^ se trouve sous elle pour l’indiquer. Je rentre cette valeur au début.
k permet de tester si tous les disques sont au bon endroit.
Principe :
Je reste dans la boucle principale tant que k=0, or on voit à la fin que si un disque n’est pas à la bonne place k reçoit la valeur 0.
A l’intérieur de cette boucle l’indice l va de 1 à n, parcourant ainsi chaque disque.
Mais avant la 1ère chose est de recalculer la hauteur et la valeur du disque supérieur de chaque pilier : h[i] et v[i], cela à chaque fois car au sein de cette boucle plusieurs déplacements peuvent s’effectuer. Cette partie ne sert qu’à savoir si un déplacement est possible.
Vient maintenant le fameux algorithme de déplacement qui s’applique sur le disque i en cours:
– si la position du disque est à sa destination (x[l]==b[l]) alors le disque suivant (l+1) reçoit la même destination.
– sinon, si le disque est déplaçable (cad si c’est le dernier de pile et s’il est plus petit (mais en fait indice plus grand) que le disque de la pile destination) alors il bouge. Sinon alors la destination du prochain prend la valeur restante parmi les 3 piliers qui n’est ni la valeur actuelle du disque(x[i]), ni sa destination(b[i]) et elle vaut:b[l+1]=6-x[l]-b[l]). Ce qui permettra alors par la suite au disque i de pouvoir aller vers b[i] puisque le disque i+1 sera à une 3ième place qui ne gênera pas le déplacement.
———————————————
– Il est logique que si un disque i est à sa destination, même une destination transitoire, le disque i+1 prenne la même destination puisqu’il faut toujours reconstruire une sous-pyramide au-dessus du disque en question, cela pour permettre au disque inférieur i-1 de pouvoir bouger vers sa destination.
– Il est aussi logique que si un disque n’est pas à sa destination alors la destination du disque supérieur i+1 sera la seule position qui ne soit ni la position actuelle du disque i, ni sa destination, afin justement de pouvoir déplacer le disque i.
– Il est aussi logique de commencer par regarder si le disque i est déplacable.
Nguồn:https://benxemientay.com/
Xem Thêm Bài Viết Khác:https://benxemientay.com/tour-du-lich/
#include<dos.h>
#include<string.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
main()
{
int i,j,l,p,n,k,x[12],y[12],b[12],h[12],v[12];
char a,c[9][16]={"==","====","======","========","==========","============",
"=============="};
clrscr();textmode(2);textcolor(1);textbackground(0);randomize();
gotoxy(13,3);printf("Nombre de disque: ");scanf("%d",&n);
gotoxy(13,4);printf("Pilier final(1…3):");scanf("%d",&p);
gotoxy(13,5);printf("Etat d‚but al‚atoire? ");a=getch();printf("%c",a);
_setcursortype(_NOCURSOR);h[1]=0;h[2]=0;h[3]=0;
/* ————– affichage des disques au depart ——————– */;
for(i=1;(i<=n);i++)
{
if (a=='n') {x[i]=1;y[i]=i;}
else {x[i]=random(3)+1;y[i]=h[x[i]]+1;h[x[i]]=y[i];}
gotoxy(x[i]*20-(n-i),20-y[i]);cprintf("%s",c[n-i]);
}
b[1]=p;k=0;gotoxy(p*20,21);printf("^^");
delay(3000);
for(;(k==0);)
{
for(l=1;(l<=n);l++)
{
/* ———— recalcul de h[1],h[2],h[3] et v[1],v[2],v[3] ———– */;
h[1]=0;h[2]=0;h[3]=0;v[1]=0;v[2]=0;v[3]=0;
for(i=1;(i<=3);i++)
{
for(j=1;(j<=n);j++) {if ((x[j]==i)&&(y[j]>h[i])) {h[i]=y[j];v[i]=j;} }
}
/* ————algorithme de deplacement sur le disque l ————- */;
if (x[l]==b[l]) {b[l+1]=b[l];}
else {
if ((y[l]==h[x[l]])&&(l>v[b[l]]))
{
textcolor(0);gotoxy(x[l]*20-(n-l),20-y[l]);cprintf("%s",c[n-l]);
x[l]=b[l];y[l]=h[x[l]]+1;b[l+1]=x[l];
textcolor(1);gotoxy(x[l]*20-(n-l),20-y[l]);cprintf("%s",c[n-l]);
delay(800);
}
else {b[l+1]=6-x[l]-b[l];}
}
}
for(k=99,i=1;(i<=n);i++) {if (x[i]!=p) {k=0;} }
}
delay(800);
}
Pour résumer simplement, la loi du mouvement pour chaque disque de 1 à n est :
– si le disque est à sa destination alors le disque suivant récupère la même destination.
– si le disque n'est pas à sa destination alors le disque suivant aura pour destination celle qui permettra le mouvement du 1er disque en question.
C'est ainsi que la machine se met en branle et que chaque disque s'actionne.
Le mouvement est juste initié en fixant la destination vers le pilier p(que je rentre au début) du 1er disque.
Moins