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

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

 سوال

 

یک شرکت بشکه‌هایی از چهار ماده‌ی شیمیایی مختلف به نام‌ها A , B,C و D تولید و در انبارهای خود ذخیره می‌کند. این شرکت 4 انبار دارد که در هر انبار 4 بشکه از انواع A , B , C و D موجود است ( از هر ماده یک بشکه ). این مواد شیمیایی در صورتی که با هم مخلوط شوند , خطرناک هستند. به همین دلیل شرکت تصمیم دارد بشکه‌ها را بین این انبارها طوری جابجا کند که در نهایت هر انبار حاوی 4 بشکه از یک نوع ماده‌ی شیمیاییی باشد. برای این کار از یک کامیون استفاده می‌شود. این کامیون می‌تواند در هر بار جابجایی حداکثر 2 بشکه را از یک انبار به یکی دیگر از انبارهای شرکت انتقال دهد. حداقل با چند بار جابجایی می‌توان این کار را انجام داد؟

 

 

 

 

معلوم است که کامیون از انبار 1 که قرار است از حالت ABCD به حالت AAAA تبدیل شود, حداقل دوبار خارج و حداقل دوبار به آن انبار وارد خواهد شد. انبارهای 2, 3 و 4 نیز چنین وضعیتی را دارند. بنابراین حداقل جابجایی های لازم برابر 4+4+4+4 ÷ 2 یعنی 8 می‌باشد. اگر کامیون با الگوریتم زیر حرکت کند با 8 بار جابجایی می‌تواند به هدف برسد:

 

1.بشکه‌های BC را از انبار 1 به انبار 2 , منتقل کند.

 

2.بشکه‌های CC را از انبار 2 به انبار 3 , منتقل کند.

 

3.بشکه‌های BD را از انبار 3 به انبار 4 , منتقل کند.

 

4.بشکه‌های BB را از انبار 4 به انبار 2 , منتقل کند.

 

5.بشکه‌های AD را از انبار 2 به انبار 1 , منتقل کند.

 

6.بشکه‌های DD را از انبار 1 به انبار 4 , منتقل کند.

 

7.بشکه‌های AC را از انبار 4 به انبار 3 , منتقل کند.

 

8.بشکه‌های AA را از انبار 3 به انبار 1 , منتقل کند.

1392/1/15لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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