مسابقه‌ی تصادفی

 
 
 برج هانوی
برج هانویمسابقه كامپيوتر
مسابقه شماره ۲۱۳

سوال


سه میله با شماره‌های ۱,۲و۳و چهار مهره‌ی سوراخدار با شماره‌های ۱ تا ۴ مطابق شکل زیر داده شده است :

 


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

 


در هر حرکت تنها یک مهره حرکت داده شود.
هیچ‌گاه مهره‌ی با شماره‌ی بزرگتر بر روی مهره با شماره‌ی کوچیکتر قرار نگیرد.
آیا می‌توان با کمتر از ۱۱ حرکت این کار را انجام داد؟ ( اثبات کنید‌)




اگر n مهره به ترتیب شماره در داخل میله‌ی A باشند و دو میله‌ی B و C خالی باشند , آنگاه حداقل با2n - 1 حرکت می‌توان مهره‌ها را از A به C منتقل کرد به طوری که مهره‌های با شماره‌ی بزرگتر هرگز روی مهره‌های با شماره‌ی کوچیکتر قرار نگیرند.

 


اثبات : فرض می‌کنیم با حداقل hn - 1 حرکت بتوان n - 1 مهره با شرایط مذکور را از A به C منتقل کرد. ابتدا n - 1 مهره   را با hn - 1 حرکت از A به B منتقل می‌کنیم. فقط مهره‌ی n در داخل میله‌ی A باقی‌می‌ماند. با یک حرکت مهره‌ی n را به C منتقل می‌کنیم و با hn - 1 حرکت n - 1 مهره‌ی دیگر را از B به C انتقال می‌دهیم. پس مجموع حرکات برای چنین کاری برابر
hn-1 + 1 + hn-1 یعنی 2hn-1 + 1 خواهد بود. پس :


hn = 2hn-1 + 1     (1)A


می‌دانیم :


h1 = 1 , h2 = 3 , h4 = 7 , …A


با استفاده از رابطه‌ی بازگشتی (۱) معلوم می‌شود که :
برای حل مسأله مورد نظر الگوریتم زیر را پیاده می‌کنیم :
مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۲ را به میله‌ی ۱ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۴ را به میله‌ی ۳ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۱ تا ۳ را به میله‌ی ۳ منتقل می‌کنیم (با توجه به لم , ۷ حرکت ).
پس مجموعأ ۱۱ حرکت می‌شود و با کمتر از این , ممکن نیست.

1391/10/27لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  2546
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  2546