تعمیم مسئله برج های هانوی

[mansourehk]

با سلام به همه

من این تاپیک را در جاوا هم گذاشتم ولی متاسفانه کسی جوابمو نداد، لطفا راهنمایی کنید.
من 2 سئوال درباره ی برج های هانوی داشتم، دانستن الگوریتم برایم مهم است:
1- در مسئله برج های هانوی اگر انتقال فقط بین دو میله مجاور مجار باشد، رابطه بازگشتی برج های هانوی به چه صورت خواهد بود؟
2- در مسئله برج های هانوی اگر 2n دیسک وجود داشته باشد به طوریکه دیسکهای با شماره فرد درمیله 1 و زوج در میله 2 باشد، مسئله به چه صورت خواهد بود؟

لطفا هر چه زودتر مرا راهنمایی کنید...
با تشکر.

[ms_zandy]

آیاشرط رو بودن مهره کوچکتر برقرار است(شرط مساله اصلی)
چون در این صوت مساله حل نخواهد شد

[mansourehk]

آیاشرط رو بودن مهره کوچکتر برقرار است(شرط مساله اصلی)
چون در این صوت مساله حل نخواهد شد

بله شرط رو بودن مهره کوچکتر برقرار است، با این شرط هم مسئله حل شدنی است ولی تعداد moveها افزایش می یابند.
برای مثال: 3=n
دیسک 1 از برج 1 به 2
دیسک 1 از برج 2 به 3
دیسک 2 از برج 1 به 2
دیسک 1 از برج 3 به 2
دیسک 1 از برج 2 به 1
دیسک 2 از برج 2 به 3
دیسک 1 از برج 1 به 2
دیسک 1 از برج 2 به 3
دیسک 3 از برج 1 به 2
دیسک 1 از برج 3 به 2
دیسک 1 از برج 2 به 1
دیسک 2 از برج 3 به 2
دیسک 1 از برج 1 به 2
و به این شکل انتقال ها صورت می گبرد.

[SamaPic]

با سلام خدمت دوست عزيز.

مسئله ي شما كمي مشكل است ولي باز هم روي آن فكر ميكنم شايد توانستم حلش كنم.
ولي در پاسخ دوستمون كه C اين برنامه را خواسته بودن كد بصورت زير است:



#include <stdlib.h>
#include <conio.h>

#define COUNT 8

enum Bar{L,C,R};
struct disk{int Size,Color;};
struct stack{int i; disk *Disks;};
void transfer(int,Bar,Bar,Bar);
void init(); // Init bars
void MoveDisk(Bar from,Bar to);
void DrawBars();
stack Bars[3]={ {0,{0}} ,{0,{0}}, {0,{0}} };
int main(void)
{
textmode(C4350);
clrscr();
init();
DrawBars();
transfer(COUNT,L,R,C);
getch();
return 0;
}
char ConvertBarEnum2Char(Bar E){
char r=0;
switch (E) {
case L: r='L'; break;
case C: r='C'; break;
case R: r='R'; break;
}
return r;
}

void msg(Bar from,Bar to){
gotoxy(25,4);
textattr(15|16*0);
cprintf("Press anykey to move from %c to %c",ConvertBarEnum2Char(from),ConvertBarEnum2Char(to) );
gotoxy(37,5);
cprintf("Esc = Exit");
}

void transfer(int n,Bar from,Bar to,Bar temp){
if(n>0){
transfer(n-1,from,temp,to);
msg( from, to);
MoveDisk(from,to);
transfer(n-1,temp,to,from);
}
}
void init(){
Bars[L].Disks=new disk[COUNT];
for(int i=0;i<COUNT;i++){
Bars[L].Disks[i].Size=COUNT-i+1;
Bars[L].Disks[COUNT-i-1].Color=i+1;
}
Bars[L].i=COUNT-1;

Bars[R].Disks=new disk[COUNT];
for(i=0;i<COUNT;i++){
Bars[R].Disks[i].Size=0;
Bars[R].Disks[i].Color=0;
}
Bars[R].i=-1;

Bars[C].Disks=new disk[COUNT];
for(i=0;i<COUNT;i++){
Bars[C].Disks[i].Size=0;
Bars[C].Disks[i].Color=0;
}
Bars[C].i=-1;
}

void MoveDisk(Bar from,Bar to){
char kb=getch();
if(kb==27) exit(1);
Bars[to].Disks[++(Bars[to].i)]= Bars[from].Disks[(Bars[from].i)--];
clrscr();
DrawBars();
}
void me(){
char c;
for(int i=0;str[i];i++){
c=i%14+1;
if(c==1)c=2;
textattr(c|16);
cprintf("%c",str[i]);
}
}

void DrawBars(){
int n=0;
for(int j=0;j<3;j++){
for(int i=0;i<=Bars[j].i;i++){
gotoxy(1+j*27,24-i);
textattr(Bars[j].Disks[i].Color|16*0);
for(n=0;n<28 && n-13<Bars[j].Disks[i].Size ;n++){
if(n<14-Bars[j].Disks[i].Size)
cprintf("%s"," ");
else
cprintf("%s","ـ");
}
}
textattr(15|16*0);
for(n=0;n<15;n++){
gotoxy(1+j*27+13,n+10);
cprintf("%s","؛");
}
}
gotoxy(5,28);
me();
}

[pars.engineer]

سلام؛


برج هانوی گرافیکی با c کسی آماده داره؟



برنامه بازگشتي مساله برجهاي هانويبه زبان cيا++


دوستان اين كار درستي نيست كه در پستي كه موضوع ديگري دارد، از اين درخواستها داشته باشيد.
با يك جستجو حتما به جوابتان خواهيد رسيد.



ولي در پاسخ دوستمون كه C اين برنامه را خواسته بودن كد بصورت زير است:

به شما نيز پيشنهاد مي كنم كه جهت جلوگيري از تضعيع حق ديگران به سوالاتي به اين شكل پاسخ ندهيد.



1- در مسئله برج های هانوی اگر انتقال فقط بین دو میله مجاور مجار باشد، رابطه بازگشتی برج های هانوی به چه صورت خواهد بود؟

شما سوالتان را كمي گنگ مطرح نموده ايد. تصحيح شده آن به شرح زير است:
همان مسئله برج هانوي با اين شرط جديد كه انتقال مستقيم نداريم.(براي مثال نمي توان يك ديسك را به طور مستقيم از A به C منتقل كرد.).همچنين ميله مقصد B مي باشد.(يعني ديسكها ابتدا بايد به C منتقل شوند سپس به B).
متاسفانه وقت براي رسم اشكال ندارم.

توضيح الگوريتم بازگشتي:
ابتدا بايد n-1 ديسك را از ميله A (مبدا) به ميله B (مقصد) منتقل كرد، سپس بزرگترين ديسك را به ميله C (كمكي) منتقل كرد. بعد از آن n-1 ديسك را از ميله B به ميله A منتقل كرد و بعد از آن بزرگترين ديسك را از C به B منتقل نماييد. بدين ترتيب اولين ديسك در محل اصلي خود قرار مي گيرد براي n-1 ديسك باقي مانده نيز اين عمل را انجام دهيد.
راهنمايي: در برج هانوي معمولي در تابع بازگشتي بايد دوبار خود تابع فراخواني شود و پيچيدگي زماني آن نيز T(n)=O(n^2) مي باشد. ولي در اين مدل تغيير يافته بايد سه مرتبه تابع را فراخواني نمود و مي توان اثبات كرد كه داراي پيچيدگي زماني T(n)=O(n^3) مي باشد.



2- در مسئله برج های هانوی اگر 2n دیسک وجود داشته باشد به طوریکه دیسکهای با شماره فرد درمیله 1 و زوج در میله 2 باشد، مسئله به چه صورت خواهد بود؟

اين مسئله نيز به برج هانوي توسعه يافته معروف است(Extended Hanoi)
فرض مي كنيم n ديسك فرد در ميله A و n ديسك زوج در ميله B قرار دارند، حال بايد تعداد 2n ديسك را در ميله C قرار دهيم.
براي اين منظور بايد ابتدا n-1 ديسك از ميله A را با n-1 ديسك از ميله B را درون ميله C قرار دهيم.(به اين ترتيب C داراي 2n-2 ديسك مي باشد) حال ديسك شماره 2 در B و ديسك شماره1 در A قرار دارد. ديسك B را روي ديسك شماره 1 در A قرار مي دهيم،سپس 2n-2 ديسك را از ميله C به كمك ميله B به ميله A قرار مي دهيم.
حال ما همان مسئله معمولي برج هانوي را براي 2n ديسك داريم كه آن را نيز حل مي نماييم.

راهنمايي: براي حل اين مسئله بايد هم تابع بازگشتي هانوي توسعه يافته را داشته باشيم و هم تابع بازگشتي هانوي معمولي.
مي توان اثبات كرد كه پيچيدگي زماني اين مسئله T(n)=O(4^n) مي باشد.

موفق باشيد.

[pars.engineer]

با سلام به همه

من این تاپیک را در جاوا هم گذاشتم ولی متاسفانه کسی جوابمو نداد، لطفا راهنمایی کنید.
من 2 سئوال درباره ی برج های هانوی داشتم، دانستن الگوریتم برایم مهم است:
1- در مسئله برج های هانوی اگر انتقال فقط بین دو میله مجاور مجار باشد، رابطه بازگشتی برج های هانوی به چه صورت خواهد بود؟
2- در مسئله برج های هانوی اگر 2n دیسک وجود داشته باشد به طوریکه دیسکهای با شماره فرد درمیله 1 و زوج در میله 2 باشد، مسئله به چه صورت خواهد بود؟

لطفا هر چه زودتر مرا راهنمایی کنید...



من اصلا متوجه تاريخ ارسال اين تاپيك نشدم.(بيشتر از يك سال پيش).
ولي به هر حال براي كساني كه اطلاعاتي راجع به انواع مسائل هانوي بخواهند بد نيست.