مسئله کلاسیک برج هانوی به صورت زیر است :
سه برج (میله) و n دیسک باقطر های متفاوت روی اولین برج داریم .
دیسک ها به ترتیب نزولی روی اولین برج از پایین به بالا چیده شده اند .کل دیسک ها را از برج اول به برج سوم منتقل کنید.به گونه ای که دقیقا همان ترکیب دیسک ها در برج اول در برج سوم پدید آید .
البته در این عملیات دو محدودیت اصلی وجود دارد .
الف :در هر بار انتقال فقط یک دیسک می نواند جا به جا شود .
ب : در هیچ مر حله ای م=نمی توان یک دیسک کوچکتر را روی دیسک بزرگ تر قرار داد.در این عملیات می توان از یک میله کمکی نیز وضعیت او لیه و نهایی باید به صورت زیر باشد :
n=2 مثلا برا ی وضعیت اولیه وضعیت نهایی اگر n=1 باشد مسئله خیلی ساده بود و تن ها با یک جا به جایی (بون کمک میله B )حل میشد .
یع نی فقط کافی بود که دیسک از میله A به میله C اتقال داده بشه .
اگر N=2 باشد به 3 جا به جایی مطابق شکل زیر نیاز داریم : B TO C A TO C A TO B وضعیت اول و اگر N=3 باشد به 7 جا به جایی مطابق روش زیر نیاز است : C TO B A TO B A TO C وضع اولیه A TO C B TO C B TO A A TO C همان طور که مشاهده می شود با افزایش N پیچیدگی مسئله بیشتر شده و مقدار جابه جایی ها نیز افزایش میابد .
در حالت کلی اثبات می شود برای حل مسئله برج هانوی با N دیسک 2^N-1 جا به جایی نیاز است .یعنی پیچیدگی مسئله به صورت نمایی زیاد می شود و برای N های بزرگ حل مسئله به کمک کامپیوتر ممکن است ساعت ها طول بکشد .
جالبی مسئله هانوی این است که به زیبایی قدرت روش بازگشتی را نشان می دهد .
یعنی این که برای حل مسائل پیچیده کا فی است یکبیا باز گشتی برای آن پیدا کنیم .
آن گاه کامپیوتر بدون آن که ما را در گیر عملیات پیچیده سازد خود به خود مسئله را حل می کند.
این جملات بازشگتی برای حالت کلی N دیسک به صورت زیر هستند : ابتدا N-1 دیسک را از میله مبدا (A) به میله ی کمکی (B) انتقال بده .
تنها دیسک باقی مانده در میله ی (A) که بزرگ ترین دیسک است را به میله ی مقصد یعنی C انتقال بده .
N-1 دیسک موجود در میله کمکی B را به میله C انتقال بده .
با انجام مراحل 1 تا 3 مسئله حالت N ام تبدیل به مسئله حالت N-1 می شود .
بدین ترتیب با تکرار این مراحل مرتبا مسئله کوچک می شود تا هنگامی که به حالت N=1 برسد .
برای این حالتخاص نیز مسئله به راحتیبا انتقال آن دیسک از میله مبدا به میله مقصد حل می شود .
با تجه به الگوریتم بالا : معادل پروسیجر آن در زبان C به صورت ساده زیر می باشد : VOID TOWER (int n , char a,char b ,char c) { If (n==1)printf(“move a disc from %c to %\n”,a,c); Else { Tower(n-1,a,c,b); Printf(“move a disc from %c to %c\n”,a,c); Tower(n-1,b,a,c); } } برنامه به صورت کامل به زبان c در زیر : ///////////////////////////////////// // programing:saber mirshahi // ///////////////////////////////////// #include #include #include int n,i,x,j,a,b,c,f,au[11],bu[11],cu[11],k; void mov(int n,int mabda,int maghsad,int o) { if (n>0) { mov(n-1,mabda,o,maghsad); getch(); sound(1800); delay(50); nosound(); if (mabda==1) {x=16;k=a;f=au[a];a=a-1;} if (mabda==2) {x=33;k=b;f=bu[b];b=b-1;} if (mabda==3) {x=53;k=c;f=cu[c];c=c-1;} gotoxy(x,20-k);printf(" "); if (maghsad==1) {x=16;a=a+1;k=a;au[a]=f;} if (maghsad==2) {x=33;b=b+1;k=b;bu[b]=f;} if (maghsad==3) {x=53;c=c+1;k=c;cu[c]=f;} gotoxy(x,20-k); for (i=1;i cprintf("ـ"); mov(n-1,o,maghsad,mabda); } } main() { clrscr(); printf("smirshahi\n\n"); printf("tedad halghe scanf("%d",&n); a=n; for(i=0;i au[i+1]=n-i; gotoxy(16,20);printf("-----------------------------------------------");gotoxy(16,21);printf("A");gotoxy(33,21);printf("B");gotoxy(53,21);printf("C"); for (i=1;i for (j=1;j {gotoxy(16-i+n,20-j);textcolor(10);cprintf("ـ");} mov(n,1,3,2); gotoxy(37,25); printf("THE END"); for(i=1;i sound(2650); delay(40); sound(1455); delay(40); sound(2530); delay(40); nosound();} getch(); }