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

[CHAPTER]

با سلام خدمت دوستان عزیز
مسئله برج هانوی رو که همه می شناسید و روش کار با 3 میله رو همه می دونند. اما حالا مشکل من اینه که برای k>3 روش کار چه جوری میشه.یعنی انتقال n دیسک به میله k ام چه جوری میشه. من فقط روال کار رو می خواستم اگر رابطه بازگشتی هم پیدا کردید چه بهتر.
ممنون از لطف همه

[saber57]

از جزییات برنامه نویسی چیزی نمیدونم
اول به سایت برنامه نویس سر بزنید که مربوط برنامه نویسی هست . این لینکو ببینید:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

توضیح ابتدایی در مورد برج هانوی با سه میله :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای 3 دیسک:

1: A---> C
2: A---->B
1: C----> B
-----
3:A---- C
-----
1: B----> A
2 : B----> C
1 : A---- >C
************************************************** ******
برای 4 دیسک(سه میله)

1: A---- > B
2: A----> C
1: B----> C
3: A----> B
1: C----> A
2: C----> B
1: A----> B
---------------
4: A----> C
---------------
1: B----> C
2: B----> A
1: C----> A
3:B----> C
1: A----> B
2: A----> C
1: B----> C

میبینیم که هر حالت 2 به توان n منهای 1 حرکت داره .ضمنا در روش بالا میله C مقصد هست.طبق روشهای بالا برای انتقال اولین دیسک بزرگ لازمه که n-1 دیسک کوچکتر ابتدا به میله کمکی B منتقل بشن و بعد دیسک بزرگ از میله مبدا به مقصد انتقال پیدا کنه و الی آخر .....

باور کنید سختی مساله برج هانوی به همین تعداد کم میله هاشه
حالا هر چی میله ها زیادتر بشه راحتتریم . یک مثال :

7 دیسک و 4 میله داریم :

1: A---D
2: A--C
3: A---B
2: C---B
1: D---B
تا اینجا سه دیسک 1و2 و 3 به میله B منتقل شدندالبته دیسک چینی به ترتیب شماره از آخرین میله شروع شد
********************************************
4: A---C
5: A---D
4: C---D
حالا دیسکای 4 و 5 هم به میله D منتقل کردیم .جالبه ایندفعه بترتیب شماره از میله سوم یاC شروع کردیم یعنی 4 بجای قرار گرفتن در D در C قرار گرفت .
******************************************
6: A---C
4: D---A
5: D---C
4: A---C
پس دیسکای 4 ، 5 و 6 در میله 3 یا C قرار گرفتند .حالا دیسک 7 میاد و در میله مقصد قرار میگیره :
******************************************
7: A---D
4: C---D
5: C---A
4: D---A
6: C---D
4: A---C
5: A---D
4: C---D
تا اینجا دیسکهای 4 و 5 و 6 و 7 در میله D قرار گرفتند

بقیه دیسکها هم به همین ترتیب جای گرفتند .

الگوریتم در حالت کلی:

در این مسایل ، کلا k میله داریم که بجز میله اول که n دیسک روش قرار داره ، k-1 تا دیگه خالیه . روش کار بدین صورت هست :

باید کاری کنیم که دیسک آخری در میله آخر قرار بگیره پس بر روی میله ها به تعداد خارج قسمت n-1 بر k-2 ، دیسک قرار میدیم . اگه باقیمانده داشت به ترتیب یکی یکی ، از میله دوم شروع میکنیم به اضافه کردن دیسک
مثلا 7 دیسک و 4 میله به تعداد خارج قسمت 6 بر 2 یعنی 3 تا 3 تا تقسیم میکنیم . همونطور که دیدیم بعد از کمی تقسیم بندی ، میله 2 (اولین میله بعد از 1) سه تا دیسک (1و2و3 ) و میله 3 دیسکای 4و5و6 قرار گرفتند و ......

اگه 31 دیسک و 6میله بود، خارج قسمت 30 بر 4 برابر 7 و باقیمانده 2 میشد بنابراین میله های 2،3، هر کدام 8 دیسک و میله های 4و8 به تعداد 7 دیسک قرار میگرفت

یعنی جابجاییها طوری باید باشه که میله 2 :
میله2: دیسکهای 8و7و6و5و............و1
میله 3 : دیسکهای 16و15و14و....و9

به همین ترتیب الی آخر

اگه نقصانی داشت دوستان برنامه نویس! یاری کنند

[CHAPTER]

اگه نقصانی داشت دوستان برنامه نویس! یاری کنند

سلام آقا صابر باز شما به داد ما رسیدی
این چه حرفیه ما خیلی مخلصیم
ممون از لطفت مثل همیشه مفصل توضیح دادی