Printable View
مساله ستاره مشهور :
فرض کنید که n نفر دارید و در بین این n نفر یک نفر به عنوان ستاره می باشد. ستاره کسی است که همه او را از قبل می شناسند ولی او کسی را نمی شناسد .
میخواهیم با حداقل تعداد پرسش از این n نفر ستاره را بشناسیم.
ما مجاز هستیم که از نفری مثل A بپرسیم که آیا B را میشناسد یا نه ؟
الگوریتم حریسانه این مسأله را ارائه دهید.
بگید ببینم ایا غیر از ستاره همه همدیگر را میشناسند؟
نه
تنها کسی که مشهور است همان ستاره است.
همه آقاي star رو مي شناسن. پس ما از اولين نفر سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت پس همين شخص star هستش و خاتمه، و اگر شناخت به متغير counter يا شمارنده 1 واحد اضافه كن. (اين متغير تعداد پرسش ها رو شمارش مي كنه).نقل قول:
بگید ببینم ایا غیر از ستاره همه همدیگر را میشناسند؟
نه
تنها کسی که مشهور است همان ستاره است.
حالا نفر دوم دوباره ازش سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت اين شخص star هست و خاتمه، در غير اينصورت 1 واحد به متغير counter اضافه كن و برو به نفر بعدي.
....
عبارت "ْآيا Star رو ميشناسه؟" اشتباهه. چون در ابتدا Star وجود نداره، وظيفه شماست كه اون رو پيدا كنيد.نقل قول:
نوشته شده توسط obalitjoOon
فرض مي كنيم شما يه ليست حاوي n نفر داريد:
n1,n2,n3,n4,n5,...در ابتدا يه ليست از همه افراد تهيه مي كنيم.
براي هر يك افراد موجود در ليست مثلا فرد L
از همه افراد (ديگه) مي پرسيم كه آيا اين فرد رو مي شناسن يا نه. در صورتي كه همه مي شناختنش، فرد Star ،L هست و در غير اينصورت به سراغ فرد بعدي ميريم.
نقل قول:
در ابتدا يه ليست از همه افراد تهيه مي كنيم.
براي هر يك افراد موجود در ليست مثلا فرد L
از همه افراد (ديگه) مي پرسيم كه آيا اين فرد رو مي شناسن يا نه. در صورتي كه همه مي شناختنش، فرد Star ،L هست و در غير اينصورت به سراغ فرد بعدي ميريم.
نقل قول:
چرا اينقدر طولانی!؟
اگر "از همه افراد (ديگه)" رو حذف می كرديد بهتر بود. كسی كس ديگری رو ( به جز ستاره ) نمی شناسه. از همون نفر اول كه پرسيدی اگر گفت بله كه معلومه فرد L ستاره هست و اگر گفت خير ميره سراغ فرد بعدی.
طبق صورت سوال که در پست اول ذکر شده، گفته شده Star رو همه میشناسننقل قول:
نوشته شده توسط Armin060
نه اینکه هیچ کس، غیر از Star رو نمیشناسه.
بنابراین راه حل حریصانه همونیه که در بالا گفتم.
اگر به پست های بعدی نگاه می كردی می فهميدی.
این مسأله در اصل برای یک گراف طرح میشه: اگر در یک گراف جهت دار، همه رأسها به یک رأس یال داشته باشند ولی آن رأس به هیچ کدام از بقیه رئوس یالی نداشته باشد، آن رأس را ستاره مشهور مینامیم. با این فرض که ماتریس مجاورت یک گراف داده شده باشد ستاره مشهور آن را پیدا کنید. در واقع پرسیدن سؤال مثل چک کردن این است که خانه i , j ماتریس مجاورت صفر است یا یک. فکر میکنم با این انتزاع، روشن شده باشه که پرسیدن "آیا ستاره را میشناسی" درست نیست. راه حل Mbt925 درسته. ولی درواقع O(n^2) زمان میگیره در صورتی که میشه با n تا پرسش کار رو تموم کرد. فرض کنید افراد رو شماره گذاری کردیم. از یک تا n. حالا از اولی میپرسیم که آیا دومی رو میشناسه یا نه. اگه بشناسه اولی حذف میشه (یعنی نمیتونه ستاره باشه، چون ستاره مشهور هیچ کس رو نمیشناسه) اگه نشناسه دومی حذف میشه (چون ستاره مشهور رو همه میشناسن). پس در هر صورت یکی حذف میشه یکی باقی میمونه. حالا کار رو با نفر باقی مونده و نفر سوم انجام میدیم و به همین ترتیب یکی دیگه حذف میشه. اگه تا آخر لیست پیش بریم با n-1 تا سؤال همه بجز یکی حذف میشن. تا جایی که میدونم توی مسأله ستاره مشهور ما نمیدونیم که توی شهر ستاره مشهور هست یا نه. یعنی خودمون باید مطمئن بشیم. در این صورت باید نفر آخر رو کاملاً تست کرد. یعنی از همه افراد بپرسیم که آیا اونو میشناسن یا نه. و همین مطمئن بشیم که اون هیچ کس رو نمیشناسه. در اینصورت حد اکرثر 3n-3 تا سؤال مجبوریم بپرسیم.
این مساله رو میشه تنها با دو سوال حل کرد.
از نفر اول میپرسیم ستاره رو میشناسی
میگه بله. میگیم خوب اون کیه؟ یا میگه منم یا میگه اونه!
در واقع ما دونوع سوال پرسیدیم تا زودتر به جواب برسیم.
یعنی هر کسی دارای 2 متغیره
یک متغیر boolean
و یک integer
در اولی ستاره بودن و در دومی شماره مربوط به ستاره
این جزیی از صورت مسئله است.نقل قول:
ما مجاز هستیم که از نفری مثل A بپرسیم که آیا B را میشناسد یا نه ؟
حالا شما میگین که :
جالبه :متفکر:نقل قول:
این مساله رو میشه تنها با دو سوال حل کرد.
از نفر اول میپرسیم ستاره رو میشناسی
میگه بله. میگیم خوب اون کیه؟ یا میگه منم یا میگه اونه!