حمید ملارضا
حمید ملارضا
خواندن ۴ دقیقه·۲ سال پیش

بازی/معمای برج‌های هانوی + کد پایتون و سی‌شارپ

بسم الله الرحمن الرحیم

بازی/معمای برج‌های هانوی
بازی/معمای برج‌های هانوی

مسئله چیه؟

مطابق تصویر، سه میله داریم با تعدادی حلقه. این حلقه‌ها با توجه به وزنشون (به ترتیب از سنگین به سبک) روی میله اول قرار گرفتن. هدف اینه که این حلقه‌ها رو (به همین ترتیب) از میله اول به میله دوم منتقل کنیم. تنها شرط بازی هم اینه که اجازه نداریم حلقه سنگین‌تر رو روی حلقه سبک‌تر قرار بدیم. (احتمالا برای اینکه ممکنه آسیب ببینن!)

قبل و بعد از حل مسئله
قبل و بعد از حل مسئله

اگر می‌خواین این بازی رو آنلاین بازی کنید تا درک بهتری داشته باشید این لینک رو ببینید.


راه‌حل

قبل از اینکه وارد دنیای کدنویسی بشیم بیایین سعی کنیم مسئله رو حل کنیم.

توی این بازی nتا حلقه وجود داره. برای اینکه راه‌حل رو پیدا کنیم بهتره از ساده‌ترین حالت شروع کنیم:

  • اگر یه دونه حلقه داشته باشیم (n = ۱ باشه): در این صورت جواب خیلی واضح هستش! حلقه رو مستقیم به میله دوم جابه‌جا می‌کنیم. هورا! مسئله حل شد!
  • اگر دوتا حلقه داشته باشیم (n = ۲ باشه):
    می‌دونیم حلقه‌ها براساس سنگینی مرتب شدن. توی میله دوم هم باید به همین ترتیب قرار بگیرن. پس باید کاری کنیم که اول حلقه سنگین‌تر در میله دوم قرار بگیره بعد حلقه سبک‌تره.
    برای اینکار باید حلقه سبک‌تر رو جابه‌جا کنیم. اگر حلقه سبک‌تر رو روی میله دوم قرار بدیم با توجه به شرط بازی دیگه نمی‌تونیم حلقه سنگین‌تر رو روی اون قرار بدیم پس باید حلقه سبک‌تر رو به میله سوم(کمکی) جابه‌جا کنیم تا شرایط برای جابه‌جایی حلقه سنگین‌تر فراهم بشه. درنتیجه:
    ۱- ابتدا حلقه سبک‌تر (بالایی) رو به میله کمکی جابه‌جا می‌کنیم. ۲- حلقه سنگین‌تر رو به میله دوم جابه‌جا می‌کنیم. ۳- در آخر حلقه سبک‌تر رو از میله کمکی به میله دومی جابه‌جا می‌کنیم. به صورت خلاصه جابه‌جایی ها به اینصورت هستش:
    میله اول به میله سوم
    میله اول به میله دوم
    میله سوم به میله دوم
حل مسئله برای n=2
حل مسئله برای n=2
  • اگر سه‌تا حلقه داشته باشیم:
    توی این حالت هم اول باید حلقه آخر که از همه سنگین‌تره روی میله دوم قرار بگیره. اما دوتا حلقه بالایی مزاحمش هستن. باید چیکار کنیم؟ ۱- ابتدا دوتا حلقه بالایی (که مزاحم هستن) رو به میله کمکی جابه‌جا کنیم. ۲- حلقه سنگین‌تر رو به میله دوم جابه‌جا کنیم. ۳- دوتا حلقه‌ای که به میله کمکی جابه‌جا کردیم رو به میله دوم جابه‌جا کنیم. جابه‌جا کردن این دوتا حلقه هم مثل حالت n=2 هستش.

خب مسئله رو برای حالت‌های یک حلقه، دو حلقه و سه حلقه حل کردیم. خصوصا اگر به دو حالت آخر توجه کنیم می‌بینیم یک روند تکراری وجود داره. هربار سنگین‌ترین حلقه (آخرین حلقه) رو در نظر می‌گیریم و ۳تا حرکت رو انجام می‌دیم. ۱- هرچی حلقه بالای اون هست رو به میله کمکی جابه‌جا می‌کنیم. ۲- حلقه سنگین رو به میله دوم جابه‌جا می‌کنیم. ۳- حلقه‌هایی که به میله کمکی منتقل شدن رو به میله دوم منتقل می‌کنیم. درواقع الگوریتم ما چیزی شبیه به این خواهد بود:
۱- برو n-1 حلقه رو از میله اول به میله کمکی منتقل کن
۲- حلقه سنگین رو از میله اول به میله دوم منتقل کن
۳- برو n-1 حلقه‌ای که به میله کمکی جابه‌جا شده رو به میله دوم منتقل کن.

اگر یک حلقه داشته باشیم (n=1) باشه که جواب بدیهی هستش. اگر هم دو حلقه یا بیشتر داشته باشیم براساس الگوریتم بالا میشه حلش کرد.

نکته دیگه‌ای که میشه حدس زد حداقل تعداد حرکت‌های لازم برای حل این مسئله هستش. به این جدول نگاه کنید:

با توجه به این جدول میشه حدس زد که احتمالا حداقل تعداد حرکت‌های لازم به صورت زیر هستش:

البته توی مسائل ریاضی حدس زدن کافی نیست و لازمه اثبات بشه اما از اثبات این قضیه می‌گذریم.


پیاده‌سازی

برای پیاده‌سازی این مسئله باید با تابع (پایتون) یا متد (سی‌شارپ) آشنا باشین. ضروری نیست اما بهتره با روش بازگشتی هم آشنا باشین.

در قسمت قبل متوجه شدیم الگوریتم مسئله به چه شکل هستش. اگر n = ۱ باشه که به راحتی حلقه رو جابه‌جا می‌کنیم و اگر n بزرگتر از ۱ باشه ۳ مرحله گفته شده رو باید انجام بدیم.

پس فقط لازمه یه تابع یا متد تعریف کنیم که تعداد حلقه‌ها رو بگیره به علاوه اسم میله‌ها (برای نمایش پیغام) بعد الگوریتم گفته شده رو اجرا کنه. بعدش هرجا نیاز به جابه‌جایی حلقه‌ها داشتیم همین تابع/متد رو فراخوانی می‌کنیم تا در نهایت مسئله ما حل بشه.

بهتره اول سعی کنید خودتون این مسئله رو پیاده‌سازی کنید بعدش برای دیدن کد پایتون این لینک رو ببینید و برای دیدن کد سی‌شارپ این لینک رو ببینید.

خروجی نمونه برای ۳ حلقه
خروجی نمونه برای ۳ حلقه


به صورت کلی تصمیم دارم مطالبی که به صورت عمومی منتشر میکنم رو توی این مخزن گیت‌هاب قرار بدم. اگر دوست داشتین ستاره بدین و این مطلب رو لایک کنید.

امیدوارم مفید بوده باشه. اگر سوالی، نکته‌ای، حرفی داشتین می‌تونید همینجا کامنت بذارین یا به hamidmolareza@gmail.com ایمیل بزنید.

موفق باشین. :)


هانویالگوریتمحل مسئلهپایتونسی‌شارپ
یادداشت‌های شخصی درباره مهندسی نرم‌افزار، کسب و کار، فرهنگی و... به هدف رشد فردی و ان‌شاءالله مفید بودن. 🇵🇸️
شاید از این پست‌ها خوشتان بیاید