بسم الله الرحمن الرحیم
مطابق تصویر، سه میله داریم با تعدادی حلقه. این حلقهها با توجه به وزنشون (به ترتیب از سنگین به سبک) روی میله اول قرار گرفتن. هدف اینه که این حلقهها رو (به همین ترتیب) از میله اول به میله دوم منتقل کنیم. تنها شرط بازی هم اینه که اجازه نداریم حلقه سنگینتر رو روی حلقه سبکتر قرار بدیم. (احتمالا برای اینکه ممکنه آسیب ببینن!)
اگر میخواین این بازی رو آنلاین بازی کنید تا درک بهتری داشته باشید این لینک رو ببینید.
قبل از اینکه وارد دنیای کدنویسی بشیم بیایین سعی کنیم مسئله رو حل کنیم.
توی این بازی nتا حلقه وجود داره. برای اینکه راهحل رو پیدا کنیم بهتره از سادهترین حالت شروع کنیم:
خب مسئله رو برای حالتهای یک حلقه، دو حلقه و سه حلقه حل کردیم. خصوصا اگر به دو حالت آخر توجه کنیم میبینیم یک روند تکراری وجود داره. هربار سنگینترین حلقه (آخرین حلقه) رو در نظر میگیریم و ۳تا حرکت رو انجام میدیم. ۱- هرچی حلقه بالای اون هست رو به میله کمکی جابهجا میکنیم. ۲- حلقه سنگین رو به میله دوم جابهجا میکنیم. ۳- حلقههایی که به میله کمکی منتقل شدن رو به میله دوم منتقل میکنیم. درواقع الگوریتم ما چیزی شبیه به این خواهد بود:
۱- برو n-1 حلقه رو از میله اول به میله کمکی منتقل کن
۲- حلقه سنگین رو از میله اول به میله دوم منتقل کن
۳- برو n-1 حلقهای که به میله کمکی جابهجا شده رو به میله دوم منتقل کن.
اگر یک حلقه داشته باشیم (n=1) باشه که جواب بدیهی هستش. اگر هم دو حلقه یا بیشتر داشته باشیم براساس الگوریتم بالا میشه حلش کرد.
نکته دیگهای که میشه حدس زد حداقل تعداد حرکتهای لازم برای حل این مسئله هستش. به این جدول نگاه کنید:
با توجه به این جدول میشه حدس زد که احتمالا حداقل تعداد حرکتهای لازم به صورت زیر هستش:
البته توی مسائل ریاضی حدس زدن کافی نیست و لازمه اثبات بشه اما از اثبات این قضیه میگذریم.
برای پیادهسازی این مسئله باید با تابع (پایتون) یا متد (سیشارپ) آشنا باشین. ضروری نیست اما بهتره با روش بازگشتی هم آشنا باشین.
در قسمت قبل متوجه شدیم الگوریتم مسئله به چه شکل هستش. اگر n = ۱ باشه که به راحتی حلقه رو جابهجا میکنیم و اگر n بزرگتر از ۱ باشه ۳ مرحله گفته شده رو باید انجام بدیم.
پس فقط لازمه یه تابع یا متد تعریف کنیم که تعداد حلقهها رو بگیره به علاوه اسم میلهها (برای نمایش پیغام) بعد الگوریتم گفته شده رو اجرا کنه. بعدش هرجا نیاز به جابهجایی حلقهها داشتیم همین تابع/متد رو فراخوانی میکنیم تا در نهایت مسئله ما حل بشه.
بهتره اول سعی کنید خودتون این مسئله رو پیادهسازی کنید بعدش برای دیدن کد پایتون این لینک رو ببینید و برای دیدن کد سیشارپ این لینک رو ببینید.
به صورت کلی تصمیم دارم مطالبی که به صورت عمومی منتشر میکنم رو توی این مخزن گیتهاب قرار بدم. اگر دوست داشتین ستاره بدین و این مطلب رو لایک کنید.
امیدوارم مفید بوده باشه. اگر سوالی، نکتهای، حرفی داشتین میتونید همینجا کامنت بذارین یا به hamidmolareza@gmail.com ایمیل بزنید.
موفق باشین. :)