حل مساله برج هانوی - تالار گفتمان آذر فروم





دعوت به همکاری با آذر فروم

 

حل مساله برج هانوی
زمان کنونی: 16-09-1395،08:22 ق.ظ
کاربران در حال بازدید این موضوع: 1 مهمان
نویسنده: Friga
آخرین ارسال: Friga
پاسخ: 1
بازدید: 290

 
 
رتبه موضوع:
  • 0 رای - 0 میانگین
  • 1
  • 2
  • 3
  • 4
  • 5

موضوع: حل مساله برج هانوی
ارسال: #1
حل مساله برج هانوی
پست‌ها: 11,943
تاریخ عضویت: 20 اردیبهشت 1390
اعتبار: 288
حالت من: Shad
برج هانوی


مساله «برج هانوی» از سه میله با نام های
A


و
B


و
C


تشکیل می شود که
n


دیسک با قطر های مختلف ( و ارتفاع های یکسان ) در میله ها قرار دارند. در
ابتدای کار تمام دیسک ها به صورت مرتب شده بر اساس قطرشان ( طوری که کم
قطرترین دیسک بالاترین و بزرگ ترین دیسک پایین ترین باشد ) روی میله
A


قرار دارند.





یک
حرکت «مجاز» در این مساله برداشتن بالاترین دیسک از یک میله( میله مبدا )و
قرار دادن آن در میله ای دیگر( میله مقصد ) است بطوری که هیچ گاه یک دیسک
روی دیسکی با قطر کوچکتر قرار نگیرد. با این وصف ، یک حرکت را می توان با
دو حرف بزرگ انگلیسی نمایش داد که حرف اول میله مبدا و حرف دوم میله مقصد
است. برای مثال حرکت
AB


یعنی برداشتن بالاترین دیسک میله
A


و قرار دادن آن روی تمام دیسک های میله
B


( در صورت وجود ). دقت کنید که حرکت
AB


تنها زمانی مجاز است که میله
A


حداقل یک دیسک داشته باشد و بعلاوه یا میله
B


خالی باشد یا قطر بالاترین دیسک میله
A


( که جابجا می شود ) از قطر بالاترین دیسک میله
B


کمتر باشد.
با شروع از حالتی که تمام دیسک ها بصورت مرتب در میله ی
A


قرار دارند ( نظیر شکل بالا )، بازی هنگامی تمام می شود که تمام دیسک ها به همین ترتیب در میله
B


قرار بگیرند ( و میله های
A


و
C


خالی باشند ) یا تمام دیسک ها به همین ترتیب در میله ی
C


قرار بگیرند ( و میله های
A


و
B


خالی باشند ).
هوشنگ
برای حل کردن این معما ، الگوریتم زیر را در پیش می گیرد. او ابتدا یک
جایگشت از تمام 6 حرکت موجود در نظر می گیرد ( مثلا جایگشت
CB


،
AC


،
BA


،
BC


،
AB


،
CA


از چپ به راست ) ، سپس در هر مرحله سمت چپ ترین حرکت مجاز از حرکات این
جایگشت را انجام می دهد. علاوه بر این ، او هبچ وقت دوست ندارد یک دیسک را
در دو حرکت متوالی جابجا کند و از این رو اگر یک حرکت ( بعد از حرکت اول )
از مقصد حرکت قبلی آغاز شود ، او این حرکت را غیر مجاز تلقی می کند. برای
مثال اگر جایگشت نمونه ی گفته شده را روی میله های شکل در نظر بگیریم ،
اولین حرکت هوشنگ
AB


خواهد بود

( چرا که
CA


بدلیل خالی بودن میله
C


غیر مجاز است ) و حرکت دوم او
AC


خواهد بود:
CA


غیر مجاز است چون
C


هنوز خالی است؛
AB


غیر مجاز است چون دیسک با قطر 2 را نمی توان روی دیسک با قطر 1 ( که در حرکت اول به
B


منتقل شده ) قرار داد؛
BC


نیز غیر مجاز است چرا که دیسک رویی
B


در حرکت قبلی تکان خورده و هوشنگ دوست ندارد یک دیسک را در 2 حرکت متوالی جابجا کند و از این رو سمت چپ ترین حرکت مجاز ،
AC


است!
می
توان اثبات کرد که الگوریتم هوشنگ همیشه پایان می یابد! آنچه از شما
خواسته می شود این است که با دانستن تعداد دیسک ها و استراتژی هوشنگ(
جایگشتی از 6 حرکت ممکن )، مشخص کنید که هوشنگ چند جابجایی انجام می دهد
تا بازی تمام شود.
ورودی
در سطر اول ورودی ، تعداد تست داده می شود. سپس هر تست در 2 خط داده می ش.د که خط اول تنها یک عدد
n


را داشته و در خط دوم یک جایگشت از حرکات ممکن بصورت 6 رشته 2 حرفی ( معتبر و دو به دو متمایز) داده می شود.
خروجی
به ازای هر تست ورودی ، در یک سطر تعداد حرکاتی که هوشنگ می کند را بنویسید.
محدودیت ها
می دانیم که N<=۱ و N<=۳۰

و جواب خروجی هیچ تستی از 10 به توان 18 بیشتر نبست.

دیدن لینک ها برای شما امکانپذیر نیست . لطفا
ثبت نام کنید یا وارد حساب کاربری خود شوید



[b]

دیدن لینک ها برای شما امکانپذیر نیست . لطفا
ثبت نام کنید یا وارد حساب کاربری خود شوید

















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


=====ஜ۩۞۩ஜ=====

28-05-1391 05:33 ب.ظ
 


[-]
پاسخ سریع
پیام
پاسخ خود را برای این پیام در اینجا بنویسید.


کد تصویری
royalfuns
(غیر حساس به بزرگی و کوچکی حروف)
لطفاً کد نشان داده شده در تصویر را وارد نمایید. این اقدام جهت جلوگیری از ارسال‌های خودکار ضروری می‌باشد.

پرش به انجمن:


کاربران در حال بازدید این موضوع: 1 مهمان