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

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

  1. #1
    کاربر دائمی آواتار Shabani.Mojtaba
    تاریخ عضویت
    آبان 1383
    محل زندگی
    اهواز
    پست
    101
    تشکر کردن
    15
    7 بار تشکر شده در 6 پست

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

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

    shabani.mojtaba@gmail.com
    irdev.info@gmail.com

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

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

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

  3. #3
    کاربر دائمی آواتار Shabani.Mojtaba
    تاریخ عضویت
    آبان 1383
    محل زندگی
    اهواز
    پست
    101
    تشکر کردن
    15
    7 بار تشکر شده در 6 پست

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

    نه
    تنها کسی که مشهور است همان ستاره است.
    مجتبی شعبانی mojtaba shabani

    shabani.mojtaba@gmail.com
    irdev.info@gmail.com

  4. #4
    کاربر دائمی آواتار اوبالیت به بو
    تاریخ عضویت
    مهر 1386
    محل زندگی
    تهران
    سن
    24
    پست
    2,259
    تشکر کردن
    554
    3,241 بار تشکر شده در 683 پست

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

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

  5. #5
    VIP آواتار Mbt925
    تاریخ عضویت
    فروردین 1387
    پست
    2,249
    تشکر کردن
    1,153
    6,832 بار تشکر شده در 1,143 پست

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

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

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



  6. #6
    کاربر دائمی آواتار Armin060
    تاریخ عضویت
    مهر 1387
    سن
    18
    پست
    510
    تشکر کردن
    252
    121 بار تشکر شده در 107 پست

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

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



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

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


    چرا اينقدر طولانی!؟
    اگر "از همه افراد (ديگه)" رو حذف می كرديد بهتر بود. كسی‌ كس ديگری‌ رو ( به جز ستاره ) نمی شناسه. از همون نفر اول كه پرسيدی اگر گفت بله كه معلومه فرد L ستاره هست و اگر گفت خير ميره سراغ فرد بعدی.
    آخرین ویرایش به وسیله Armin060 : پنجشنبه 04 تیر 1388 در 00:20 قبل از ظهر
    Im trying ^ n for things that I really want

  7. #7
    VIP آواتار Mbt925
    تاریخ عضویت
    فروردین 1387
    پست
    2,249
    تشکر کردن
    1,153
    6,832 بار تشکر شده در 1,143 پست

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

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

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



  8. #8
    کاربر دائمی آواتار Armin060
    تاریخ عضویت
    مهر 1387
    سن
    18
    پست
    510
    تشکر کردن
    252
    121 بار تشکر شده در 107 پست

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

    اگر به پست های بعدی نگاه می كردی می فهميدی.
    Im trying ^ n for things that I really want

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

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

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

  10. کاربرانی که به خاطر مطلب مفید newamir از وی تشکر کرده‌اند:


  11. #10
    کاربر دائمی آواتار golbafan
    تاریخ عضویت
    اردیبهشت 1388
    محل زندگی
    اولین عدد آخر
    پست
    320
    تشکر کردن
    50
    185 بار تشکر شده در 82 پست

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

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

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

  12. #11
    کاربر دائمی آواتار Shabani.Mojtaba
    تاریخ عضویت
    آبان 1383
    محل زندگی
    اهواز
    پست
    101
    تشکر کردن
    15
    7 بار تشکر شده در 6 پست

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

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

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

    shabani.mojtaba@gmail.com
    irdev.info@gmail.com

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

بوک مارک کردن این تاپیک

بوک مارک کردن این تاپیک

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

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