سلام،گل گفتید،منم قبلا همین حرفو زدم ولی کسی نتونست قانعم کنه

تو پرانتز چرا نوشته بهترین حالت؟

(۱۹ دى ۱۳۹۳ ۰۸:۳۱ ب.ظ)Aurora نوشته شده توسط:  تو پرانتز چرا نوشته بهترین حالت؟

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

خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟

(۱۹ دى ۱۳۹۳ ۰۸:۳۵ ب.ظ)miladcr7 نوشته شده توسط:  خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟

خوب در این صورت ایا نابغه پیدا میشه؟ اگر همه در یگ گروه باشن فقط می دونیم که نابغه در اون گروه هست یا نه ولی نمی دونیم نابغه کیه.

سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدن

(۱۹ دى ۱۳۹۳ ۰۸:۴۱ ب.ظ)miladcr7 نوشته شده توسط:  سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدن

بله اگر فقط دونستن اینکه نابغه تو گروه هست یا نه، کفایت کنه حرف شما درسته. ولی اگر بخواد نابغه رو پیدا کنه نه.

(۱۹ دى ۱۳۹۳ ۰۸:۴۳ ب.ظ)Aurora نوشته شده توسط:  

(19 دى ۱۳۹۳ ۰۸:۴۱ ب.ظ)miladcr7 نوشته شده توسط:  سوال گفته وقتی ما از گروه میپرسیم نابغه توی گروه شماست یا نه اونا هم پاسخ بله و خیر میدن

بله اگر فقط دونستن اینکه نابغه تو گروه هست یا نه، کفایت کنه حرف شما درسته. ولی اگر بخواد نابغه رو پیدا کنه نه.

نه فک کنم حق با شماست!!!میخوایم پیداش کنیم
عجب سوالایی

با این وضع حتما باید k یک باشه تا خود نابغه پیدا شه، چون توو گروه فقط جواب بله میگیریم و تمام
امان از سوالای علوم

---

(۱۹ دى ۱۳۹۳ ۰۸:۳۵ ب.ظ)miladcr7 نوشته شده توسط:  خب بهترین روش این نیست که k=n باشه و همه دانشجوها تو یه گروه باشن؟؟؟

خب اون بهترین حالتشه که با یه بار پرسش کشف میشه،ما بدترین حالتو میخایم
بدترین حالته بهترین روش :-D چه استدلالی کنیم سر کنکور

یه توضیح درباره روشش میدید؟؟؟

این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.

(۱۹ دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط:  این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.

حالا به نظرتون چرا این n/2 میشه بدترین حالت؟؟؟؟

(۱۹ دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط:  این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.

درسته جواب همینه
ما دنبال بدترین مرتبه ی بهترین راه حل می گردیم
هر دفعه جمعیت رو نصف می کنیم از نصفیشون می پرسیم اگه گفت بله که همونو دوباره نصف می کنیم اگه گفت نه که می ریم اون یکی گروه و نصف می کنیم. n/2 نمی شه که
می شه logn
و می خواهیم خود فرد نابغه رو پیدا کنیم نه گروهشو

(۲۰ دى ۱۳۹۳ ۱۲:۱۹ ق.ظ)fatemeh69 نوشته شده توسط:  

(19 دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط:  این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.

درسته جواب همینه
ما دنبال بدترین مرتبه ی بهترین راه حل می گردیم
هر دفعه جمعیت رو نصف می کنیم از نصفیشون می پرسیم اگه گفت بله که همونو دوباره نصف می کنیم اگه گفت نه که می ریم اون یکی گروه و نصف می کنیم. n/2 نمی شه که
می شه logn
و می خواهیم خود فرد نابغه رو پیدا کنیم نه گروهشو

چرا n/3 نه???یا یه تقسیم دیگه؟؟؟؟

(۲۰ دى ۱۳۹۳ ۱۲:۲۱ ق.ظ)miladcr7 نوشته شده توسط:  چرا n/3 نه???یا یه تقسیم دیگه؟؟؟؟

فرقی نداره شما هر دفعه اگه به m قسمت هم تقسیم کنید جواب می شه logn در مبنای m که مبناها تو پیچیدگی تاثیر ندارن

(۲۰ دى ۱۳۹۳ ۱۲:۲۸ ق.ظ)fatemeh69 نوشته شده توسط:  

(20 دى ۱۳۹۳ ۱۲:۲۱ ق.ظ)miladcr7 نوشته شده توسط:  چرا n/3 نه???یا یه تقسیم دیگه؟؟؟؟

فرقی نداره شما هر دفعه اگه به m قسمت هم تقسیم کنید جواب می شه logn در مبنای m که مبناها تو پیچیدگی تاثیر ندارن

اها درسته به اینش دقت نکرده بودم!!!!!ممنونم

اگر بیایم مثل افراز باهاش برخورد کنیم چی؟
افراز به دو مجموعه،یکی اون دسته ای که برمیداریم و ازش سوال میکنیم،یکی اون دسته که باقی میمونه،سه حالت همیشگیمونو میبینیم،وقتی افرازمون n به صفر بشه و اولین بار بله میگیریم و میشه بهترین حالت، یبار افرازامون هی نصف نصف میشه که حالت متوسطه، یبارم افرازمون هی ۱ به n-1 میشه که بدترین حالتشم وقتیه که اون جناب دسته اخر باشه، با این حساب جواب حالت متوسطو گفته؟