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

 
 
 يافتن فرد مشهور! (مسابقه‌ي شماره‌ي 13) ويژه‌ي ايام نوروز
يافتن فرد مشهور! (مسابقه‌ي شماره‌ي 13) ويژه‌ي ايام نوروزمسابقه كامپيوتر
گراف جهت‌دار

يافتن فرد مشهور




سؤال
در بين n نفر، «فرد مشهور» به كسي گفته مي‌شود كه همه او را بشناسند و او هيچ‌كس را نشناسد.

- مسأله، پيدا كردن «فرد مشهور» در يك جمع است.
- تنها سؤالي كه مجاز هستيم بپرسيم اين است كهآيا فرد x فرد y را مي‌شناسد يا نه.
- هدف كمينه كردن تعداد سؤال‌ها است.

چون n(n-1)/2 جفت از افراد داريم پس در بدترين حالت با پرسيدن n(n-1) سؤال مي‌توانيم كه «فرد مشهور» را پيدا كنيم.

حال الگوريتمي بنويسيد كه اين كار را با كمينه‌ترين تعداد سؤال‌ها انجام دهد.

راهنمايي
براي حل كردن مسأله مي‌توانيم از يك «گراف جهت‌دار» استفاده كنيم. رأس x را به رأس y وصل كنيم اگر و فقط اگر فرد x فرد y را بشناسد.

     

1386/1/9لينک مستقيم

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

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