سلام دوستان
سوال ۵۱ آزمون جامع پارسه به نظرم آسونه ولی نتونستم حلش کنم و حیفه یادش نگیرم.
سوال اینه:
چند درخت با خاصیت Max Heap برای درخت زیر با ۱۳ کلید متفاوت میتوان رسم کرد؟
گزینه ۱: ۱۵۲۰۶۴
گزینه ۲: ۳۰۴۱۲۸
گزینه ۳: ۱۲۱۶۵۱۲
گزینه۴: ۶۰۸۲۵۶
جواب گزینه ۲ میشه.
تا یه قسمتی رو میدونم ولی از یه جایی به بعد نه!
چون ۵ عدد کوچکتر از ریشه باید داشته باشیم پس یه ترکیب ۵ از ۱۲ داریم. حالا بعدش تو زیردرخت چپ دوباره یه ترکیب ۳ از ۴ داریم . واسه دو فرزند هم سطح آخر هم دو حالت داریم.
حالا واسه درختی که فرزند راست ریشه هم میشه به همین صورت ترکیب ها رو بنویسم؟ اینجوری جوابم با پاسخنامه درست نیست.
گزینه ها کو؟؟؟؟
حدس میزنم برای درخت سمت راستی هم میگین ۷ از ۱۲/ که نباید بگین. چون هیپ کامله و همیشه از چپ چیده میشه. وقتی درخت سمت چپ رو گفتیم ۵ از ۱۲، میگیم باقی عددا میرن سمت راست، یعنی ۷ تا میرن راست، حالا اون ۷ تا یکیش میره ریشه و ۵ از ۶ هم میرن سمت چپ. و بعدش باز ازون ۵ تا یکیش میشه ریشه، و ۱ از ۴ تاش میره سمت چپ، و ۳ تای باقیمونده میرن سمت راست، حالا ازین ۳ تا یکیش میشه ریشه و توو گره هاشم ۲ حالت پیش میاد. و اون تک گره سمت راستی هم دیگه ۱ حالته فقط.
(۱۴ دى ۱۳۹۳ ۱۰:۴۰ ب.ظ)AVA 94 نوشته شده توسط: حدس میزنم برای درخت سمت راستی هم میگین ۷ از ۱۲/ که نباید بگین. چون هیپ کامله و همیشه از چپ چیده میشه. وقتی درخت سمت چپ رو گفتیم ۵ از ۱۲، میگیم باقی عددا میرن سمت راست، یعنی ۷ تا میرن راست، حالا اون ۷ تا یکیش میره ریشه و ۵ از ۶ هم میرن سمت چپ. و بعدش باز ازون ۵ تا یکیش میشه ریشه، و ۱ از ۴ تاش میره سمت چپ، و ۳ تای باقیمونده میرن سمت راست، حالا ازین ۳ تا یکیش میشه ریشه و توو گره هاشم ۲ حالت پیش میاد. و اون تک گره سمت راستی هم دیگه ۱ حالته فقط.
دقیقا. جواب هم میشه این:
[tex]\binom{12}{5}\: \times4\times2\times6\times4\times2[/tex]
فقط اینکه ۷ تا نود سمت راست رو دیگه ترکیب نگرفتیم هنوز واسم سواله. خب بازم مثل ۵ تا نود سمت چپ که متفاوت میتونن وارد درخت بشن، پس نودهای سمت راست هم ترتیب وارد شدنشون به درخت مهمه. چرا دیگه ترکیب ۷ از ۱۲ رو نداریم.
(۱۴ دى ۱۳۹۳ ۱۰:۳۵ ب.ظ)miladcr7 نوشته شده توسط: گزینه ها کو؟؟؟؟
ویرایش کردم.
ببینید اونم ترکیبه ولی به این صورت:
ما ۱۳ تا کلید داریم بزرگترین رو ریشه میذاریم و از بین ۱۲ تا حالا ۵ تا رو برای زیر درخت چپ انتخاب میکنیم[tex]\binom{12}{5}[/tex] (ببینید یعنی ۵ تا کلید میره دیگه و ما الان ۷ تا کلید باقیمونده داریم) حالا برای زیر درخت سمت راست ۷ تا کلید مونده که میخوایم ۷ تاشو انتخاب کنیم که میشه [tex]\binom{7}{7}[/tex] که همون یه حالت میشه
من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
ببخشید اینشکلی ک گذاشتین ماله max heap هس؟؟؟؟؟؟؟؟؟
مگه maxheapی درخت دودویی کامل که maxtreeباشه نیس؟؟!!!!!!!!!امگ نباید فرزندانو از چپ پر میشدن!!؟
(۱۴ دى ۱۳۹۳ ۱۱:۱۹ ب.ظ)miladcr7 نوشته شده توسط: ببینید اونم ترکیبه ولی به این صورت:
ما ۱۳ تا کلید داریم بزرگترین رو ریشه میذاریم و از بین ۱۲ تا حالا ۵ تا رو برای زیر درخت چپ انتخاب میکنیم[tex]\binom{12}{5}[/tex] (ببینید یعنی ۵ تا کلید میره دیگه و ما الان ۷ تا کلید باقیمونده داریم) حالا برای زیر درخت سمت راست ۷ تا کلید مونده که میخوایم ۷ تاشو انتخاب کنیم که میشه [tex]\binom{7}{7}[/tex] که همون یه حالت میشه
وقتی ۵تامیدی ب زیر درخت چپ و ۷تا میدی به زیر درخت راست بنظرتون این میشه درخت کامل؟؟
فرزندانان باید از چپ چیده بشن!!
(۱۵ دى ۱۳۹۳ ۰۱:۰۵ ق.ظ)ریحان نوشته شده توسط: من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
سلام .خسته نباشید .راستش بنا به مسائل پیش اومده فک کنم باید اول همه پستام اینو بنویسم که من توضیح دادنم کلا اینشکلیه و خدایی نکرده قصد توهین به معلومات کسی رو ندارم(ببخشید منظورم شما نیستی ولی خب مسائلی پیش اومده که باید اینو میگفتم)
خب بریم سراغ حل سوال
جواب این سوال اینه: [tex]\binom{12}{5}\times4\times2\times6\times4\times2[/tex]
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده
و گفته به چند حالت میشه نودها رو چید که خاصیت مکس هیپ داشته باشند.
بازم تاکید میکنم خاصیت مکس هیپ .
حالا شاید بگید خاصیت مکس هیپ چی داره که اینقد تاکید میکنیم ببینید اکثرا این رو با اینکه گفته شه درخت مکس هیپ هستش اشتباه میکنن و به کلمه خاصیت که تو متنه توجه نمیکنن.ببینید صورت سوال گفته خاصیت مکس هیپ رو داشته باشه یعنی مقدار هر نود از فرزنداش بیشتر باشه همین!!!چیز بیشتری نداریم دیگه قرار نیست درخت هم مکس هیپ باشه فقط گفته خاصیت مکس هیپ داشته باشه .پس همون طور که گفتم یعنی مقدار هر نود از فرزنداش بیشتر باشه
خب ما الان ۱۳ تا کلید داریم و همون طور که میدونید برای این که بتونیم خاصیت مکس هیپ بودن رو به درختمون بدیم باید بزرگترین عنصر رو توی ریشه قرار بدیم درسته؟؟؟
پس از ۱۳ تا کلید موجود بزرگترین کلید رو انتخاب میکنیم و تو ریشه میذاریم به چند حالت میتونیم این کار رو انجام بدیم؟؟؟یک حالت فقط اونم انتخاب بزرگترین کلیده
خب حالا یا باید کلیدای سمت چپ رو بچینیم یا سمت راست!!برای اینکه مشابه پاسخ سوال پیش بریم اول کلیدای سمت چپ رو میچینیم.
ببینید الان ۱۲ تا کلید باقیمونده داریم درسته؟بزرگترین رو که ریشه قرار دادیم و و کنار گذاشتیم.
حالا اگه شکل درخت رو ببینید معلومه که کل زیردرخت سمت چپ ۵ تا کلید داره.پس ما باید ۵ تا کلید از ۱۲ تا کلید رو برداریم و تو زیر درخت سمت چپ بذاریم درسته؟؟خب میایم ۵ تا رو انتخاب میکنیم که میشه [tex]\binom{12}{5}[/tex]
حالا بازم برای اینکه خاصیت مکس هیپ بودن رو حفظ کنیم بزرگترین کلید از این ۵ تا کلید رو ریشه میذاریم که این یه حالت داره فقط
حالا میبینید که (شکل رو مد نظر داشته باشید) سمت چپ این ریشه باید ۳ تا کلید باشه و سمت راستش هم یه دونه!!خب از ۵ تا کلید که یکیش برای ریشه رفت حالا از ۴ تا کلید باقیمونده ۳ تاش رو برای برای قسمت چپ انتخاب میکنیم به صورت[tex]\binom{4}{3}=4[/tex]
و یکی که باقیمونده رو هم به یه حالت توی قسمت سمت راست قرار میدیم
حالا دقت کنید این ۳ تا کلید رو که انتخاب کردیم بزرگترینش رو ریشه میذاریم درسته؟؟؟و ۲ تا کلید باقیمونده رو فرزنداش.ولی یه نکته ای هستش و اونم اینکه فرقی نداره که هر کدوم از کلیدا چپ قرار داده شن یا راست.پس اینم ۲ حالت میشه
ببینید این مثالو داشته باشید :
۳ تا عدد ۱و۲و۳ .خب ما ۳ رو ریشه میذاریم و میخوایم خاصیت مکس هیپ داشته باشیم یه حالت اینه ۳ ریشه باشه و ۲ فرزند چپ و ۱ فرزند راست و یه حالتم اینه که ۳ ریشه باشه و ۱ فرزند راست و ۲ فرزند چپ اکی؟؟
شاید بپرسید چرا بقیه قسمت ها اینجوری جابه جا نمیکردیم؟؟جواب اینه به این علت که اون موقه شکل اصلی درخت به هم میریخت درسته؟؟؟؟
و ما مجاز به این کار نیستسم ولی الان شکل درخت رو بهم نریختیم . فقط کلیدا رو جا به جا کردیم.
چیدن کلیدا تو قسمت سمت چپ تموم شد.حالا قسمت سمت راست.
همون طور که تو شکل میبینید کل زیر درخت سمت راست باید ۷ تا کلید داشته باشه و ما هم الان ۷ تا کلید داریم (۱ کلید برای ریشه اصلی رفت و ۵ تا هم برای زیر درخت سمت چپ)پس ۷تا کلید رو انتخاب میکنیم به صورت [tex]\binom{7}{7}=1[/tex] و بزرگترین کلید رو مطابق معمول ریشه میذاریم از ۶ تا کلید باقیمونده ۵ تا رو برای زیر درخت چپ این ریشه انتخاب میکنیم به صورت [tex]\binom{6}{5}=6[/tex] و یه دونه کلید باقیمونده رو هم به یه حالت تو قسمت سمت راست قرار میدیم.
حالا از ۵ تا کلیدی که انتخاب کردیم بزرگترین کلید رو ریشه میذاریم و از ۴ تا کلید باقیمونده ۳ تا کلید رو برای زیر درخت راست این ریشه انتخاب میکنیبه شکل [tex]\binom{4}{3}=4[/tex] و اون یکی رو هم به یه حالت سمت چپ میذاریم
حالا از ۳ تا کلیدی که مونده بزرگترین رو ریشه میذاریم و اون دوتای باقیمونده هم به ۲ حالت میتونن جا به جا شن(به همون دلیلی که قبلا اشاره کردیم)
خب پس کلا شد: [tex]\binom{12}{5}\times4\times2\times6\times4\times2=304128[/tex]
که گزینه دوم صحیح هستش
موفق باشید
(۱۵ دى ۱۳۹۳ ۰۱:۱۹ ب.ظ)miladcr7 نوشته شده توسط:جامع و کامل!!(15 دى ۱۳۹۳ ۰۱:۰۵ ق.ظ)ریحان نوشته شده توسط: من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
سلام .خسته نباشید .راستش بنا به مسائل پیش اومده فک کنم باید اول همه پستام اینو بنویسم که من توضیح دادنم کلا اینشکلیه و خدایی نکرده قصد توهین به معلومات کسی رو ندارم(ببخشید منظورم شما نیستی ولی خب مسائلی پیش اومده که باید اینو میگفتم)
خب بریم سراغ حل سوال
جواب این سوال اینه: [tex]\binom{12}{5}\times4\times2\times6\times4\times2[/tex]
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده ....................
کی گفته این جامع توضیح داده مورد سازه!!
اقا خدا خیرت بده من تاحالا همچین سوالی ندیده بودم تو تستا
ولی کامل باهاش اشنا شدم!(خوشبحالتون اینقد ب ساختمان و طراحی الگوریتم واردین!:cool
موفق باشید
سلام
اقا مگه maxheap نیس!!از چپ پر میشه دیگه ۷ تا میشه چپ ۵تا میشه راست
؟اشتباه میکنم ؟
(۱۵ دى ۱۳۹۳ ۱۱:۰۰ ب.ظ)mahayr نوشته شده توسط: سلامسلام.یه لطف کنید پست بالا رو که توضیح دادم بخونید.متوجه میشید
اقا مگه maxheap نیس!!از چپ پر میشه دیگه ۷ تا میشه چپ ۵تا میشه راست
(۱۵ دى ۱۳۹۳ ۰۵:۱۷ ب.ظ)shamim_70 نوشته شده توسط:(15 دى ۱۳۹۳ ۰۱:۱۹ ب.ظ)miladcr7 نوشته شده توسط:جامع و کامل!!(15 دى ۱۳۹۳ ۰۱:۰۵ ق.ظ)ریحان نوشته شده توسط: من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
سلام .خسته نباشید .راستش بنا به مسائل پیش اومده فک کنم باید اول همه پستام اینو بنویسم که من توضیح دادنم کلا اینشکلیه و خدایی نکرده قصد توهین به معلومات کسی رو ندارم(ببخشید منظورم شما نیستی ولی خب مسائلی پیش اومده که باید اینو میگفتم)
خب بریم سراغ حل سوال
جواب این سوال اینه: [tex]\binom{12}{5}\times4\times2\times6\times4\times2[/tex]
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده ....................
کی گفته این جامع توضیح داده مورد سازه!!
اقا خدا خیرت بده من تاحالا همچین سوالی ندیده بودم تو تستا
(خوشبحالتون اینقد ب ساختمان و طراحی الگوریتم واردین!:cool
موفق باشید
واقعا دستتون درد نکنه.چقدر عالی و اسون نوضیح دادین.جون میدین واسه استاد شدن...موفق باشید.بازم تش
کر
(۱۶ دى ۱۳۹۳ ۰۱:۰۶ ق.ظ)ریحان نوشته شده توسط:(15 دى ۱۳۹۳ ۰۵:۱۷ ب.ظ)shamim_70 نوشته شده توسط:(15 دى ۱۳۹۳ ۰۱:۱۹ ب.ظ)miladcr7 نوشته شده توسط:جامع و کامل!!(15 دى ۱۳۹۳ ۰۱:۰۵ ق.ظ)ریحان نوشته شده توسط: من این سوال رو کلا بلد نبودم میشه از اول توضیحش بدین؟
سلام .خسته نباشید .راستش بنا به مسائل پیش اومده فک کنم باید اول همه پستام اینو بنویسم که من توضیح دادنم کلا اینشکلیه و خدایی نکرده قصد توهین به معلومات کسی رو ندارم(ببخشید منظورم شما نیستی ولی خب مسائلی پیش اومده که باید اینو میگفتم)
خب بریم سراغ حل سوال
جواب این سوال اینه: [tex]\binom{12}{5}\times4\times2\times6\times4\times2[/tex]
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده ....................
کی گفته این جامع توضیح داده مورد سازه!!
اقا خدا خیرت بده من تاحالا همچین سوالی ندیده بودم تو تستا
(خوشبحالتون اینقد ب ساختمان و طراحی الگوریتم واردین!:cool
موفق باشید
واقعا دستتون درد نکنه.چقدر عالی و اسون نوضیح دادین.جون میدین واسه استاد شدن...موفق باشید.بازم تش
خواهش میکنم کاری نکردم که...
(۱۵ دى ۱۳۹۳ ۱۱:۰۵ ب.ظ)miladcr7 نوشته شده توسط:(15 دى ۱۳۹۳ ۱۱:۰۰ ب.ظ)mahayr نوشته شده توسط: خیلی ممنونسلام.یه لطف کنید پست بالا رو که توضیح دادم بخونید.متوجه میشید
سلام
اقا مگه maxheap نیس!!از چپ پر میشه دیگه ۷ تا میشه چپ ۵تا میشه راست
