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

 
 
 حرکت روبات
حرکت روباتمسابقه كامپيوتر
مسابقه شماره ۱۸۱

سوال

روباتی روی خطوط یک جدول 3×3 با خطوط افقی و عمودی حرکت میکند. طی کردن هر پاره خط به طول 1 افقی 1 ثانیه و هر پاره خط به طول 1 عمودی 2 ثانیه طول میکشد. میخواهیم روبات را به گونه ای برنامه ریزی کنیم که از یک نقطه شروع کنید , از روی تمامی پاره خط های جدول عبور کند (میتواند از مسیرهای تکراری هم عبور کند ) و به جای اولش برگردد. انجام این کار حداقل چند ثانیه طول میکشد ؟  (مثلا در شکل زیر طی کردن مسیر مشخص شده 5 ثانیه طول میکشد.)

 

 


 

پاسخ

 

تعداد پاره خط های افقی 12 و نیز تعداد پاره خط های عمودی نیز 12 میباشد بنابراین اگر از هر پاره خط  فقط یک بار عبور کنیم مدت زمان لازم  2 × 12 + 1 × 12 ؛ یعنی 36 خواهد بود. اما شرط لازم برای آن که بتوان یک گراف را بدون برداشتن قلم از روی کاغذ و با عبور از هر یال دقیقا یک بار چنان رسم کرد که نقطه پایان همان نقطه شروع باشد, آن است که درجه همه رئوس  آن زوج باشد که در گراف رسم شده درجه 8 راس ؛ یعنی رئوس B , C , E , H , I , L , N و O فرد بوده

و به ازای هر دو راس فرد که به یکدیگر وصل هستند

یک حرکت اضافی لازم است. اگر حرکت به صورت زیر باشد , مدت زمان لازم 42 ثانیه خواهد بود.

A - B - F - G - C - B - C - D - H - G - K - L - H - L - P - O - K - J - N - O - N - M - I - J - F - E - I - E - A

1391/1/14لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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