Fliqpy
کاربر نیمهحرفهای
- ارسالها
- 181
- امتیاز
- 303
- نام مرکز سمپاد
- غیر انتفاعی علامه حلی 3
- شهر
- تهران
- مدال المپیاد
- هر جوری حساب میکنم افتخار نمیکنم بهش
- دانشگاه
- شريف
- رشته دانشگاه
- نرم افزار
پاسخ : آرشیو سوالات از گذشته تا کنون
نمیدونم درسته یا نه ولی فکر کنم با 3n-logn-3 بشه
الگوریتم ما این طوریه که در هر مرحله ثابت میکنیم یه نفر ستاره مشهور نیست
دو نفر رو که نمیدونیم ممکنه باشن یا نه رو انتخاب میکنیم و از یکی در مورد اون یکی میپرسیم.اگه جواب بله بود پس اونی که ازش پرسیدیم ستاره نیست و اگه "نه" بود اونی که راجع بهش پرسیدیم.(هر مرحله دو نفری رو انتخاب میکنیم کمترین تعداد پرسش ازشون صورت گرفته شده باشه)پس بعد از n-1 مرحله یه نفر میمونه. حالا برای اینکه بفهمیم اون ستاره هست یا نه،باید حداکثر 2n-2 تا سوال بپرسیم (اون راجع به هر کدوم از افراد دیگه و هر کدوم از افراد دیگه راجع به اون)اما قبلاً logn تا از این سوالا رو پرسیدیم پس میشه 3n-logn-3.
نمیدونم درسته یا نه ولی فکر کنم با 3n-logn-3 بشه
الگوریتم ما این طوریه که در هر مرحله ثابت میکنیم یه نفر ستاره مشهور نیست
دو نفر رو که نمیدونیم ممکنه باشن یا نه رو انتخاب میکنیم و از یکی در مورد اون یکی میپرسیم.اگه جواب بله بود پس اونی که ازش پرسیدیم ستاره نیست و اگه "نه" بود اونی که راجع بهش پرسیدیم.(هر مرحله دو نفری رو انتخاب میکنیم کمترین تعداد پرسش ازشون صورت گرفته شده باشه)پس بعد از n-1 مرحله یه نفر میمونه. حالا برای اینکه بفهمیم اون ستاره هست یا نه،باید حداکثر 2n-2 تا سوال بپرسیم (اون راجع به هر کدوم از افراد دیگه و هر کدوم از افراد دیگه راجع به اون)اما قبلاً logn تا از این سوالا رو پرسیدیم پس میشه 3n-logn-3.