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

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

سوال


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

 


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

 


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




اگر 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 لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.