انجمنصفحه اولجستجوی انجمن

[fatima1537]

من ۱۱۴ رو ۲ بدست اوردم.
۱۱۳ یکم شک برانگیزه.چون فکر کنم ۲ تا از جمله ها صحیح باشه یعنی میشه گزینه ۳ (ابلته من ۳ نزدم)-جمله اول که طبیعتا صحیحه.جمله سوم هم همینطور.جمله دوم یکم شک برانگیزه.چون توی جستجوی حبابی با یک دور مرتب سازی میشه متوجه شد عناصر مرتب هستند یانه.از طرفی کمترین مرتبه زمانی برای مرتب سازی nlogn هست.

[مهمد]

(۲۲ بهمن ۱۳۹۱ ۱۱:۵۳ ق.ظ)fatima1537 نوشته شده توسط:  من ۱۱۴ رو ۲ بدست اوردم.
۱۱۳ یکم شک برانگیزه.چون فکر کنم ۲ تا از جمله ها صحیح باشه یعنی میشه گزینه ۳ (ابلته من ۳ نزدم)-جمله اول که طبیعتا صحیحه.جمله سوم هم همینطور.جمله دوم یکم شک برانگیزه.چون توی جستجوی حبابی با یک دور مرتب سازی میشه متوجه شد عناصر مرتب هستند یانه.از طرفی کمترین مرتبه زمانی برای مرتب سازی nlogn هست.

سوال ۱۱۴ - شما با برداشتن n/2 صفر و n/3 یک هنوز متوجه نمیشید که کدوم گونه است. و باید یکی دیگه هم بردارید. پس جواب گزینه ۴ است. کاش سر جلسه میتونستم این تهلیلو بکنم.

[nader618]

(۲۲ بهمن ۱۳۹۱ ۱۱:۵۳ ق.ظ)fatima1537 نوشته شده توسط:  من ۱۱۴ رو ۲ بدست اوردم.
۱۱۳ یکم شک برانگیزه.چون فکر کنم ۲ تا از جمله ها صحیح باشه یعنی میشه گزینه ۳ (ابلته من ۳ نزدم)-جمله اول که طبیعتا صحیحه.جمله سوم هم همینطور.جمله دوم یکم شک برانگیزه.چون توی جستجوی حبابی با یک دور مرتب سازی میشه متوجه شد عناصر مرتب هستند یانه.از طرفی کمترین مرتبه زمانی برای مرتب سازی nlogn هست.

چطور جمله ی اول صحیحه؟؟؟؟؟؟؟
من هر کار ی میکنم یه درخت با این شرایط نمیتونم درست کنم
جمله ی دوم صد در صد درسته
تو یکی ار کنکور های گذشته اومده بود که درست بود تو کلید ها
جمله ی سوم هم صد در صد درسته
فقط رو اولی شک دارم که اگه درست باشه یعنی درست زدم

[osho]

من سوال ۱۱۴ این جوری تحلیل کردم ابتدا با n-1 مقایسه حالت اول را بررسی می کنیم بعد در قسمت ۲ قسمت بزرگتر را در نظر می گیریم این ها رو با هم جمع می کنیم و گزینه ۴ میشه .
۱۱۳- دو تاش درست است.
۱۱۵-n میشه از پویا حل میشه
۱۱۰-n میشه
۱۱۱ اول غلط دومی درست.

[sy_NBA]

(۲۱ بهمن ۱۳۹۱ ۰۹:۴۷ ب.ظ)مهمد نوشته شده توسط:  ۱۱۳ - اولین مورد بستگی داره درجه یک گره رو تعداد فرزنداش در نزر بگیری یا تعداد یالهاش، که من چون تعداد فرزنداش در نزر گرفتم، مورد اول درسته.
مورد دوم قلته.
مورد سوم هم درسته.
پس گزینه ۳ رو زدم.

---

(۲۱ بهمن ۱۳۹۱ ۰۹:۴۳ ب.ظ)sy_NBA نوشته شده توسط:  ۱۱۰ گزینه ۱ زدم ولی خیلی شک دارم. اگه یه الگوریتم جدا برای merge در نظر بگیریم جواب گزینه ۳ میشه
۱۱۱ گزینه ۳/ اولی رو میشه راحت براش یه مثال زد. ab= 4 ، ac=8 ، bc=5 .یال اندازه ۸ این مورد رو نقض میکنه. دومی هم درسته اگه لازمه توضیح بدم؟
۱۱۲ قسمت آخر سوال (به ترتیب فاصله) رو نخوندم و مفت اشتباه زدم گزینه ۱/ باید با الگوریتم selection kامین رو پیدا کنی(اوی n)، با partition همه ی kتای نزدیک رو بیاری کنار هم (اوی n) و بعد مرتبشون کنی (اوی klogk) در کل میشه n+klogk
۱۱۳ رو من زدم گزینه ۳/ آخریش که درسته، فقط ۶ تا عدد رو با ۹ تا مقایسه میشه مرتب کرد؟ اگه نشه یعنی غلط زدم.
۱۱۴ گزینه ۴/ با مثال عددی خیلی راحت حل شد.
۱۱۵ گزینه ۳/ الگوریتم بزرگترین زیردنباله جمع رو که بدونی از روی اون میشه خیلی راحت کوچکترین زیردنباله ی نزدیک به صفر رو هم پیدا کرد.

این الگوریتم بزرگترین زیردنباله جمع تو چه کتابیه؟ میشه یه توزیهی بدین.
۱۱۲ - هم درست میگید گزینه ۳ میشه. من قلت زدم.

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

[Dr_spam]

بچه ها میشه بگید سوال ۱۱۳ مورد سومش رو چه حساب درسته ؟ :-|

[osho]

(۲۲ بهمن ۱۳۹۱ ۱۲:۳۳ ب.ظ)Dr_spam نوشته شده توسط:  بچه ها میشه بگید سوال ۱۱۳ مورد سومش رو چه حساب درسته ؟ :-|

به کتاب ۶۰۰ مسله دکتر قدسی رجوع کن اونجا جواب داده

[fateme66]

(۲۲ بهمن ۱۳۹۱ ۱۲:۰۸ ب.ظ)nader618 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۱:۵۳ ق.ظ)fatima1537 نوشته شده توسط:  من ۱۱۴ رو ۲ بدست اوردم.
۱۱۳ یکم شک برانگیزه.چون فکر کنم ۲ تا از جمله ها صحیح باشه یعنی میشه گزینه ۳ (ابلته من ۳ نزدم)-جمله اول که طبیعتا صحیحه.جمله سوم هم همینطور.جمله دوم یکم شک برانگیزه.چون توی جستجوی حبابی با یک دور مرتب سازی میشه متوجه شد عناصر مرتب هستند یانه.از طرفی کمترین مرتبه زمانی برای مرتب سازی nlogn هست.

چطور جمله ی اول صحیحه؟؟؟؟؟؟؟
من هر کار ی میکنم یه درخت با این شرایط نمیتونم درست کنم
جمله ی دوم صد در صد درسته
تو یکی ار کنکور های گذشته اومده بود که درست بود تو کلید ها
جمله ی سوم هم صد در صد درسته
فقط رو اولی شک دارم که اگه درست باشه یعنی درست زدم

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

[pouri_sb]

۱۱۳ یکش غلطه
دومیش هم غلطه چون می شه تابع سقف logn! که می شه ۱۰! پس غلطه.
سومیش درسته

[fateme66]

(۲۲ بهمن ۱۳۹۱ ۱۲:۳۳ ب.ظ)Dr_spam نوشته شده توسط:  بچه ها میشه بگید سوال ۱۱۳ مورد سومش رو چه حساب درسته ؟ :-|

حسابش رو برید از کتاب clrs ببینید
به نظرم این همون الگوریتمه کوتاهترین مسیرها از یک مبدا.که چون گراف دور نداره طبق مرتب سازی توپولوژیکی کار میکنه،الگوریتم مرتب سازی توپولوژیک هم از dfs استفاده میکنه،چون زمان dfs برابره v+e هست این الگوریتم هم مرتبش همین میشه
این الگوریتم داخل کتاب پوران هم هست

[adele_69]

(۲۲ بهمن ۱۳۹۱ ۰۳:۱۳ ب.ظ)fateme66 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۲:۳۳ ب.ظ)Dr_spam نوشته شده توسط:  بچه ها میشه بگید سوال ۱۱۳ مورد سومش رو چه حساب درسته ؟ :-|

حسابش رو برید از کتاب clrs ببینید
به نظرم این همون الگوریتمه کوتاهترین مسیرها از یک مبدا.که چون گراف دور نداره طبق مرتب سازی توپولوژیکی کار میکنه،الگوریتم مرتب سازی توپولوژیک هم از dfs استفاده میکنه،چون زمان dfs برابره v+e هست این الگوریتم هم مرتبش همین میشه
این الگوریتم داخل کتاب پوران هم هست

چون یال منفی داره مگه نمیشه فلوید؟فلویدم با لیست مجاورتی o(ev)

---

(۲۲ بهمن ۱۳۹۱ ۰۳:۱۱ ب.ظ)pouri_sb نوشته شده توسط:  ۱۱۳ یکش غلطه
دومیش هم غلطه چون می شه تابع سقف logn! که می شه ۱۰! پس غلطه.
سومیش درسته

دومیش درسته من حساب کردم با حالت درجی!!

[مهمد]

(۲۲ بهمن ۱۳۹۱ ۱۲:۰۸ ب.ظ)nader618 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۱:۵۳ ق.ظ)fatima1537 نوشته شده توسط:  من ۱۱۴ رو ۲ بدست اوردم.
۱۱۳ یکم شک برانگیزه.چون فکر کنم ۲ تا از جمله ها صحیح باشه یعنی میشه گزینه ۳ (ابلته من ۳ نزدم)-جمله اول که طبیعتا صحیحه.جمله سوم هم همینطور.جمله دوم یکم شک برانگیزه.چون توی جستجوی حبابی با یک دور مرتب سازی میشه متوجه شد عناصر مرتب هستند یانه.از طرفی کمترین مرتبه زمانی برای مرتب سازی nlogn هست.

چطور جمله ی اول صحیحه؟؟؟؟؟؟؟
من هر کار ی میکنم یه درخت با این شرایط نمیتونم درست کنم
جمله ی دوم صد در صد درسته
تو یکی ار کنکور های گذشته اومده بود که درست بود تو کلید ها
جمله ی سوم هم صد در صد درسته
فقط رو اولی شک دارم که اگه درست باشه یعنی درست زدم

سوال ۱۱۳ جمله ی اولش کاملن به این بستگی داره که شما درجه یک گره رو در درخت تعداد فرزندان اون در نزر بگیرید یا تعداد یالهای اون. من کتاب هوروویتز الان دم دست ندارم ببینم کودوماشو در نزر گرفته. ولی اگه مسل من درجه گره رو تعداد فرزنداش در نزر بگیری. این جمله درسته (درختی با چهار نود، یک ریشه و ۳ فرزند) ولی اگه درجه گره تعداد یالهاش باشه این جمله قلته.

[مهمد]

(۲۲ بهمن ۱۳۹۱ ۱۲:۱۴ ب.ظ)sy_NBA نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۹:۴۷ ب.ظ)مهمد نوشته شده توسط:  ۱۱۳ - اولین مورد بستگی داره درجه یک گره رو تعداد فرزنداش در نزر بگیری یا تعداد یالهاش، که من چون تعداد فرزنداش در نزر گرفتم، مورد اول درسته.
مورد دوم قلته.
مورد سوم هم درسته.
پس گزینه ۳ رو زدم.

---

(۲۱ بهمن ۱۳۹۱ ۰۹:۴۳ ب.ظ)sy_NBA نوشته شده توسط:  ۱۱۰ گزینه ۱ زدم ولی خیلی شک دارم. اگه یه الگوریتم جدا برای merge در نظر بگیریم جواب گزینه ۳ میشه
۱۱۱ گزینه ۳/ اولی رو میشه راحت براش یه مثال زد. ab= 4 ، ac=8 ، bc=5 .یال اندازه ۸ این مورد رو نقض میکنه. دومی هم درسته اگه لازمه توضیح بدم؟
۱۱۲ قسمت آخر سوال (به ترتیب فاصله) رو نخوندم و مفت اشتباه زدم گزینه ۱/ باید با الگوریتم selection kامین رو پیدا کنی(اوی n)، با partition همه ی kتای نزدیک رو بیاری کنار هم (اوی n) و بعد مرتبشون کنی (اوی klogk) در کل میشه n+klogk
۱۱۳ رو من زدم گزینه ۳/ آخریش که درسته، فقط ۶ تا عدد رو با ۹ تا مقایسه میشه مرتب کرد؟ اگه نشه یعنی غلط زدم.
۱۱۴ گزینه ۴/ با مثال عددی خیلی راحت حل شد.
۱۱۵ گزینه ۳/ الگوریتم بزرگترین زیردنباله جمع رو که بدونی از روی اون میشه خیلی راحت کوچکترین زیردنباله ی نزدیک به صفر رو هم پیدا کرد.

این الگوریتم بزرگترین زیردنباله جمع تو چه کتابیه؟ میشه یه توزیهی بدین.
۱۱۲ - هم درست میگید گزینه ۳ میشه. من قلت زدم.

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

خوب، سخنران منبر کی بود؟

[fateme66]

(۲۲ بهمن ۱۳۹۱ ۰۳:۱۶ ب.ظ)adele_69 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۳:۱۳ ب.ظ)fateme66 نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۱۲:۳۳ ب.ظ)Dr_spam نوشته شده توسط:  بچه ها میشه بگید سوال ۱۱۳ مورد سومش رو چه حساب درسته ؟ :-|

حسابش رو برید از کتاب clrs ببینید
به نظرم این همون الگوریتمه کوتاهترین مسیرها از یک مبدا.که چون گراف دور نداره طبق مرتب سازی توپولوژیکی کار میکنه،الگوریتم مرتب سازی توپولوژیک هم از dfs استفاده میکنه،چون زمان dfs برابره v+e هست این الگوریتم هم مرتبش همین میشه
این الگوریتم داخل کتاب پوران هم هست

چون یال منفی داره مگه نمیشه فلوید؟فلویدم با لیست مجاورتی o(ev)

---

فکر نمیکنم الگوریتمی که گفتم با یال منفی مشکل داشته باشه آخه اصل الگوریتم برمیگرده به dfs .
چون تو سوال گفته بدون دوره و همچین الگوریتمی وجود داره به نظرم منظورش این بوده.

[fatima1537]

تست ۱۱۳ : برای جمله اول درخت رو ضمیمه کردم.فقط یک راس درجه فرد داره.خیلی ساده است
جمله سوم هم که کوتاهترین مسیر هست میشه |V|+|E| . چون گراف دور منفی نداره و جهت دار هست . که همون گراف DAGهست یعنی DIRECTED ACYCLIC GRAF (گراف بدن دور جهت دار) توی کتب تست الگوریتم توضیح داده.
جمله دوم.
فقط جمله دوم یکم شک برانگیزه و مفهومش واضح نیست.من هم سر همین فکر کنم اشتباه زده باشم.باید منتظر کلید بود.

---

(۲۲ بهمن ۱۳۹۱ ۱۲:۰۲ ب.ظ)مهمد نوشته شده توسط:  سوال ۱۱۴ - شما با برداشتن n/2 صفر و n/3 یک هنوز متوجه نمیشید که کدوم گونه است. و باید یکی دیگه هم بردارید. پس جواب گزینه ۴ است. کاش سر جلسه میتونستم این تهلیلو بکنم.

خب به خاطر همینه که میشه ۲/۳N+1 (همون بعلاوه ۱ هست که باعث میشه یک عنصر بیشتر رو بررسی کنیم و متوجه بشیم که کدوم گونه است) با ۲/۳Nنمیشه.