حلش رو دیدم - جواب ۴۲ بود و گفته بود با عمق ۴ فقط ۴ تا میشه ساخت و احتمال می داد سنجش غلط زده باشه!

(۰۵ بهمن ۱۳۸۹ ۰۴:۳۳ ق.ظ)grayman نوشته شده توسط:  حلش رو دیدم - جواب ۴۲ بود و گفته بود با عمق ۴ فقط ۴ تا میشه ساخت و احتمال می داد سنجش غلط زده باشه!

ببخشید شما مطمئنید در مورد سوال من صحبت می کنید؟

از نظر من میشه ۴^۲=۱۶ چون ارتفاع n-1 است یعنی نودها تک فرزندی اند پس به جز برگ برای هر نود ۲ حالت داریم( که فرزند چپ داشته باشد یا راست) پس ۱۶ تا درخت داریم که به یک طریق میتوانیم پر کنیم.

بله - و جوابم هم از روی کنکور جامع علوم کامپیوتر تالیف مقسمی بود که گفتم!

آفاق جون طراح سوال صریحاً اعلام کرده ریشه در سطح یک هست.
اگر هم سطح ریشه رو صفر در نظر می گرفتیم با n گره و ارتفاع n-1 تعداد درختان جستجوی دودویی ۲ به توان n-1 می شد. یعنی ۱۶ تا.
برای این سوال یکی از گره‌ها غیر از گره سطح ۴ باید دو فرزندی باشه.

عزیزم سطح ریشه همیشه ۱ بوده و هست.
اون چیزی که توش بحثه عمق و ارتفاع که من عمق ریشه رو صفر گرفتم در ضمن n=5 پس n-1=4 !!
حالا اگه عمق ریشه رو یک بگیریم بحثش فرق میکنه و همونیه که شما میگید.

خوب به نظر من مقسمی اشتباه گفته.
اوه ببخشید آفاق جون درسته در صورتی که سطح ریشه صفر باشه ۲ به توان ۴ جوابه.
با عمق ۴ هشت تا درخت می شه ساخت من امتحان کردم.
حالا سه تا جا هست که گره پنجم می تونه قرار بگیره یعنی ترکیب ۱ از سه. می شه ۳ تا حالت:
۸*۳
یه مسئله دیگه هم هست اونه که یک سری شکل‌ها تکراری هستن. من فعلاً ۴ تا شکل تکراری پیدا کردم. پس۴ تا رو یکی در نظر می گیریم می شه:
۳-۸*۳
درسته به نظرتون؟
آقای ۱۲۸qwi شما این فرمول رو چطوری به دست آوردین؟

(۰۵ بهمن ۱۳۸۹ ۰۵:۰۲ ق.ظ)**sara** نوشته شده توسط:  خوب به نظر من مقسمی اشتباه گفته.
اوه ببخشید آفاق جون درسته در صورتی که سطح ریشه صفر باشه ۲ به توان ۴ جوابه.
با عمق ۴ هشت تا درخت می شه ساخت من امتحان کردم.
حالا سه تا جا هست که گره پنجم می تونه قرار بگیره یعنی جایگشت ۱ از سه. می شه ۳ تا حالت:
۸*۳
یه مسئله دیگه هم هست اونه که یک سری شکل‌ها تکراری هستن. من فعلاً ۴ تا شکل تکراری پیدا کردم. پس۴ تا رو یکی در نظر می گیریم می شه:
۳-۸*۳
درسته به نظرتون؟
آقای ۱۲۸qwi شما این فرمول رو چطوری به دست آوردین؟

همین راهی که میگین درستق فقط حالتهای تکراری میشه ۴ تا که باید کم شه که جواب میشه ۲۰!
توضیح کاملم حامدخان زحمتشو کشیدن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

چرا منهای ۴ می شه؟ مگه ۴تا تکراری نیست؟ خوب حداقل یکی از اون ۴ تا رو باید در نظر بگیریم دیگه؟
صادقانه بگم من هیچی از مطالب آقای حامد نفهمیدم

(۰۵ بهمن ۱۳۸۹ ۰۵:۲۵ ق.ظ)**sara** نوشته شده توسط:  چرا منهای ۴ می شه؟ مگه ۴تا تکراری نیست؟ خوب حداقل یکی از اون ۴ تا رو باید در نظر بگیریم دیگه؟
صادقانه بگم من هیچی از مطالب آقای حامد نفهمیدم

هر چی بگم همون حرفای حامده
فقط میتونم بگم که ما در ۳*۸ حالتی که گره آخر تو سطح آخره رو ۸ تا شمردیم که نصف اونا یعنی ۴ تاش دقیقا تلراریه پس ۴ تا باید کم کنیم

---

حالتهایی که دوتا برگ در سطح آخر داریم میشه ۴تا(با رسم شکل مشخصه)
حالتهایی که در سطح آخر یک برگ داریم میشه ۸*۲
حالا جمعشون میشه ۱۶+۴=۲۰

(۰۵ بهمن ۱۳۸۹ ۰۵:۲۵ ق.ظ)**sara** نوشته شده توسط:  صادقانه بگم من هیچی از مطالب آقای حامد نفهمیدم

یعنی انقدر اون سوال رو بد توضیح دادم.کلی تایپ کردم که!(البته سوال نسبتا سخت بود و توضیح دادنش مشکل)




راه دوم:
تعداد کل درخت های دودویی برابر میشه با عدد کاتالان که میشه ۴۲ تا که شامل درختهایی به ارتفاع ۳،۴،۵ می باشد.حالا اگر درختهای به ارتفاع ۳و۵ رو حساب کنیم می تونیم درختهای به ارتفاع ۴ رو نیز بدست بیاریم.پس:

تعداد درختهای دودویی به ارتفاع ۵ با ۵ گره:$2^4=16$

تعداد درختهای دودویی به ارتفاع ۳ با ۵ گره: ۶ (اگر گره ۵ ریشه باشد ۴ حالت داره و اگر گره ۴ ریشه باشد ۱ حالت داره و به تقارن اگر گره ۱۰ ریشه باشد نیز ۱ حالت داره)

پس تعداد درختهای دودویی به ارتفاع ۴ با ۵ گره برابر است با: $42-16-6=20$

ممنون آقای ۱۲۸qwi
جواب شما کاملاً درسته.

جواب نهایی:
برای این سوال یکی از گره‌ها غیر از گره سطح ۴ باید دو فرزندی باشه.
با عمق ۴ هشت تا درخت می شه ساخت.
حالا سه تا جا هست که گره پنجم می تونه قرار بگیره یعنی ترکیب ۱ از سه. می شه ۳ تا حالت:
۸*۳
یه مسئله دیگه هم هست اونه که یک سری شکل‌ها تکراری هستن.
در ۳*۸ حالتی که گره آخر تو سطح آخره رو ۸ تا شمردیم که نصف اونا یعنی ۴ تاش دقیقا تکراریه پس ۴ تا باید کم کنیم:
$(2^{3}\ast 3)-4$