![[تصویر: 465615_mgnc_p_20190121_221521_vhdr_on_1.jpg]](https://img.manesht.ir/465615_mgnc_p_20190121_221521_vhdr_on_1.jpg)
برای این سوال
واسه قسمت اولش میشه درخت اریب را مثال بزنیم؟؟؟
واسه قسمت دومش درخت پر؟؟؟
واسه قسمت سومش نمیفهمم چجوری حل میشه اصلا
قسمت چهارم هم میگه غلط چرا؟
![[تصویر: 465615_o1gc_p_20190122_020338_vhdr_on_1.jpg]](https://img.manesht.ir/465615_o1gc_p_20190122_020338_vhdr_on_1.jpg)
این سوال راه حلش چجوریه باید واسه هر عددی دونه دونه حساب کرد؟میشه لطفا یک کم توضیح بدین خیلی خیلی ممنون میشم
(۰۲ بهمن ۱۳۹۷ ۰۳:۲۵ ق.ظ)Sanazzz نوشته شده توسط:
برای این سوال
واسه قسمت اولش میشه درخت اریب را مثال بزنیم؟؟؟
واسه قسمت دومش درخت پر؟؟؟
واسه قسمت سومش نمیفهمم چجوری حل میشه اصلا
قسمت چهارم هم میگه غلط چرا؟
این سوال راه حلش چجوریه باید واسه هر عددی دونه دونه حساب کرد؟میشه لطفا یک کم توضیح بدین خیلی خیلی ممنون میشم
سختترین و بدترین نوع سوال، سوالاتیه که به این سبک داده میشن! برای حلشون باید هر چهارتا گزینه رو بلد باشید تا بدونید چندتاشون درستن و یا غلط و متاسفانه سالهای اخیر این نوع سوالات خیلی باب شدن!
سوال اول: دوتا مورد اول رو درست حدس زدین. مورد سوم اینطوریه که با استفاده از n/2 نود، درخت تقریباً پر میسازیم که در این صورت پهنای این درخت حدوداً n/4 میشه که پهناش از مرتبه تتای(n) میشه. و برای به دست آوردن ارتفاع از مرتبه‌ی n، گره‌های باقیمونده رو به صورت مورب زیر آخرین سطح قرار میدیم که ارتفاع از مرتبه تتای(n) رو بهمون میده.
مورد چهارم هم اگه درختی ارتفاعش lg n باشه پهناش قطعاً n خواهد بود و درختی که پهناش رادیکال n باشه، ارتفاعش حداقل رادیکال n هست.
سوال دوم: ریشه باید حتماً ۱۱ باشه. و از ۱۰ عدد باقیمونده باید ۷ عدد برای زیر درخت چپ انتخاب بشه که میشه (انتخاب ۷ از ۱۰ (ترکیب)). حالا از این ۷ عدد بزرگترینش باید تو ریشه باشه و از ۶ عدد باقیمونده ۵ تاشو برای زیر درخت راست انتخاب میکنیم که میشه (انتخاب ۵ از ۶) و از این ۵ عدد، بزرگترین باید ریشه باشه و از ۴ عدد باقیمونده ۳تاشو برای زیردرخت چپ انتخاب میکنیم که میشه (انتخاب ۳ از ۴) و این سه عدد رو به دو حالت میشه تو زیردرخت باقیمونده چید! در ضمن ۳ عددی که به زیر درخت راست ریشه تعلق دارن هم به ۲ طریق میشه چید. پس در کل میشه
(انتخاب ۷ از ۱۰)×(انتخاب ۵ از ۶)×(انتخاب ۳ از ۴)×۲×۲ = ۱۱۵۲۰
جواب سوالات از کتاب مجموعه سوالات سالهای اخیر پوران.
(۰۲ بهمن ۱۳۹۷ ۰۱:۰۵ ب.ظ)ph0en1x نوشته شده توسط:(02 بهمن ۱۳۹۷ ۰۳:۲۵ ق.ظ)Sanazzz نوشته شده توسط:
برای این سوال
واسه قسمت اولش میشه درخت اریب را مثال بزنیم؟؟؟
واسه قسمت دومش درخت پر؟؟؟
واسه قسمت سومش نمیفهمم چجوری حل میشه اصلا
قسمت چهارم هم میگه غلط چرا؟
این سوال راه حلش چجوریه باید واسه هر عددی دونه دونه حساب کرد؟میشه لطفا یک کم توضیح بدین خیلی خیلی ممنون میشم
سختترین و بدترین نوع سوال، سوالاتیه که به این سبک داده میشن! برای حلشون باید هر چهارتا گزینه رو بلد باشید تا بدونید چندتاشون درستن و یا غلط و متاسفانه سالهای اخیر این نوع سوالات خیلی باب شدن!
سوال اول: دوتا مورد اول رو درست حدس زدین. مورد سوم اینطوریه که با استفاده از n/2 نود، درخت تقریباً پر میسازیم که در این صورت پهنای این درخت حدوداً n/4 میشه که پهناش از مرتبه تتای(n) میشه. و برای به دست آوردن ارتفاع از مرتبه‌ی n، گره‌های باقیمونده رو به صورت مورب زیر آخرین سطح قرار میدیم که ارتفاع از مرتبه تتای(n) رو بهمون میده.
مورد چهارم هم اگه درختی ارتفاعش lg n باشه پهناش قطعاً n خواهد بود و درختی که پهناش رادیکال n باشه، ارتفاعش حداقل رادیکال n هست.
سوال دوم: ریشه باید حتماً ۱۱ باشه. و از ۱۰ عدد باقیمونده باید ۷ عدد برای زیر درخت چپ انتخاب بشه که میشه (انتخاب ۷ از ۱۰ (ترکیب)). حالا از این ۷ عدد بزرگترینش باید تو ریشه باشه و از ۶ عدد باقیمونده ۵ تاشو برای زیر درخت راست انتخاب میکنیم که میشه (انتخاب ۵ از ۶) و از این ۵ عدد، بزرگترین باید ریشه باشه و از ۴ عدد باقیمونده ۳تاشو برای زیردرخت چپ انتخاب میکنیم که میشه (انتخاب ۳ از ۴) و این سه عدد رو به دو حالت میشه تو زیردرخت باقیمونده چید! در ضمن ۳ عددی که به زیر درخت راست ریشه تعلق دارن هم به ۲ طریق میشه چید. پس در کل میشه
(انتخاب ۷ از ۱۰)×(انتخاب ۵ از ۶)×(انتخاب ۳ از ۴)×۲×۲ = ۱۱۵۲۰
جواب سوالات از کتاب مجموعه سوالات سالهای اخیر پوران.
خیی خیلی خیلی خیلی ممنون که جواب دادین
دستتون درد نکنه
ممنونممممم