تالار گفتمان مانشت

کلید سوالش گزینه ۱ هست. چطوری به جواب گزینه ۱ می رسیم؟(صورت سوال رو توی ضمیمه گذاشتم)

[attachment=342]

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

(05 بهمن 1389 04:33 ق.ظ)grayman نوشته شده توسط: [ -> ]حلش رو دیدم - جواب 42 بود و گفته بود با عمق 4 فقط 4 تا میشه ساخت و احتمال می داد سنجش غلط زده باشه!

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

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

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

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

[tex]2^{3}\ast 3-4[/tex]

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

خوب به نظر من مقسمی اشتباه گفته.
اوه ببخشید آفاق جون درسته در صورتی که سطح ریشه صفر باشه 2 به توان 4 جوابه.
با عمق 4 هشت تا درخت می شه ساخت من امتحان کردم.
حالا سه تا جا هست که گره پنجم می تونه قرار بگیره یعنی ترکیب 1 از سه. می شه 3 تا حالت:
8*3
یه مسئله دیگه هم هست اونه که یک سری شکل‌ها تکراری هستن. من فعلاً 4 تا شکل تکراری پیدا کردم. پس4 تا رو یکی در نظر می گیریم می شه:
3-8*3
درسته به نظرتون؟
آقای 128qwi شما این فرمول رو چطوری به دست آوردین؟

(05 بهمن 1389 05:02 ق.ظ)**sara** نوشته شده توسط: [ -> ]خوب به نظر من مقسمی اشتباه گفته.
اوه ببخشید آفاق جون درسته در صورتی که سطح ریشه صفر باشه 2 به توان 4 جوابه.
با عمق 4 هشت تا درخت می شه ساخت من امتحان کردم.
حالا سه تا جا هست که گره پنجم می تونه قرار بگیره یعنی جایگشت 1 از سه. می شه 3 تا حالت:
8*3
یه مسئله دیگه هم هست اونه که یک سری شکل‌ها تکراری هستن. من فعلاً 4 تا شکل تکراری پیدا کردم. پس4 تا رو یکی در نظر می گیریم می شه:
3-8*3
درسته به نظرتون؟
آقای 128qwi شما این فرمول رو چطوری به دست آوردین؟

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

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

(05 بهمن 1389 05:25 ق.ظ)**sara** نوشته شده توسط: [ -> ]چرا منهای 4 می شه؟ مگه 4تا تکراری نیست؟ خوب حداقل یکی از اون 4 تا رو باید در نظر بگیریم دیگه؟
صادقانه بگم من هیچی از مطالب آقای حامد نفهمیدم

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

---

حالتهایی که دوتا برگ در سطح آخر داریم میشه 4تا(با رسم شکل مشخصه)
حالتهایی که در سطح آخر یک برگ داریم میشه 8*2
حالا جمعشون میشه 16+4=20

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

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

(05 بهمن 1389 05:25 ق.ظ)**sara** نوشته شده توسط: [ -> ]صادقانه بگم من هیچی از مطالب آقای حامد نفهمیدم

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




راه دوم:
تعداد کل درخت های دودویی برابر میشه با عدد کاتالان که میشه 42 تا که شامل درختهایی به ارتفاع 3،4،5 می باشد.حالا اگر درختهای به ارتفاع 3و5 رو حساب کنیم می تونیم درختهای به ارتفاع 4 رو نیز بدست بیاریم.پس:

تعداد درختهای دودویی به ارتفاع 5 با 5 گره:[tex]2^4=16[/tex]

تعداد درختهای دودویی به ارتفاع 3 با 5 گره: 6 (اگر گره 5 ریشه باشد 4 حالت داره و اگر گره 4 ریشه باشد 1 حالت داره و به تقارن اگر گره 10 ریشه باشد نیز 1 حالت داره)

پس تعداد درختهای دودویی به ارتفاع 4 با 5 گره برابر است با: [tex]42-16-6=20[/tex]

(05 بهمن 1389 01:27 ب.ظ)حامد نوشته شده توسط: [ -> ]یعنی انقدر اون سوال رو بد توضیح دادم.کلی تایپ کردم که!(البته سوال نسبتا سخت بود و توضیح دادنش مشکل)

ببخشید آقا حامد احتمالا شما خوب توضیح دادی ولی من انقدر خسته بودم که درکم یکم دچار مشکل شده بود
این راه حل دومتون جالب بود ممنون