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

 
 
 دنباله
دنبالهمسابقه كامپيوتر
مسابقه شماره ۲۳۵

 سوال 

 

ترکیب دو دنباله مرتب A و B به ترتیب با اندازه‌های n و m یک دنباله مرتب به اندازه  n + m تولید می‌کند و این کار به اندازه m + n  هزینه دارد. 
 
( مثلا اگر A = ( 1,2,3,4,) و B = ( 4,6 ) باشد, C = ( 1,2,3,4,5,6 ) ترکیب این دو دنباله و هزینه تولید آن 6 است.)
 
برای ترکیب سه دنباله , ابتدا دوتای آنها را به هم ترکیب و دنباله حاصل را با دنباله سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله اول در کل هزینه ترکیب موثر است. حال فرض کنید 7 دنباله سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله اول در کل هزینه ترکیب موثر است. حال فرض کنید 7 دنباله به اندازه‌های 10,8,8,7,6,5,4 داریم. کمترین هزینه کل برای ترکیب این 7 دنباله چقدر است؟
 

 
پاسخ
 
ابتدا توجه می‌کنیم که برای ترکیب سه دنباله با طول‌های c,b,a ابتدا دو تا از آنها مانند , b,a را ترکیب کرده ( که حاصل دنباله به طول a + b و با هزینه a + b می‌شود)  و سپس دنباله‌های حاصل را با دنباله سوم ترکیب می‌کنیم که حاصل دنباله‌ای به طول a + b + c  شده ولی هزینه آن  ( a + b ) + c  می‌شود که در کل مجموع هزینه‌ها برابر 2( a + b) + c  می‌شود. برای آنکه کل هزینه‌ها مینیمم شود کافی است هر یک از دو عدد a و b از عدد c کمتر یا مساوی باشند. بنابراین در هر دسته‌ای که حداقل 3 دنباله داشته باشد ابتدا ذنباله‌های با طول مینیمم را با هم ترکیب می‌کنیم , که به جدول زیر خواهیم رسید.
 

 

1392/5/27لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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