۰
subtitle
ارسال: #۱
  
شمارش تعداد درختان با خاصیت Maxheap ؟؟
سلام
خداییش این جور سوالات استاندارد هست؟؟؟؟
آخه طراحی الگوریتم چ ربطی به ساختمان گسسته داره که بیاییم بشماریم...؟؟؟؟
این فرمولش از کجا آورده؟؟؟
باید حفظ کنیم؟؟؟؟؟
خداییش این جور سوالات استاندارد هست؟؟؟؟
آخه طراحی الگوریتم چ ربطی به ساختمان گسسته داره که بیاییم بشماریم...؟؟؟؟
این فرمولش از کجا آورده؟؟؟
باید حفظ کنیم؟؟؟؟؟
۱
ارسال: #۲
  
RE: شمارش تعداد درختان با خاصیت Maxheap ؟؟
جواب این سوال اینه: [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]
که گزینه دوم صحیح هستش
ببخشید سرتون رو درد اوردم موفق باشید
نگران نباشین هنوز توضیحش مونده فقط خواستم بگم قراره به چی برسیم.خب شروع میکنیم ببینید صورت سوال یه شکل خاصی رو به ما داده
و گفته به چند حالت میشه نودها رو چید که خاصیت مکس هیپ داشته باشند.
بازم تاکید میکنم خاصیت مکس هیپ .
حالا شاید بگید خاصیت مکس هیپ چی داره که اینقد تاکید میکنیم ببینید اکثرا این رو با اینکه گفته شه درخت مکس هیپ هستش اشتباه میکنن و به کلمه خاصیت که تو متنه توجه نمیکنن.ببینید صورت سوال گفته خاصیت مکس هیپ رو داشته باشه یعنی مقدار هر نود از فرزنداش بیشتر باشه همین!!!چیز بیشتری نداریم دیگه قرار نیست درخت هم مکس هیپ باشه فقط گفته خاصیت مکس هیپ داشته باشه .پس همون طور که گفتم یعنی مقدار هر نود از فرزنداش بیشتر باشه
خب ما الان ۱۳ تا کلید داریم و همون طور که میدونید برای این که بتونیم خاصیت مکس هیپ بودن رو به درختمون بدیم باید بزرگترین عنصر رو توی ریشه قرار بدیم درسته؟؟؟
پس از ۱۳ تا کلید موجود بزرگترین کلید رو انتخاب میکنیم و تو ریشه میذاریم به چند حالت میتونیم این کار رو انجام بدیم؟؟؟یک حالت فقط اونم انتخاب بزرگترین کلیده
خب حالا یا باید کلیدای سمت چپ رو بچینیم یا سمت راست!!برای اینکه مشابه پاسخ سوال پیش بریم اول کلیدای سمت چپ رو میچینیم.
ببینید الان ۱۲ تا کلید باقیمونده داریم درسته؟بزرگترین رو که ریشه قرار دادیم و و کنار گذاشتیم.
حالا اگه شکل درخت رو ببینید معل.مه که کل زیردرخت سمت چپ ۵ تا کلید داره.پس ما باید ۵ تا کلید از ۱۲ تا کلید رو برداریم و تو زیر درخت سمت چپ بذاریم درسته؟؟خب میایم ۵ تا رو انتخاب میکنیم که میشه [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]
که گزینه دوم صحیح هستش
ببخشید سرتون رو درد اوردم موفق باشید
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۴,۹۱۱ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
تعداد جواب | mostafaheydar1370 | ۲۱ | ۱۹,۶۴۴ |
۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa |
|
تعداد روش های نوشتن عدد n | ss311 | ۲ | ۳,۴۱۱ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد مسیرها در گراف | ss311 | ۰ | ۲,۰۵۷ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد درخت فراگیر | ss311 | ۰ | ۲,۳۳۹ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
تعداد توابع پوشا | ss311 | ۰ | ۲,۱۰۴ |
۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد اعداد ۵ رقمی هم ارز | ss311 | ۲ | ۲,۶۷۵ |
۰۶ بهمن ۱۳۹۸ ۰۴:۳۹ ب.ظ آخرین ارسال: ss311 |
|
تعداد رشته های n بیتی | hamedsos | ۲ | ۳,۱۷۰ |
۱۸ آبان ۱۳۹۸ ۰۹:۰۶ ب.ظ آخرین ارسال: Jooybari |
|
تعداد درختهای پوشا | ss311 | ۰ | ۱,۷۴۰ |
۱۹ بهمن ۱۳۹۷ ۱۲:۰۸ ب.ظ آخرین ارسال: ss311 |
|
تفاوت تعداد مقایسه های مورد نیاز در الگوریتم های متفاوت | porseshgar | ۰ | ۲,۱۸۱ |
۱۵ بهمن ۱۳۹۷ ۱۲:۳۳ ب.ظ آخرین ارسال: porseshgar |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close