(۰۲ اسفند ۱۳۸۹ ۰۴:۳۵ ب.ظ)ramezanpour.r نوشته شده توسط:(02 اسفند ۱۳۸۹ ۰۴:۰۳ ب.ظ)khoofi66 نوشته شده توسط: نظر من درباره سوال ۳۴:منم سر جلسه مثال زدم و log n رو زدم
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه
ولی مثال زیر رو حل کن
A[1]=3
A[2]=1
A[3]=2
حق با شماست پس گزینه ۱ باید درست باشه
منم دقیقاً سر امتحان همین آرایه را مثال زدم و در حلقه افتادم
(۰۲ اسفند ۱۳۸۹ ۰۴:۱۰ ب.ظ)psps1368 نوشته شده توسط:نه گزاره درسته چون گفته حتما دو راس وجود دارد توی همون مثلث هم این دو راس وجود دارد وگرنه اصلا اون یال جزو درخت نمیشد.(02 اسفند ۱۳۸۹ ۰۳:۳۹ ب.ظ)hatami84 نوشته شده توسط: سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن
درسته، نمی دونم چرا فرض کردم که گراف وزن هاش متفاوته...
ان شاا... که دومی و سوی درستند....
ویرایش: میشه یه مقدار توضیح بدی، آخه گفته حتما دو راسی وجود خواهند داشت، یعنی تو مثال شما هیچ دو راسی وجود ندارند؟
البته اثبات من که کاملا غلطه....
گزاره بعدی رو من زدم غلط
گزاره سوم رو زدم درست
منم خودم الان که چک کردم دیدم با این مثال جواب نمیده پس فعلاً در مورد درست و غلطی این سوال نظر نمیدم
(۰۲ اسفند ۱۳۸۹ ۰۴:۱۰ ب.ظ)psps1368 نوشته شده توسط:(02 اسفند ۱۳۸۹ ۰۳:۳۹ ب.ظ)hatami84 نوشته شده توسط: سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن
درسته، نمی دونم چرا فرض کردم که گراف وزن هاش متفاوته...
ان شاا... که دومی و سوی درستند....
ویرایش: میشه یه مقدار توضیح بدی، آخه گفته حتما دو راسی وجود خواهند داشت، یعنی تو مثال شما هیچ دو راسی وجود ندارند؟
البته اثبات من که کاملا غلطه....
حتی اگر یال های تکراری هم وجود داشته باشه، باز هم اگر یال e به عنوان یال کمینه انتخاب شود، دو راسی که یال e را به وجود می آورند(u,v) ،کوتاه ترین مسیر بین راس u,v همان یال e است که انتخاب می شود.
سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه
سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم
سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش
۳۵ رو نزدم
گزینه های احتمالی:
۳۱: ۳
۳۲: ۱
۳۳: ۲
۳۴: ۴
۳۵: ۲
آقای تنهایی میشه نظرتون رو در مورد سوال ۳۳ و ۳۴ بگین.
با تشکر
(۰۳ اسفند ۱۳۸۹ ۰۱:۰۰ ق.ظ)موج نوشته شده توسط: سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه
سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم
سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش
۳۵ رو نزدم
۳۲ گزاره وسط درست هم میشه!!!! شما فرض کنید از الگوریتم کراسکال بریم واسه این کار! همون طور که می دونید این الگوریم از o(v2) هست حالا فرض کنید گراف کامل باشه و o(e)=o(v2) پس می بینید که شدنیه! ما اگه از bfs واسه این کار بریم میشه از o(e+v)اما همون طور که گفتم با کروسکال و گراف کامل هم باشه میشه.
آره وسطی هم درسته.
چون گراف بیجهت هست در زمان v+e میشه مساله رو حل کرد.
حالا چون همبنده پس تعداد یالها از راسها همیشه بیشتره و در زمان eمیشه حلش کرد.
ولی به نظر من سوال ۳۲ همون گزینه ۱ درسته!
استدلال هم دوستان آوردن به جای ما!
سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)
الگوریتمش خیلی پیچیدهاست و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!
راهنمایی: هر بار میانه دو لیست رو میگیریم و با هم مقایسه میکنیم اگه میانه یکی بزرگتر از دیگری بود میانهشو دوباره میگیریم!
بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان میبره. سوال فوق العاده زیبایی است این سوال.
سوال ۳۲ گزینه یک در کتاب طراحی الگوریتم ارشد سپاهان گفته غلطه. صفحه شو دقیق براتون میگم.
سوال ۳۳ به نظر من ابتدا اجتماع را در lgn پیدا میکنیم سپس در lgn ما k امین عنصر را مییابیم جمع اینا میشه lgn.
۳۴- کد تموم نمیشه
۳۵- n به توان دو میشه.
(۰۳ اسفند ۱۳۸۹ ۰۱:۲۴ ب.ظ)www نوشته شده توسط: سوال ۳۲ گزینه یک در کتاب طراحی الگوریتم ارشد سپاهان گفته غلطه. صفحه شو دقیق براتون میگم.
سوال ۳۳ به نظر من ابتدا اجتماع را در lgn پیدا میکنیم سپس در lgn ما k امین عنصر را مییابیم جمع اینا میشه lgn.
۳۴- کد تموم نمیشه
۳۵- n به توان دو میشه.
عزیزم نا سلامتی خود جناب تنهایی مدیر تالار دکترای این رشته رو دارن
اگه قرار باشه به سپاهان استناد کرد به نظر من استناد به حرف دکتر بهتره
سوال ۳۲ بخش الف گفته که حتما دو راس وجود دارد که ... شما اگه به نظرت غلطه یه مثال نقض بیار که هیچ دو راسی با این شرایط نباشه ما هم با تمام وجود میپذیریم
درمورد سوال ۳۳ من هم lgn زدم از خدامه که حرف تو درست باشه
۳۴ نظرم همینه
ولی من هنوز با اقای تنهایی مخالفم!!!!