نمایش نتایج 1 تا 11 از 11

نام تاپیک: مساله ستاره مشهور

  1. #1

    مساله ستاره مشهور

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

  2. #2
    کاربر دائمی آواتار golbafan
    تاریخ عضویت
    اردیبهشت 1388
    محل زندگی
    در قلب دوستان
    پست
    2,018

    نقل قول: مساله ستاره مشهور

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

  3. #3

    نقل قول: مساله ستاره مشهور

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

  4. #4

    نقل قول: مساله ستاره مشهور

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

  5. #5

    نقل قول: مساله ستاره مشهور

    نقل قول نوشته شده توسط obalitjoOon مشاهده تاپیک
    همه آقاي star رو مي شناسن. پس ما از اولين نفر سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت پس همين شخص star هستش و خاتمه، و اگر شناخت به متغير counter يا شمارنده 1 واحد اضافه كن. (اين متغير تعداد پرسش ها رو شمارش مي كنه).
    حالا نفر دوم دوباره ازش سوال مي كنيم كه star رو مي شناسه يا نه. اگر نشناخت اين شخص star هست و خاتمه، در غير اينصورت 1 واحد به متغير counter اضافه كن و برو به نفر بعدي.
    ....
    عبارت "ْآيا Star رو ميشناسه؟" اشتباهه. چون در ابتدا Star وجود نداره، وظيفه شماست كه اون رو پيدا كنيد.

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



  6. #6

    نقل قول: مساله ستاره مشهور

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



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

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


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

  7. #7

    نقل قول: مساله ستاره مشهور

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

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



  8. #8

    نقل قول: مساله ستاره مشهور

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

  9. #9
    کاربر تازه وارد
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    سن
    34
    پست
    32

    نقل قول: مساله ستاره مشهور

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

  10. #10
    کاربر دائمی آواتار golbafan
    تاریخ عضویت
    اردیبهشت 1388
    محل زندگی
    در قلب دوستان
    پست
    2,018

    نقل قول: مساله ستاره مشهور

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

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

  11. #11

    Talking نقل قول: مساله ستاره مشهور

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

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

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •