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

[msn_issue]

من اینا رو زدم طبق دفترچه B
۱۱۱ - ۴
۱۱۲ - ۴
۱۱۵ - ۴

!!!!

[sy_NBA]

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

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

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

---

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

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

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

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

manber
توی فصل استقرا گفته

[hashm1]

(۲۱ بهمن ۱۳۹۱ ۰۵:۵۹ ب.ظ)irisadaf نوشته شده توسط:  ۱۱۱->3
۱۱۳->2

سوال ۱۱۳ گزینه ۴

[mizgly]

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

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

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

در مورد سوال ۱۱۵
اون الگوریتم اینجا جواب نمیده، چون نمی‌خوایم کمترین مقدار رو پیدا کنیم بلکه می‌خوایم نزدیک‌ترین مقدار به صفر رو پیدا کنیم (یعنی کمترین قدر مطلق) که با تغییر اون الگوریتم نمیشه بهش رسید
منطق اون الگوریتم اینه که بزرگترین تا اینجا رو نگه داریم باشد که بزرگتر شود ولی اینجا نمی‌دونیم باید چه مقدار مثبت یا منفی رو نگه داریم که نزدیک‌تر به صفر بشیم
جواب nlogn هست که با درخت‌های متوازن (مثل AVL) قابل پیاده‌سازیه