الگوریتم برج هانوی و پیاده سازی آن در c

[آبجی]

برج هانوی معمایی است که از 3 میله و N حلقه یا دیسک با اندازه های متفاوت . مطابق شکل زیر می خواهیم تمام N حلقه را از میله اول به یک میله دیگر انتقال دهیم. از میله سوم می توان به عنوان کمکی استفاده کرد



حل این معما دو شرط دارد:
1- در هر انتقال تنها یک حلقه را می توان انتقال داد.
2- در هیچ کدام از میله ها هیچ وقت نمی توان یک حلقه بزرگتر را بر روی یک حلقه کوچکتر قرار داد.


راه حل :

این مسئله با استفاده از الگوریتم بازگشتی حل می شود.

اگر فقط یک دیسک باشد آنگاه آن را به میله مورد نظر انتقال می دهیم.

اگر n>1 باشد برای این کار n-1 دیسک بالای میله 1 را به میله 2 انتقال می دهیم . حالا دیسک پایینی میله 1 را ثابت باقی می ماند. حال دیسک باقی مانده در دیسک 1 را به میله 1 انتقال می دهیم . سرانجام بار دیگر به صورت بازگشتی الگوریتم را فراخوانده تاn-1 دیسک میله 2 را به 3 منتقل کند .
اکنون موفق شدیم n دیسک را از میله 1 به 3 منتقل کنیم .

کد:


#include<stdio.h>

#include<conio.h>

void tower(int,char,char,char);
int main()
{
int ndisk;
clrscr();
cout<<"\nEnter number of disks: ";
cin>>ndisk;
tower(ndisk,'A','B','C');
getch();
return 0;
}
/**********************************/
// scr = Source , aux = Auxility , dest = Destination
void tower (int topN,char scr,char aux,char dest)
{
if(topN==1)
{
cout<<"\nDisk 1 from"<<src<<" to"<<dest;
}
else {
tower(topN-1,scr,dest,aux); // scr to aux
cout<<"\nDisk"<<topN<<"from"<<scr<<"to"<<dest;
tower(topN-1,aux,scr,dest); // aux to dest
}
}