تالار گفتمان مانشت

تست های47 تا 52

در مورد سوال 98 گزینه 1 صحیح است با آرایه 123 بررسی کنید

---

در مورد سوال 99 هم هر سه درست است مگر ایمکه منظور طراح از جمله سوم این بوده که بیش از یک دور داشته باشد ( چون نگفته فقط یکی ) که در این صورت دو جمله درست می شود

---

سوال 100 به وضوح گزینه 1

---

سوال 101 بین گزینه 1 و 2 شک دارم که وقت نکردم به دقت بررسی کنم

سوال 101 قطعا گزینه 2 جواب صحیحه.در بدترین حالت باید 31 بسته رو باز کرد.

---

در مورد سوال 47 پاسخ قطعا 199هست که من اشتباها 200 زدم.
من اینجور حساب کردم شد 200 ولی غلطه.
50 درج هزینش :50
1 حذف هزینش : 50+1
49 درج هزینش :49
1 حذف هزینش : 49+1
جما 200
ولی پاسخ صحیح:
99درج هزینش :99
1 حذف هزینش : 99+1
جمعا 199
سوال 49:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
52 قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت 1 بار اجرا میشه و در بدترین حالت n-1 بار که بر 2 تقسیم کنیم از مرتبه n هستش.

با سوال 101 گزینه 3 موافقم ...
بدترین: فرض کنیم تو 30 خانه اول که باز کردیم همه عدد 1 بود. و در خانه 31 عدد 2 باشد. پس باید 31 خانه باز شود دیگر :دی

با سوال 98 گزینه 1 هم موافتم ...
سر جلسه خیلی حالت تست کردم که یکیشم همون 123 بود. ولی عجب الگوریتم تو جیب جا شوییه ...

(21 بهمن 1391 11:27 ب.ظ)sarous نوشته شده توسط: [ -> ]سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

در مورد سوال 49 هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد

من در مورد سوال 100 موافق نیستم. رابطه بازگشتیش میشه
T(N) = 2T(N/2) + 1
خوب جوابشم میشه تتای N که نزدیکترین گزینه همان اوی بزرگ N میشه. رابطه بازگشتی به این خاطر این میشه که اگر در ریشه باشیم کافیه که طول وزن دار زیر درخت چپ و زیر درخت راست رو بدست بیاریم بعد با یک مقایسه بزرگترین رو انتخاب کنیم وسچس با وزن ریشه جمع کنیم. مقایسه و جمع تتای 1 هستن و چون درخت متوازن هست پس رابطه بازگشتی همونیه که نوشتم.

دوستان بحث طراحی الگوریتم مهندسی کامپیوتر ۹۲ رو انتقال بدن به اینجا:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(22 بهمن 1391 11:20 ق.ظ)vahidfrr نوشته شده توسط: [ -> ]

(21 بهمن 1391 11:27 ب.ظ)sarous نوشته شده توسط: [ -> ]سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد

(22 بهمن 1391 11:20 ق.ظ)vahidfrr نوشته شده توسط: [ -> ]

(21 بهمن 1391 11:27 ب.ظ)sarous نوشته شده توسط: [ -> ]سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد

دوست عزیز دومی مکس هیپه.در مکس هیپ کوچکترین عنصر در یکی از برگهاس و معلوم نیست کدوم برگ که بخوای با زمان logn پیداش کنی.باید n/2 عناصر که برگ هستند مورد جستجو قرار بگیره و از مرتبه n هستش که قطعا این رو نمی توان ساخت.
اولیش هم که avl فرض میکنیم به ازای هر a و b دلخواه گفته در مرتبه logn هست.a رو ریشه avl فرض میکنیم و b رو فرزند چپ a,حالا باید چند تا از نودها بررسی بشه؟n-1 که از مرتبه n هست.
پس هر 2 رو نمی توان ساخت.

طبق دفترچه B
۴۷- ۴ (البته به نظرم سوال مشکل داره)
۴۸- ۴
۴۹- ۳
۵۰ - ۳
۵۱- ۱
۵۲- ۲

پ.ن: گزینه‌های فوق نظر شخصیه منه و ممکنه لزوما درست نباشن

(22 بهمن 1391 02:10 ب.ظ)mfXpert نوشته شده توسط: [ -> ]طبق دفترچه B
۴۷- ۴
۴۸- ۴
۴۹- ۳
۵۰ - ۳
۵۱- ۱
۵۲- ۲

پ.ن: گزینه‌های فوق نظر شخصیه منه و ممکنه لزوما درست نباشن

سلام میشه بگین قسمت دوم 49 رو با چه داده ساختاری پیاده سازی کردین؟

(22 بهمن 1391 02:15 ب.ظ)ADELZX نوشته شده توسط: [ -> ]سلام میشه بگین قسمت دوم 49 رو با چه داده ساختاری پیاده سازی کردین؟

مین هیپ

(22 بهمن 1391 02:21 ب.ظ)mfXpert نوشته شده توسط: [ -> ]

(22 بهمن 1391 02:15 ب.ظ)ADELZX نوشته شده توسط: [ -> ]سلام میشه بگین قسمت دوم ۴۹ رو با چه داده ساختاری پیاده سازی کردین؟

مین هیپ

توی صورت سوال o کوچیک گذاشته .
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟

(22 بهمن 1391 02:24 ب.ظ)ADELZX نوشته شده توسط: [ -> ]توی صورت سوال o کوچیک گذاشته .
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟

چه نتیجه‌ای از این حرف شما باید گرفت؟

(22 بهمن 1391 02:35 ب.ظ)mfXpert نوشته شده توسط: [ -> ]

(22 بهمن 1391 02:24 ب.ظ)ADELZX نوشته شده توسط: [ -> ]توی صورت سوال o کوچیک گذاشته .
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟

چه نتیجه‌ای از این حرف شما باید گرفت؟

خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟

(22 بهمن 1391 02:37 ب.ظ)ADELZX نوشته شده توسط: [ -> ]خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟

شما می‌تونید به من بگید تفاوت اصلی اوی کوچیک و بزرگ در چی هستش؟