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

 
 
 برج هانوي (مسابقه‌ي شماره‌ي 15) ويژه‌ي ايام نوروز
برج هانوي (مسابقه‌ي شماره‌ي 15) ويژه‌ي ايام نوروزمسابقه كامپيوتر
محاسبه‌ي حداقل تعداد حركت‌ها براي n ديسك

برج هانوي


 سؤال
مسأله‌ي «برج هانوي» به اين صورت است كه سه ميله به‌نام‌هاي A,B,C داريم كه در ميله‌ي اول n صفحه متمايز به‌ترتيب نزولي‌ قرار دارند. در هر حركت مي‌توانيم كه يك صفحه را از بالاي يك ميله برداشته در ميله‌ي ديگر قرار دهيم با اين شرط كه هيچ‌گاه صفحه‌ي كوچك‌تر زير صفحه‌ي بزرگ‌تر قرار نگيرد.



هدف بردن تمام ديسك‌ها از ميله‌‌ي A به C است با اين شرط اضافي كه هيچ‌گاه صفحه‌اي را به‌طور مستقيم از A به C يا از C به A منتقل نكنيم. حداقل تعداد حركت‌ها براي n ديسك را به‌دست آوريد. اگر تعداد ميله‌ها چهار تا باشد در مورد تعداد حركت‌ها چه مي‌توان گفت؟


            

1386/1/11لينک مستقيم

فرستنده :
reza HyperLink HyperLink 1386/10/1
مـتـن : تعداد حرکت میشه 2 به توان n و سپس منهای یک.
دو به توان ان و سپس منهای یک
پاسـخ :ايميل فرستنده: reza.magical@yahoo.com
صفحه‌ي شخصي: http://bushehrteam.com
تاريخ ارسال: 1386

فرستنده :
محمد رضا HyperLink HyperLink 1386/2/30
مـتـن : مي شود 2به توان nدر كل -1

فرستنده :
محمد محمودی HyperLink HyperLink 1386/1/15
مـتـن : بسم الله الرحمن الرحیم

جواب 2n+4 حرکت می شود .

اگر برجها را به ترتیب با 1A و 2An …………… A نامگذاری کنیم . و بخواهیم همه حلقه ها را از 1Aبه An منتقل کنیم :
آنگاه طی این 6 مرحله این کار انجام می شود.

1)کوچکترین حلقه را به برج An منتقل کرده و سپس بقیه ی حلقه ها را نیز به برج های دیگر منتقل می کنیم که این کار نیاز مند n-1 حرکت است . ( n-1 حرکت )

2) سپس کوچکترین حلقه را از An به بالای یکی دیگر از حلقه ها به جز بزرگترین حلقه منتقل می کنیم ( 1 حرکت )

3) و برای برقرار شدن شرط اضافی نیز دو حلقه دلخواه دیگر انتخاب می کنیم و حلقه کوچکتر را روی حلقه بزرگتر قرار داده تا یکی از برجهای مثل Ai نیز خالی شود. (1 حرکت )

4) اکنون دو برج خال داریم برای برقراری شرط اضافی بزرگترین حلقه را ابتدا به Ai و سپس به An منتقل می کنیم (2 حرکت )

5) دو برج دو دو تایی را با انتقال حلقه های بالایی آن ها به Ai و An به برجهای یک حلقه ای تبدیل می کنیم .
(2 حرکت )

6) همه برجها را به ترتیب از بزرگ به کوچک به An منتقل می کنیم ( n-1 حرکت )


تعداد کل برابر با :

n-1+1+1+2+2+n-1= 2n+4
پاسـخ : سلام دوست عزيز متاسفانه نظر شما به اشتباه دوبار فرستاده شده كه چون هيچ تفاوتي با هم ندارند پس پاسخ ما به اين نظر همان پاسخ قبلي خواهد بود !
موئفق باشي !

فرستنده :
محمد محمودی HyperLink HyperLink 1386/1/15
مـتـن : بسم الله الرحمن الرحیم

جواب 2n+4 حرکت می شود .

اگر برجها را به ترتیب با 1A و 2An …………… A نامگذاری کنیم . و بخواهیم همه حلقه ها را از 1Aبه An منتقل کنیم :
آنگاه طی این 6 مرحله این کار انجام می شود.

1)کوچکترین حلقه را به برج An منتقل کرده و سپس بقیه ی حلقه ها را نیز به برج های دیگر منتقل می کنیم که این کار نیاز مند n-1 حرکت است . ( n-1 حرکت )

2) سپس کوچکترین حلقه را از An به بالای یکی دیگر از حلقه ها به جز بزرگترین حلقه منتقل می کنیم ( 1 حرکت )

3) و برای برقرار شدن شرط اضافی نیز دو حلقه دلخواه دیگر انتخاب می کنیم و حلقه کوچکتر را روی حلقه بزرگتر قرار داده تا یکی از برجهای مثل Ai نیز خالی شود. (1 حرکت )

4) اکنون دو برج خال داریم برای برقراری شرط اضافی بزرگترین حلقه را ابتدا به Ai و سپس به An منتقل می کنیم (2 حرکت )

5) دو برج دو دو تایی را با انتقال حلقه های بالایی آن ها به Ai و An به برجهای یک حلقه ای تبدیل می کنیم .
(2 حرکت )

6) همه برجها را به ترتیب از بزرگ به کوچک به An منتقل می کنیم ( n-1 حرکت )


تعداد کل برابر با :

n-1+1+1+2+2+n-1= 2n+4
پاسـخ :سلام دوست عزيز ،‌متاسفانه شما جواب نادرست به اين مسابقه دايد !
شما اصلا به شكل هايي كه براي كمكبه شما و همچين براي روشنشدن وضعيت حركت قرار داده شده دقت نكرديد !
اصلا در اين مسئله ما فقط سه برج داريم نه n تا !
مي تونيد با توجه به راهنمايي هايي كه شكل دوم به شما در مورد چگونگي حركت ديسك ها ميدهد ، بيشتر روي اين مساله فكر كنيد !

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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