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

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

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




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

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

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

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

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

         

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

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

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

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

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

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

     

 

اخبار

 

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

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.