صفحه‌ها: ۱ ۲
سلام!!!دوستان توی این سوال بدترین مرتبه رو خواسته!حالا سوالم اینه چرا لگاریتمی انتخاب کردن دانشجوها میشه بدترین ؟؟
خب بیایم k رو یک انتخاب کنیم که بدترین حالت به دست بیاد و اونوقت در بدترین حالت باید n تا پرسش انجام بدیم!!!میشه یکی توضیح بده اینو
![[تصویر: 325915_zv57aunplwd2ihp0or4j.jpg]](https://img.manesht.ir/325915_zv57aunplwd2ihp0or4j.jpg)
سلام،گل گفتید،منم قبلا همین حرفو زدم ولی کسی نتونست قانعم کنه
تو پرانتز چرا نوشته بهترین حالت؟
(۱۹ دى ۱۳۹۳ ۰۸:۳۱ ب.ظ)Aurora نوشته شده توسط: تو پرانتز چرا نوشته بهترین حالت؟حدس من اینه پرانتز میخواسته بگه بدترین حالته بهترین روش!
خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟
(۱۹ دى ۱۳۹۳ ۰۸:۳۵ ب.ظ)miladcr7 نوشته شده توسط: خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟
خوب در این صورت ایا نابغه پیدا میشه؟ اگر همه در یگ گروه باشن فقط می دونیم که نابغه در اون گروه هست یا نه ولی نمی دونیم نابغه کیه.
سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدن
(۱۹ دى ۱۳۹۳ ۰۸:۴۱ ب.ظ)miladcr7 نوشته شده توسط: سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدنبله اگر فقط دونستن اینکه نابغه تو گروه هست یا نه، کفایت کنه حرف شما درسته. ولی اگر بخواد نابغه رو پیدا کنه نه.
(۱۹ دى ۱۳۹۳ ۰۸:۴۳ ب.ظ)Aurora نوشته شده توسط:(19 دى ۱۳۹۳ ۰۸:۴۱ ب.ظ)miladcr7 نوشته شده توسط: سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدنبله اگر فقط دونستن اینکه نابغه تو گروه هست یا نه، کفایت کنه حرف شما درسته. ولی اگر بخواد نابغه رو پیدا کنه نه.
نه فک کنم حق با شماست!!!میخوایم پیداش کنیم
عجب سوالایی
با این وضع حتما باید k یک باشه تا خود نابغه پیدا شه، چون توو گروه فقط جواب بله میگیریم و تمام
امان از سوالای علوم
(۱۹ دى ۱۳۹۳ ۰۸:۳۵ ب.ظ)miladcr7 نوشته شده توسط: خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟خب اون بهترین حالتشه که با یه بار پرسش کشف میشه،ما بدترین حالتو میخایم
بدترین حالته بهترین روش :-D چه استدلالی کنیم سر کنکور
یه توضیح درباره روشش میدید؟؟؟
این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.
اگر بیایم مثل افراز باهاش برخورد کنیم چی؟
افراز به دو مجموعه،یکی اون دسته ای که برمیداریم و ازش سوال میکنیم،یکی اون دسته که باقی میمونه،سه حالت همیشگیمونو میبینیم،وقتی افرازمون n به صفر بشه و اولین بار بله میگیریم و میشه بهترین حالت، یبار افرازامون هی نصف نصف میشه که حالت متوسطه، یبارم افرازمون هی ۱ به n-1 میشه که بدترین حالتشم وقتیه که اون جناب دسته اخر باشه، با این حساب جواب حالت متوسطو گفته؟
(۱۹ دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط: این جواب من نمی دونم درسته یا نه!حالا به نظرتون چرا این n/2 میشه بدترین حالت؟؟؟؟
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.
(۱۹ دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط: این جواب من نمی دونم درسته یا نه!درسته جواب همینه
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.
ما دنبال بدترین مرتبه ی بهترین راه حل می گردیم
هر دفعه جمعیت رو نصف می کنیم از نصفیشون می پرسیم اگه گفت بله که همونو دوباره نصف می کنیم اگه گفت نه که می ریم اون یکی گروه و نصف می کنیم. n/2 نمی شه که
می شه logn
و می خواهیم خود فرد نابغه رو پیدا کنیم نه گروهشو