توضیح الگوریتم برج هانوی

[mahtab_18]

سلام

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

آنچه آینده بود حال است و آنچه که حال است گذشته می شود ، پس چرا نگرانی ؟

[mzjahromi]

ببینید من فقط یه توضیح ساده میتونم بدهم امیدوارم کمکتان کند.
فرض کنید ما سه میله A , B , C داریم و 10 حلقه درون A وجود دارد که میخواهیم آنها را به B ببریم در این راستا میتوانیم از حلقه C نیز کمک بگیریم.(با شرایطی که برای تغییر مکان حلقه ها وجود دارد). ما باید به طریقی 9 حلقه از A را روی C قرار دهیم تا بتوانیم حلقه دهم را از A به B منتقل کنیم. و سپس باید همین 9 حلقه را از C به B منتقل کنیم
حال صورت مساله عوض شد.
ما سه میله A , B , C داریم و 9 حلقه درون A وجود دارد که میخواهیم آنها را به C ببریم در این راستا میتوانیم از حلقه B نیز کمک بگیریم.(با شرایطی که برای تغییر مکان حلقه ها وجود دارد). ما باید به طریقی 8 حلقه از A را روی B قرار دهیم تا بتوانیم حلقه دهم را از A به C منتقل کنیم. و سپس باید همین 9 حلقه را از B به C منتقل کنیم
و الی آخر
در انتها به جائی می رسیم که تنها کافی است یک حلقه را جابجا کنیم که این یک حلقه نیز به سادگی جابجا پذیر است
بطور خلاصه عملکرد الگوریتم هانوی به شکل زیر است
1- تعداد N-1 حلقه را از A به C منتقل کن با کمک B
2-حلقه N را از A به B منتقل کن
3- تعداد N-1 حلقه را از C به B منتقل کن با کمک C

[mina.m]

:: الگوریتم برج هانوی
برج هانوی , معمایی است که از سه میله و N دیسک با اندازه های متفاوت . فرض شود که اگر دیسکی روی یک میله باشد , فقط دیسکی که قطر آن کوچکتر است می تواند بالای آن قرار گیرد مسئله چنین است که هر بار فقط یک دیسک انتقال یابد .
را حل : این مسئله با استفاده از یک الگوریتم باز گشتی حل می شود .
-اگر فقط یک دیسک باشد آنگاه آن را به میله مورد نظر انتقال می دهیم .
-اگر n > 1 باشد ; برای این کار n-1 دیسک بالای میله 1 را به میله 2 انتقال می دهیم . حالا دیسک پایینی میله 1 را ثابت باقی می ماند . حال دیسک باقیمانده در در میله 1 را به میله 3 منتقل میکنیم . سرانجام بار دیگر بصورت بازگشتی الگوریتم را فرا خانده تا n - 1 دیسک میله دو را به 3 منتقل کند .
اکنون موفق شدیم n دیسک را از میله 1 به 3 منقل کنیم



: الگوریتم
/*
Algorithmic solution is as follows

1) if TopN==1, move the single disc from A to C and stop.
2) Move the top n-1 discs from A to B, using C as Inter.
3) Move the remaining disc from A to C.
4) Move the n-1 discs from B to C, using A as destination(dest).
* /
اگر کدش را هم خواستی بگو تا برایت بنویسم
با تشکر . مینا

[mahtab_18]

خیلی ممنون از جوابهاتون
ولی باز هم جواب منو ندادین من فقط می خواهم به صورت دستی خط به خط برنامه بازگشتی برج هانوی را برایم حل کنید چون من با برنامه بازگشتی هانوی مشکل دارم

آنچه آینده بود حال است و آنچه که حال است گذشته می شود ، پس چرا نگرانی ؟

[mina.m]

پس برنامه میخواهی؟ بله
:
#include <stdio.h>
#include <conio.h>
void tower(int,char,char,char); /*prototype*/
int main()
{
int ndisk;
clrscr();
printf("\n Enter number of disks <<<::: ");
scanf("%d",&ndisk);
tower(ndisk,'A','B','C'); /*Calling Function*/
getch();
return 0;
}
/* End of program */

/********************************************/

// src = Source | aux = Auxiliry | dest = Destination
void tower(int topN, char src,char aux,char dest)
{
if(topN == 1)
{
printf("\n Disk 1 from %c to %c ",src,dest);
}
else
{
tower(topN-1,src,dest,aux); //src to aux
printf("\n Disk %d from %c to %c ",topN,src,dest);
tower(topN-1,aux,src,dest); //aux to dest
}

}

این هم برنامه بازگشتی به زبان ++C
امیدوارم بیشتر تلاش کنی و موف باشی
با تشکر . مینا

[mahtab_18]

من از اول گفتم که برنامه را دارم و برنامه نمی خواهم . بگذارید توضیح بیشتری بدم ما وقتی سر کلاس برنامه ای رو نمی فهمیم اساتید جدولی می کشند و سیر تغییر متغیرها را درون جدول نشان می دهند که من هم همان جدول را می خواهم

آنچه آینده بود حال است و آنچه که حال است گذشته می شود ، پس چرا نگرانی ؟

[Mehrafrooz]

شما منظورتون Trace کردن برنامس ؟

[mzjahromi]

من از اول گفتم که برنامه را دارم و برنامه نمی خواهم . بگذارید توضیح بیشتری بدم ما وقتی سر کلاس برنامه ای رو نمی فهمیم اساتید جدولی می کشند و سیر تغییر متغیرها را درون جدول نشان می دهند که من هم همان جدول را می خواهم

آنچه آینده بود حال است و آنچه که حال است گذشته می شود ، پس چرا نگرانی ؟
اون توضیحی که من دادم شرحی از Trace برنامه بود . باور کنید اینجا دیگه نمیشه دقیقتر توضیح داد. یخورده هم خودتون باید توضیحات رو با برنامه منطبق کنید.

[mahtab_18]

خیلی ممنون از جوابهاتون سعی می کنم با کنار هم گذاشتن جوابها به نتیجه برسم

[Mehrafrooz]

ببینید خلاصش اینه :
یه جدول می کشید که هر ستون جدول مشخص کننده یکی از متغییر هایی هست که تو برنامه استفاده کردید . بعد از اول برنامه شروع می کنید یعنی خودتون رو می گذارید جای کامپیوتر . خط به خط جلو می رید و نتایج رو تو جدول می نویسد تا به آخر . اگر وسطهای راه دیدید که درست جواب نمیده یعنی اینکه برنامتون ایراد داره . چون کامپیوتر هم مطمئنا به اونجا که برسه ایراد خواهد گرفت .
فقط کافیه خودتون رو بذارید جای کامپیوتر . کمی هم تمرین کنید راه می افتید . مهم اینه که الگوریتمی رو که نوشته اید خط به خط دنبال کنید .

[skyline1985]

سلام
من الگوریتم برج هانوی رابرای سه میله به زبان c++ میخواستنم