تاریخچه و صورت مساله
در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که
یکی از آنها حاوی تعدادی قرص طلایی بود. کاهنان معبد در تلاش
بودند تا قرص‌های طلائی را از آن میله به یکی دیگر از میله‌ها تحت
شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها
عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت
که بر روی هم به طور نزولی بر اساس اندازه‌شان چیده شده‌بودند
نمونه‌ای از برج هانوی
همانند شکل سه میله داریم
یکی از میله‌ها میله مبدا (الف)، دیگری میله کمکی (ب) و دیگری
میله مقصد (ج) است. هدف انتقال تمام دیسکها از میله مبدا
به میله مقصد با رعایت شرایط زیر است
در هر زمان فقط یک دیسک را می‌توان جابجا نمود. نباید در هیچ زمانی
دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد
حل مساله
هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال
دیسکها به ما بدهد. مثلا اگر تعداد دیسکها ۲ باشد، توالی حرکت به
صورت زیر است
حل مساله برج هانوی
دیسک ۱ را به میله ب منتقل می‌کنیم
دیسک ۲ را به میله ج منتقل می‌کنیم
دیسک ۱ را به میله ج منتقل می‌کنیم
حل مساله برج هانوی
توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین
دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد
|
برج هانوی در ویکیپدیا
توضیح مسئله برج هانوی و کد سی++ آن
معمای حلقه های برج هانوی
|