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

 
 
 ادغام
ادغاممسابقه كامپيوتر
مسابقه شماره ۲۴۶

 سوال

 

۵ گونی شکر به وزن‌های ۲ ٫ ۳ ٫ ۴ ٫ ۴ و ۶ و یک گونی خالی داده شده‌اند. می‌خواهیم همه شکرها را در یک گونی بریزیم. هر بار می‌توانیم یک عمل ادغام انجام دهیم. هر ادغام یعنی انتخاب دو عدد از گونی‌های شکر ٫ مثلا با وزن‌های a و b و یک گونی خالی و ریختن کامل شکرهای دوگونی در گونی خالی ٫ فرض کنید که هزینه انجام این ادغام برابر a + b باشد ٫ کمترین هزینه کل انجام این کار چقدر است ؟ 
 
 
 
 

 
پاسخ
 
اگر سه گونی به اوزان a ٫ b و c چنان باشند که  a ≤ b ≤ c ٫ آنگاه با توجه به ادغام‌های گوناگون به یکی از هزینه‌های a+2b+2c ٫ 2a+b+2c و یا 2a+2b+c خواهیم رسید که در بین آن هزینه‌ها 2a+2b+c کمترین مقدار ممکن را دارد.
بنابراین بهتر آن است که در ابتدا گونی‌های سبک‌تر را با هم ادغام کرده و حاصل را با بعدی و به همین ترتیب تا آخر پیش رویم :
 
2 + 3 = 5(هزینه ۵)
 
4 + 4 = 8(هزینه ۸)
 
5 + 6 = 11(هزینه ۱۱)
 
8 + 11 = 19(هزینه ۱۹)
 
که مجموع هزینه‌ها برابر است با ۴۳

 

1392/10/11لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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