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

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

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


پاسخ
تعداد پاره خط‌های افقی 12 و نیز تعداد پاره خط‌های عمودی نیز 12 می‌باشد , بنابراین اگر از هر پاره خطر فقط یک بار عبور کنیم مدت زمان لازم 2 × 12 + 1 × 12 ؛ یعنی 36 ثانیه خواهد بود. اما شرط لازم برای آن که بتوان یک گراف را بدون برداشتن قلم از روی کاغذ و با عبور از هر یال دقیقا یک با چنان رسم کرد که نقطه‌ی پایان همان نقطه‌ی شروع باشد , آن است که درجه‌ی همه رئوس آن زوج باشد که در گراف رسم شده درجه‌ی 8 راس ؛ یعنی رئوس   N , L , I , H , E , C , B و 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/8/26لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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