مساله ستاره مشهور [بایگانی]

Shabani.Mojtaba

دوشنبه 25 خرداد 1388, 16:26 عصر

مساله ستاره مشهور :
فرض کنید که n نفر دارید و در بین این n نفر یک نفر به عنوان ستاره می باشد. ستاره کسی است که همه او را از قبل می شناسند ولی او کسی را نمی شناسد .
میخواهیم با حداقل تعداد پرسش از این n نفر ستاره را بشناسیم.
ما مجاز هستیم که از نفری مثل A بپرسیم که آیا B را میشناسد یا نه ؟
الگوریتم حریسانه این مسأله را ارائه دهید.

golbafan

دوشنبه 25 خرداد 1388, 19:42 عصر

بگید ببینم ایا غیر از ستاره همه همدیگر را میشناسند؟

Shabani.Mojtaba

سه شنبه 26 خرداد 1388, 17:09 عصر

نه
تنها کسی که مشهور است همان ستاره است.

اوبالیت به بو

پنج شنبه 28 خرداد 1388, 14:38 عصر

بگید ببینم ایا غیر از ستاره همه همدیگر را میشناسند؟
نه
تنها کسی که مشهور است همان ستاره است.

همه آقاي star رو مي شناسن. پس ما از اولين نفر سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت پس همين شخص star هستش و خاتمه، و اگر شناخت به متغير counter يا شمارنده 1 واحد اضافه كن. (اين متغير تعداد پرسش ها رو شمارش مي كنه).
حالا نفر دوم دوباره ازش سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت اين شخص star هست و خاتمه، در غير اينصورت 1 واحد به متغير counter اضافه كن و برو به نفر بعدي.
....

Mbt925

دوشنبه 01 تیر 1388, 16:25 عصر

همه آقاي star رو مي شناسن. پس ما از اولين نفر سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت پس همين شخص star هستش و خاتمه، و اگر شناخت به متغير counter يا شمارنده 1 واحد اضافه كن. (اين متغير تعداد پرسش ها رو شمارش مي كنه).
حالا نفر دوم دوباره ازش سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت اين شخص star هست و خاتمه، در غير اينصورت 1 واحد به متغير counter اضافه كن و برو به نفر بعدي.
....

عبارت "ْآيا Star رو ميشناسه؟" اشتباهه. چون در ابتدا Star وجود نداره، وظيفه شماست كه اون رو پيدا كنيد.

فرض مي كنيم شما يه ليست حاوي n نفر داريد:

n1,n2,n3,n4,n5,...
در ابتدا يه ليست از همه افراد تهيه مي كنيم.
براي هر يك افراد موجود در ليست مثلا فرد L
از همه افراد (ديگه) مي پرسيم كه آيا اين فرد رو مي شناسن يا نه. در صورتي كه همه مي شناختنش، فرد Star ،L هست و در غير اينصورت به سراغ فرد بعدي ميريم.

Armin060

چهارشنبه 03 تیر 1388, 20:53 عصر

در ابتدا يه ليست از همه افراد تهيه مي كنيم.

براي هر يك افراد موجود در ليست مثلا فرد L

از همه افراد (ديگه) مي پرسيم كه آيا اين فرد رو مي شناسن يا نه. در صورتي كه همه مي شناختنش، فرد Star ،L هست و در غير اينصورت به سراغ فرد بعدي ميريم.

چرا اينقدر طولانی!؟
اگر "از همه افراد (ديگه)" رو حذف می كرديد بهتر بود. كسی‌ كس ديگری‌ رو ( به جز ستاره ) نمی شناسه. از همون نفر اول كه پرسيدی اگر گفت بله كه معلومه فرد L ستاره هست و اگر گفت خير ميره سراغ فرد بعدی.

Mbt925

پنج شنبه 04 تیر 1388, 10:19 صبح

چرا اينقدر طولانی!؟
اگر "از همه افراد (ديگه)" رو حذف می كرديد بهتر بود. كسی‌ كس ديگری‌ رو ( به جز ستاره ) نمی شناسه. از همون نفر اول كه پرسيدی اگر گفت بله كه معلومه فرد L ستاره هست و اگر گفت خير ميره سراغ فرد بعدی.

طبق صورت سوال که در پست اول ذکر شده، گفته شده Star رو همه میشناسن
نه اینکه هیچ کس، غیر از Star رو نمیشناسه.

بنابراین راه حل حریصانه همونیه که در بالا گفتم.

Armin060

پنج شنبه 04 تیر 1388, 18:19 عصر

اگر به پست های بعدی نگاه می كردی می فهميدی.

newamir

جمعه 05 تیر 1388, 17:18 عصر

این مسأله در اصل برای یک گراف طرح میشه: اگر در یک گراف جهت دار، همه رأسها به یک رأس یال داشته باشند ولی آن رأس به هیچ کدام از بقیه رئوس یالی نداشته باشد، آن رأس را ستاره مشهور مینامیم. با این فرض که ماتریس مجاورت یک گراف داده شده باشد ستاره مشهور آن را پیدا کنید. در واقع پرسیدن سؤال مثل چک کردن این است که خانه i , j ماتریس مجاورت صفر است یا یک. فکر میکنم با این انتزاع، روشن شده باشه که پرسیدن "آیا ستاره را میشناسی" درست نیست. راه حل Mbt925 درسته. ولی درواقع O(n^2) زمان میگیره در صورتی که میشه با n تا پرسش کار رو تموم کرد. فرض کنید افراد رو شماره گذاری کردیم. از یک تا n. حالا از اولی میپرسیم که آیا دومی رو میشناسه یا نه. اگه بشناسه اولی حذف میشه (یعنی نمیتونه ستاره باشه، چون ستاره مشهور هیچ کس رو نمیشناسه) اگه نشناسه دومی حذف میشه (چون ستاره مشهور رو همه میشناسن). پس در هر صورت یکی حذف میشه یکی باقی میمونه. حالا کار رو با نفر باقی مونده و نفر سوم انجام میدیم و به همین ترتیب یکی دیگه حذف میشه. اگه تا آخر لیست پیش بریم با n-1 تا سؤال همه بجز یکی حذف میشن. تا جایی که میدونم توی مسأله ستاره مشهور ما نمیدونیم که توی شهر ستاره مشهور هست یا نه. یعنی خودمون باید مطمئن بشیم. در این صورت باید نفر آخر رو کاملاً تست کرد. یعنی از همه افراد بپرسیم که آیا اونو میشناسن یا نه. و همین مطمئن بشیم که اون هیچ کس رو نمیشناسه. در اینصورت حد اکرثر 3n-3 تا سؤال مجبوریم بپرسیم.

golbafan

جمعه 03 دی 1389, 07:03 صبح

این مساله رو میشه تنها با دو سوال حل کرد.
از نفر اول میپرسیم ستاره رو میشناسی
میگه بله. میگیم خوب اون کیه؟ یا میگه منم یا میگه اونه!

در واقع ما دونوع سوال پرسیدیم تا زودتر به جواب برسیم.
یعنی هر کسی دارای 2 متغیره
یک متغیر boolean
و یک integer
در اولی ستاره بودن و در دومی شماره مربوط به ستاره

Shabani.Mojtaba

شنبه 11 دی 1389, 21:41 عصر

ما مجاز هستیم که از نفری مثل A بپرسیم که آیا B را میشناسد یا نه ؟

این جزیی از صورت مسئله است.

حالا شما میگین که :

این مساله رو میشه تنها با دو سوال حل کرد.
از نفر اول میپرسیم ستاره رو میشناسی
میگه بله. میگیم خوب اون کیه؟ یا میگه منم یا میگه اونه!

جالبه :متفکر: