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

واضح آرشیو وب فارسی:سایت ریسک: CHAPTER02-05-2009, 09:38 PMبا سلام خدمت دوستان عزیز مسئله برج هانوی رو که همه می شناسید و روش کار با 3 میله رو همه می دونند. اما حالا مشکل من اینه که برای k>3 روش کار چه جوری میشه.یعنی انتقال n دیسک به میله k ام چه جوری میشه. من فقط روال کار رو می خواستم اگر رابطه بازگشتی هم پیدا کردید چه بهتر. ممنون از لطف همه saber5703-05-2009, 06:54 PMاز جزییات برنامه نویسی چیزی نمیدونم اول به سایت برنامه نویس سر بزنید که مربوط برنامه نویسی هست . این لینکو ببینید: http://www.barnamenevis.org/forum/showthread.php?t=84226 توضیح ابتدایی در مورد برج هانوی با سه میله : http://fa.wikipedia.org/wiki/%D 8%A 8%D 8%B 1%D 8%AC_%D 9%87%D 8%A 7%D 9%86%D 9%88%DB%8C برای 3 دیسک: http://www.freezpic.com/pics/4b 950caec296f967fa 34446d 5722b 8d 8.gif 1: A---> C 2: A---->B 1: C----> B ----- 3:A---- C ----- 1: B----> A 2 : B----> C 1 : A---- >C ************************************************** ****** برای 4 دیسک(سه میله) http://www.freezpic.com/pics/f2ef509d 13bca 8441ad 6fe25b 0fcdf67.gif 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 منتقل بشن و بعد دیسک بزرگ از میله مبدا به مقصد انتقال پیدا کنه و الی آخر ..... باور کنید سختی مساله برج هانوی به همین تعداد کم میله هاشه :31: حالا هر چی میله ها زیادتر بشه راحتتریم . یک مثال : 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 به همین ترتیب الی آخر اگه نقصانی داشت دوستان برنامه نویس! یاری کنند CHAPTER03-05-2009, 07:28 PMاگه نقصانی داشت دوستان برنامه نویس! یاری کنند سلام آقا صابر باز شما به داد ما رسیدی این چه حرفیه ما خیلی مخلصیم ممون از لطفت مثل همیشه مفصل توضیح دادی سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 725]