(15 دى 1393 01:05 ق.ظ)ریحان نوشته شده توسط: [ -> ]من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
سلام .خسته نباشید .راستش بنا به مسائل پیش اومده فک کنم باید اول همه پستام اینو بنویسم که من توضیح دادنم کلا اینشکلیه و خدایی نکرده قصد توهین به معلومات کسی رو ندارم(ببخشید منظورم شما نیستی ولی خب مسائلی پیش اومده که باید اینو میگفتم)
خب بریم سراغ حل سوال
جواب این سوال اینه: [tex]\binom{12}{5}\times4\times2\times6\times4\times2[/tex]
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده
و گفته به چند حالت میشه نودها رو چید که
خاصیت مکس هیپ داشته باشند.
بازم تاکید میکنم
خاصیت مکس هیپ .
حالا شاید بگید
خاصیت مکس هیپ چی داره که اینقد تاکید میکنیم ببینید اکثرا این رو با اینکه گفته شه درخت مکس هیپ هستش اشتباه میکنن و به کلمه
خاصیت که تو متنه توجه نمیکنن.ببینید صورت سوال گفته
خاصیت مکس هیپ رو داشته باشه یعنی مقدار هر نود از فرزنداش بیشتر باشه همین!!!چیز بیشتری نداریم دیگه قرار نیست درخت هم مکس هیپ باشه فقط گفته
خاصیت مکس هیپ داشته باشه .پس همون طور که گفتم یعنی مقدار هر نود از فرزنداش بیشتر باشه
خب ما الان 13 تا کلید داریم و همون طور که میدونید برای این که بتونیم خاصیت مکس هیپ بودن رو به درختمون بدیم باید بزرگترین عنصر رو توی ریشه قرار بدیم درسته؟؟؟
پس از 13 تا کلید موجود بزرگترین کلید رو انتخاب میکنیم و تو ریشه میذاریم به چند حالت میتونیم این کار رو انجام بدیم؟؟؟یک حالت فقط اونم انتخاب بزرگترین کلیده
خب حالا یا باید کلیدای سمت چپ رو بچینیم یا سمت راست!!برای اینکه مشابه پاسخ سوال پیش بریم اول کلیدای سمت چپ رو میچینیم.
ببینید الان 12 تا کلید باقیمونده داریم درسته؟بزرگترین رو که ریشه قرار دادیم و و کنار گذاشتیم.
حالا اگه شکل درخت رو ببینید معلومه که کل زیردرخت سمت چپ 5 تا کلید داره.پس ما باید 5 تا کلید از 12 تا کلید رو برداریم و تو زیر درخت سمت چپ بذاریم درسته؟؟خب میایم 5 تا رو انتخاب میکنیم که میشه [tex]\binom{12}{5}[/tex]
حالا بازم برای اینکه خاصیت مکس هیپ بودن رو حفظ کنیم بزرگترین کلید از این 5 تا کلید رو ریشه میذاریم که این یه حالت داره فقط
حالا میبینید که (شکل رو مد نظر داشته باشید) سمت چپ این ریشه باید 3 تا کلید باشه و سمت راستش هم یه دونه!!خب از 5 تا کلید که یکیش برای ریشه رفت حالا از 4 تا کلید باقیمونده 3 تاش رو برای برای قسمت چپ انتخاب میکنیم به صورت[tex]\binom{4}{3}=4[/tex]
و یکی که باقیمونده رو هم به یه حالت توی قسمت سمت راست قرار میدیم
حالا دقت کنید این 3 تا کلید رو که انتخاب کردیم بزرگترینش رو ریشه میذاریم درسته؟؟؟و 2 تا کلید باقیمونده رو فرزنداش.ولی یه نکته ای هستش و اونم اینکه فرقی نداره که هر کدوم از کلیدا چپ قرار داده شن یا راست.پس اینم 2 حالت میشه
ببینید این مثالو داشته باشید :
3 تا عدد 1و2و3 .خب ما 3 رو ریشه میذاریم و میخوایم خاصیت مکس هیپ داشته باشیم یه حالت اینه 3 ریشه باشه و 2 فرزند چپ و 1 فرزند راست و یه حالتم اینه که 3 ریشه باشه و 1 فرزند راست و 2 فرزند چپ اکی؟؟
شاید بپرسید چرا بقیه قسمت ها اینجوری جابه جا نمیکردیم؟؟جواب اینه به این علت که اون موقه شکل اصلی درخت به هم میریخت درسته؟؟؟؟
و ما مجاز به این کار نیستسم ولی الان شکل درخت رو بهم نریختیم . فقط کلیدا رو جا به جا کردیم.
چیدن کلیدا تو قسمت سمت چپ تموم شد.حالا قسمت سمت راست.
همون طور که تو شکل میبینید کل زیر درخت سمت راست باید 7 تا کلید داشته باشه و ما هم الان 7 تا کلید داریم (1 کلید برای ریشه اصلی رفت و 5 تا هم برای زیر درخت سمت چپ)پس 7تا کلید رو انتخاب میکنیم به صورت [tex]\binom{7}{7}=1[/tex] و بزرگترین کلید رو مطابق معمول ریشه میذاریم از 6 تا کلید باقیمونده 5 تا رو برای زیر درخت چپ این ریشه انتخاب میکنیم به صورت [tex]\binom{6}{5}=6[/tex] و یه دونه کلید باقیمونده رو هم به یه حالت تو قسمت سمت راست قرار میدیم.
حالا از 5 تا کلیدی که انتخاب کردیم بزرگترین کلید رو ریشه میذاریم و از 4 تا کلید باقیمونده 3 تا کلید رو برای زیر درخت راست این ریشه انتخاب میکنیبه شکل [tex]\binom{4}{3}=4[/tex] و اون یکی رو هم به یه حالت سمت چپ میذاریم
حالا از 3 تا کلیدی که مونده بزرگترین رو ریشه میذاریم و اون دوتای باقیمونده هم به 2 حالت میتونن جا به جا شن(به همون دلیلی که قبلا اشاره کردیم)
خب پس کلا شد: [tex]\binom{12}{5}\times4\times2\times6\times4\times2=304128[/tex]
که گزینه دوم صحیح هستش
موفق باشید
ولی کامل باهاش اشنا شدم!
؟اشتباه میکنم
کر