(۲۵ بهمن ۱۳۹۲ ۰۹:۱۰ ب.ظ)kh.jafarzade نوشته شده توسط:این که نشد روش حل دوست عزیز :دی(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
گزینه ۳
روش من:
شما ۳ گره کامل و همبندو در نظر بگیرید ...ما میدونیم که یکی از روشهای تشخیص ۲بخشی بودن اینه که بتونیم با ۲تا رنگ به شکل سازگار(ارضای محدودیت) رنگ آمیزی بشن و ازونجایی که این اتفاق نمیوفته این گزینه قطعا غلطه.
شما یه حالت خاص رو مثال میزنی بعد میگی نمیتونه باشه ؟؟؟
چون گفته گراف «میتواند» ۲ بخشی باشه حرف شما غلطه. اگه گفته بود گراف «حتمن» ۲ بخشیه حرفتون درست بود.
۳ تا گره که به صورت ۸ به هم وصل شدن رو در نظر بگیرین. هم ۲ بخشیه هم فرض سوال رو داره :دی
(۲۵ بهمن ۱۳۹۲ ۰۷:۳۹ ب.ظ)Amoojan نوشته شده توسط: اون سوالی که گفته میخوایم a میانه باشه و kتا عدد از ارایه داشته باشیم که نصفشون کوچکتر و نصفشون بزرگتر از a باشند،میشه از مرتبه n.
روی آرایه با a یک پارتیشن میزنیم. اعداد قبل a از اون کوچیکترند و بعد از اون بزرگتر. البته ترتیبشون درست نیست! که صورت سوال هم اینو نخواسته.
حالا شما k/2 از قبل و k/2از بعد a انتخاب میکنی که a میشه میانه و مرتبه زمانی هم میشه n.
موافقم و منم با همین استدلال زدم n
(۲۵ بهمن ۱۳۹۲ ۰۶:۴۱ ب.ظ)mrdudu نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی
این سوال همون الگوریتم های زمانبدی ریال تایم بود :یییییی
اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم
td-ti
ti زمان پردازش
td زمانی که باید تموم بشه
این سوال گزینه هیچکدام هم داشت. که به نظرم درست بود. این الگوریتم شبیه HRRN تو سیستم عامل بود، همون فرمول رو می خواست فکر کنم
(۲۵ بهمن ۱۳۹۲ ۰۷:۳۹ ب.ظ)Amoojan نوشته شده توسط: اون سوالی که گفته میخوایم a میانه باشه و kتا عدد از ارایه داشته باشیم که نصفشون کوچکتر و نصفشون بزرگتر از a باشند،میشه از مرتبه n.استدلال شما درسته ولی K رو N/2 در نظر بگیرید
روی آرایه با a یک پارتیشن میزنیم. اعداد قبل a از اون کوچیکترند و بعد از اون بزرگتر. البته ترتیبشون درست نیست! که صورت سوال هم اینو نخواسته.
حالا شما k/2 از قبل و k/2از بعد a انتخاب میکنی که a میشه میانه و مرتبه زمانی هم میشه n.
حالا باید N/2 تا عنصر نزدیک به میانگین رو چک کنیم هر بار O(n) و جمعا" O(n^2 میشه
به نظر من باید O(nk) باشه
(۲۵ بهمن ۱۳۹۲ ۱۰:۲۲ ب.ظ)mehdi1902 نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۹:۱۰ ب.ظ)kh.jafarzade نوشته شده توسط:این که نشد روش حل دوست عزیز :دی(25 بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
گزینه ۳
روش من:
شما ۳ گره کامل و همبندو در نظر بگیرید ...ما میدونیم که یکی از روشهای تشخیص ۲بخشی بودن اینه که بتونیم با ۲تا رنگ به شکل سازگار(ارضای محدودیت) رنگ آمیزی بشن و ازونجایی که این اتفاق نمیوفته این گزینه قطعا غلطه.
شما یه حالت خاص رو مثال میزنی بعد میگی نمیتونه باشه ؟؟؟
چون گفته گراف «میتواند» ۲ بخشی باشه حرف شما غلطه. اگه گفته بود گراف «حتمن» ۲ بخشیه حرفتون درست بود.
۳ تا گره که به صورت ۸ به هم وصل شدن رو در نظر بگیرین. هم ۲ بخشیه هم فرض سوال رو داره :دی
%۱۰۰ گزینه ۴ میشه چون فقط این گفته حتما، گزینه ۱و۳ گفته میتواند..
اینم مثال نقض گزینه ۴
[attachment=15427]اینو چی زدین؟؟
(۲۵ بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم
بهترین حالت log n من حساب کردم. خودتون برای مثلا ۴ یا ۸ مثال بزنید در میاد. و این حالتیه که دو تا دو تا اعداد را با هم جمع کنیم. بدترینشم هر چی فکر کردم احساس کردم nlognخیلی زیاد میشه و در نمیاد زدم n !!! استدلال از این محکم تر؟!!
(۲۶ بهمن ۱۳۹۲ ۰۸:۵۶ ق.ظ)alagh نوشته شده توسط: اینو چی زدین؟؟
یه سوالی هست کنکور۸۵ مطرح شده
که t درخت فراگیر کمینه یک گراف است. اگر وزن یک یال را در گراف کاهش دهیم با چه مرتبه ای می توان درخت کمینه را پیدا کرد.
به نظرم شبیه همون سواله.
دقیقا گزینه هاش همیناست و جواب از مرتبه V را زده
(۲۶ بهمن ۱۳۹۲ ۰۸:۵۶ ق.ظ)alagh نوشته شده توسط: اینو چی زدین؟؟این سوال تکراری هست. میشه از مرتبه V .
(۲۶ بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)cse.abdali نوشته شده توسط:بهترین حالت رو چطوری حساب کردین؟!(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم
بهترین حالت log n من حساب کردم. خودتون برای مثلا ۴ یا ۸ مثال بزنید در میاد. و این حالتیه که دو تا دو تا اعداد را با هم جمع کنیم. بدترینشم هر چی فکر کردم احساس کردم nlognخیلی زیاد میشه و در نمیاد زدم n !!! استدلال از این محکم تر؟!!
من هرجوری حساب میکنم nمیشه... هم بهترین هم بدترین...
(۲۶ بهمن ۱۳۹۲ ۰۱:۲۲ ق.ظ)E.SH نوشته شده توسط: استدلال شما درسته ولی K رو N/2 در نظر بگیریدمن منظورتون از اینکه باید n/2 تا عنصر رو چک کنیم نمیفهمم. بیشتر توضیح میدین؟
حالا باید N/2 تا عنصر نزدیک به میانگین رو چک کنیم هر بار O(n) و جمعا" O(n^2 میشه
به نظر من باید O(nk) باشه
شما پارتیشن رو که زدی اندیس a (مثلا i)رو که داری. میگی از i-k/2 تا i+k/2 میشه جواب طراح محترم!
(۲۶ بهمن ۱۳۹۲ ۱۱:۲۴ ق.ظ)AI. نوشته شده توسط:(26 بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)cse.abdali نوشته شده توسط: یه سوالی هست کنکور۸۵ مطرح شده
که t درخت فراگیر کمینه یک گراف است. اگر وزن یک یال را در گراف کاهش دهیم با چه مرتبه ای می توان درخت کمینه را پیدا کرد.
به نظرم شبیه همون سواله.
دقیقا گزینه هاش همیناست و جواب از مرتبه V را زده
درسته ظاهرن شبیه هستند، اما کاملا متفاوت.
مسئله اینه که ما نمی دونیم چه یالی با چه وزنی و به کجای درخت اضافه شده!
فکر میکنم باید مراحل ساخت درخت پوشا رو طی کنیم با یکی از الگوریتم ها
که چون تعداد یال ها کمه، کراسکال با مرتبه E Log V احتمالا پاسخ هست.
فرقی ندارن!!! ما توی اون سوال هم نمیدونم یال کجا اضافه شده! همون V میشه! دقیقا سوالا عین همن و با پیمایش درخت میشه به نتیجه رسید
(۲۵ بهمن ۱۳۹۲ ۰۳:۳۶ ب.ظ)hosein_khoshdel نوشته شده توسط: الان چرا هیشکی به جواب من توجه نمی کنه؟
گزینه ی ۴ غلطه حالا شاید ۲ هم غلط باشه نمی دونم ولی ۴ صد در صد غلطه.به شکل پست قبلیم نیگا کنید.
این سوال غلط است
چون که هم گزینه دو و هم چهار غلط است مثال نقض برای گزینه دو...(۲۶ بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)cse.abdali نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- اعداد رو میخواست جمع کنه. n عدد ۱ بیتی
من بهترین رو n بدترین رو هم nlgn زدم
بهترین حالت log n من حساب کردم. خودتون برای مثلا ۴ یا ۸ مثال بزنید در میاد. و این حالتیه که دو تا دو تا اعداد را با هم جمع کنیم. بدترینشم هر چی فکر کردم احساس کردم nlognخیلی زیاد میشه و در نمیاد زدم n !!! استدلال از این محکم تر؟!!
(۲۶ بهمن ۱۳۹۲ ۰۸:۵۶ ق.ظ)alagh نوشته شده توسط: اینو چی زدین؟؟
یه سوالی هست کنکور۸۵ مطرح شده
که t درخت فراگیر کمینه یک گراف است. اگر وزن یک یال را در گراف کاهش دهیم با چه مرتبه ای می توان درخت کمینه را پیدا کرد.
به نظرم شبیه همون سواله.
دقیقا گزینه هاش همیناست و جواب از مرتبه V را زده
با مرتبه o(v) میشه فهمید ایا این یال از بزرگترین یال کوچکتر است یا نه اگز کوچکتر بود کافی است این یال را اضافه کنیم که با این کار مسلما دور تشکیل می شود که وجود دور را میشه با مرتبه o)e+v) فهمید که چون درخت اس از مرتبه v می شود و بعد بزرگتری یال در این دور را حذف می کنیم پس جواب می شود از مرتبه v می شود.
(۲۶ بهمن ۱۳۹۲ ۰۷:۵۱ ب.ظ)ahad_kr نوشته شده توسط: با مرتبه o(v) میشه فهمید ایا این یال از بزرگترین یال کوچکتر است یا نه اگز کوچکتر بود کافی است این یال را اضافه کنیم که با این کار مسلما دور تشکیل می شود که وجود دور را میشه با مرتبه o)e+v) فهمید که چون درخت اس از مرتبه v می شود و بعد بزرگتری یال در این دور را حذف می کنیم پس جواب می شود از مرتبه v می شود.
حق باشماست
(۲۵ بهمن ۱۳۹۲ ۰۲:۳۵ ب.ظ)mahtab69 نوشته شده توسط: سوال ۱۱۲) اگر در یک گراف همبند Dfs=Bfs باشه کدام گزینه غلط بود؟؟؟
۱)گراف میتواند کامل باشد
۲)قطر گراف حداکثر ۲ هست
۳)گراف میتواند ۲بخشی کامل باشد
۴)گراف حتما یا درخت است یا گراف کامل
گزینه ۲ میشه
بچه ها پارسه سوال ۱۱۲ پَ چیکا اینجوری حل کرده؟؟؟
سوال کی گفته حتما هر گراف کاملی dfs و bfs اون با هم برابرن!!! گفته G میتواند کامل باشه!!!
(۲۵ بهمن ۱۳۹۲ ۰۶:۴۱ ب.ظ)mrdudu نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی
این سوال همون الگوریتم های زمانبدی ریال تایم بود :یییییی
اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم
td-ti
ti زمان پردازش
td زمانی که باید تموم بشه
من واسه این سوال نزدیک ده تا نمونه تست کردم و برای همشون حداقل دوتا مثال نقض آوردم. ۹۹درصد گزینه ۴ میشه. پارسه هم گزینه ۴ رو زدده.
(۲۹ بهمن ۱۳۹۲ ۱۱:۲۳ ب.ظ)mehrdad4all نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۶:۴۱ ب.ظ)mrdudu نوشته شده توسط:(25 بهمن ۱۳۹۲ ۰۴:۳۳ ب.ظ)mehdi1902 نوشته شده توسط: توی سوالات الگوریتم این چن تا سوال رو کسی نظری داره ؟؟
- سوالی که جریمه داشت هر کاری
من خودم اون رو زدم که ti-td داشت :-؟ :-اس
من این سوال رو دیدم تعجب کردم چرا سیستم عامل دادن :ی
این سوال همون الگوریتم های زمانبدی ریال تایم بود :یییییی
اگر اشتباه نکنم باید لکستی تایم رو به دست می اوردیم به ترتیب اونی که کوچیکتر رو انجام میدادیم
td-ti
ti زمان پردازش
td زمانی که باید تموم بشه
من واسه این سوال نزدیک ده تا نمونه تست کردم و برای همشون حداقل دوتا مثال نقض آوردم. ۹۹درصد گزینه ۴ میشه. پارسه هم گزینه ۴ رو زدده.
گزینه ۴ هیچکدامه؟