حل تشریحی سوال شماره 59 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1398
59.
فرض کنید n بازه روی محور اعداد حقیقی داریم. میخواهیم بیشترین تعداد بازه را پیدا کنیم که با یکدیگر همپوشانی نداشته باشند. برای بازه I فرض کنید c(I) برابر تعداد بازه‌هایی است که با I هم پوشانی دارند. برای حل این مسئله از الگوریتم حریصانه زیر استفاده میکنیم. در هر مرحله از بین بازه‌های باقی مانده بازه I را کهc(I) از همه کمتر است انتخاب و تمام بازه‌هایی که با آن همپوشانی دارند حذف میکنیم. اگر چند بازه وجود داشت که تعداد همپوشانی شان کمینه بود یکی را به دلخواه انتخاب میکنیم. کمترین n که الگوریتم حریصانه فوق لزوما جواب بهینه را تولید نمیکند در بین گزینه‌ها کدام است؟
1)
9
2)
5
3)
3
4)
2
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،