تست های۴۷ تا ۵۲
در مورد سوال ۹۸ گزینه ۱ صحیح است با آرایه ۱۲۳ بررسی کنید
در مورد سوال ۹۹ هم هر سه درست است مگر ایمکه منظور طراح از جمله سوم این بوده که بیش از یک دور داشته باشد ( چون نگفته فقط یکی ) که در این صورت دو جمله درست می شود
سوال ۱۰۰ به وضوح گزینه ۱
سوال ۱۰۱ بین گزینه ۱ و ۲ شک دارم که وقت نکردم به دقت بررسی کنم
سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
با سوال ۱۰۱ گزینه ۳ موافقم ...
بدترین: فرض کنیم تو ۳۰ خانه اول که باز کردیم همه عدد ۱ بود. و در خانه ۳۱ عدد ۲ باشد. پس باید ۳۱ خانه باز شود دیگر :دی
با سوال ۹۸ گزینه ۱ هم موافتم ...
سر جلسه خیلی حالت تست کردم که یکیشم همون ۱۲۳ بود. ولی عجب الگوریتم تو جیب جا شوییه ...
(۲۱ بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط: سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
من در مورد سوال ۱۰۰ موافق نیستم. رابطه بازگشتیش میشه
T(N) = 2T(N/2) + 1
خوب جوابشم میشه تتای N که نزدیکترین گزینه همان اوی بزرگ N میشه. رابطه بازگشتی به این خاطر این میشه که اگر در ریشه باشیم کافیه که طول وزن دار زیر درخت چپ و زیر درخت راست رو بدست بیاریم بعد با یک مقایسه بزرگترین رو انتخاب کنیم وسچس با وزن ریشه جمع کنیم. مقایسه و جمع تتای ۱ هستن و چون درخت متوازن هست پس رابطه بازگشتی همونیه که نوشتم.
دوستان بحث طراحی الگوریتم مهندسی کامپیوتر ۹۲ رو انتقال بدن به اینجا:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۲ بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط:(21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط: سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
(۲۲ بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط:(21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط: سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد
در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.
دوست عزیز دومی مکس هیپه.در مکس هیپ کوچکترین عنصر در یکی از برگهاس و معلوم نیست کدوم برگ که بخوای با زمان logn پیداش کنی.باید n/2 عناصر که برگ هستند مورد جستجو قرار بگیره و از مرتبه n هستش که قطعا این رو نمی توان ساخت.
اولیش هم که avl فرض میکنیم به ازای هر a و b دلخواه گفته در مرتبه logn هست.a رو ریشه avl فرض میکنیم و b رو فرزند چپ a,حالا باید چند تا از نودها بررسی بشه؟n-1 که از مرتبه n هست.
پس هر ۲ رو نمی توان ساخت.
طبق دفترچه B
۴۷- ۴ (البته به نظرم سوال مشکل داره)
۴۸- ۴
۴۹- ۳
۵۰ - ۳
۵۱- ۱
۵۲- ۲
پ.ن: گزینه‌های فوق نظر شخصیه منه و ممکنه لزوما درست نباشن
(۲۲ بهمن ۱۳۹۱ ۰۲:۱۰ ب.ظ)mfXpert نوشته شده توسط: طبق دفترچه B
۴۷- ۴
۴۸- ۴
۴۹- ۳
۵۰ - ۳
۵۱- ۱
۵۲- ۲
پ.ن: گزینه‌های فوق نظر شخصیه منه و ممکنه لزوما درست نباشن
سلام میشه بگین قسمت دوم ۴۹ رو با چه داده ساختاری پیاده سازی کردین؟
(۲۲ بهمن ۱۳۹۱ ۰۲:۱۵ ب.ظ)ADELZX نوشته شده توسط: سلام میشه بگین قسمت دوم ۴۹ رو با چه داده ساختاری پیاده سازی کردین؟مین هیپ
(۲۲ بهمن ۱۳۹۱ ۰۲:۲۱ ب.ظ)mfXpert نوشته شده توسط:توی صورت سوال o کوچیک گذاشته .(22 بهمن ۱۳۹۱ ۰۲:۱۵ ب.ظ)ADELZX نوشته شده توسط: سلام میشه بگین قسمت دوم ۴۹ رو با چه داده ساختاری پیاده سازی کردین؟مین هیپ
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟
(۲۲ بهمن ۱۳۹۱ ۰۲:۲۴ ب.ظ)ADELZX نوشته شده توسط: توی صورت سوال o کوچیک گذاشته .چه نتیجه‌ای از این حرف شما باید گرفت؟
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟
(۲۲ بهمن ۱۳۹۱ ۰۲:۳۵ ب.ظ)mfXpert نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۲:۲۴ ب.ظ)ADELZX نوشته شده توسط: توی صورت سوال o کوچیک گذاشته .چه نتیجه‌ای از این حرف شما باید گرفت؟
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟
خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟
(۲۲ بهمن ۱۳۹۱ ۰۲:۳۷ ب.ظ)ADELZX نوشته شده توسط: خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟شما می‌تونید به من بگید تفاوت اصلی اوی کوچیک و بزرگ در چی هستش؟