صفحه‌ها: ۱ ۲
(۰۷ شهریور ۱۳۹۳ ۰۲:۲۹ ب.ظ)miladcr7 نوشته شده توسط: خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش
درسته، مشکل یه چیز خیلی بی ارزشه ..
تو ساختمان داده معمولا هم میشه ریشه رو صفر گرفت و هم یک. من هم حتی تو همون فرمول پایه ریشه رو یک گرفته ام و کلا بحث هام با ریشه ۱ بوده. خب شما هم کلا از دید اینکه ریشه تو سطح صفر هست نگاه کردین. اما در کل مشکل خاصی نیست.
پیشنهاد می کنم شما ریشه رو ۱ فرض کنید. بعد فرمول [tex]\binom{2^{h-1}}{n-(2^{h-1}-1)}[/tex] رو برای n گره با ارتفاع h در نظر بگیرید. دقیقا تعداد درختهای دودویی با ارتفاع h و تعداد n گره رو نتیجه خواهد داد.
اگه مشکلی هست بگید لطفا.
حالا اگر هم خواستید ریشه رو صفر بگیرید از این فرمول استفاده کنید:
[tex]\binom{2^h}{n-(2^h-1)}[/tex]
(۰۷ شهریور ۱۳۹۳ ۰۲:۴۶ ب.ظ)!!! نوشته شده توسط:(07 شهریور ۱۳۹۳ ۰۲:۲۹ ب.ظ)miladcr7 نوشته شده توسط: خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش
درسته، مشکل یه چیز خیلی بی ارزشه ..
تو ساختمان داده معمولا هم میشه ریشه رو صفر گرفت و هم یک. من هم حتی تو همون فرمول پایه ریشه رو یک گرفته ام و کلا بحث هام با ریشه ۱ بوده. خب شما هم کلا از دید اینکه ریشه تو سطح صفر هست نگاه کردین. اما در کل مشکل خاصی نیست.
پیشنهاد می کنم شما ریشه رو ۱ فرض کنید. بعد فرمول [tex]\binom{2^{h-1}}{n-(2^{h-1}-1)}[/tex] رو برای n گره با ارتفاع h در نظر بگیرید. دقیقا تعداد درختهای دودویی با ارتفاع h و تعداد n گره رو نتیجه خواهد داد.
اگه مشکلی هست بگید لطفا.
حالا اگر هم خواستید ریشه رو صفر بگیرید از این فرمول استفاده کنید:
[tex]\binom{2^h}{n-(2^h-1)}[/tex]
بله میدونم ریشه رو هم ۱ میگیرن.ولی برای کنکور میگن صفر در نظر بگیرید.در ضمن فرمول هاتون هم فکر کنم جابجا هستن.توی فرمول دومی برای ۳ نود با ارتفاع ۲ میشه ترکیب ۰ از ۴ که میشه ۱در صورتی که باید ۴ بده
(۰۷ شهریور ۱۳۹۳ ۰۳:۰۸ ب.ظ)miladcr7 نوشته شده توسط: بله میدونم ریشه رو هم ۱ میگیرن.ولی برای کنکور میگن صفر در نظر بگیرید.در ضمن فرمول هاتون هم فکر کنم جابجا هستن.توی فرمول دومی برای ۳ نود با ارتفاع ۲ میشه ترکیب ۰ از ۴ که میشه ۱در صورتی که باید ۴ بده
آفرین! حق دارید. فرمول جابجا نیست. این یه اشکال فرموله. البته نه اینکه مشکلی باشه. می تونیم از این فرمول فقط برای درخت های کامل یا پر استفاده کنیم.
پس بهتره به این صورت تصحیح کنیم:
تعداد درخت های دودویی کامل یا پر با n گره و ارتفاع h:
[tex]\binom{2^{h-1}}{n-(2^{h-1}-1)}[/tex]
حالا مونده این که یه فرمول کلی پیدا کنیم. من هر موقع وقت کردم حتما روش کار می کنم. شما هم لطفا اگه پیدا کردید اینجا هم بنویسید تا ما هم استفاده کنیم.
راستش من فروم های خارجی رو هم گشتم (قبلا) دنبال این مسئله. ولی نبود. حالا این یه قدم عالی به سوی پیشرفته
حالا یه فرمول جامع تر ... نمی دونم .منتظزتونم ..
مرسی.
بازم سلام
در رابطه با تعداد درخت های دودویی کامل از این روابط استفاده کنیم راحت تره
اگه سطح رو x و ارتفاع رو h در نظر بگیریم
قبول دارید که :[tex]x=h 1[/tex]
حالا با فرض اینکه حتی ارتفاع رو هم نداشته باشیم، تعداد سطح درخت دودویی با داشتن n گره میشه:[tex]\lfloor\lg n\rfloor 1[/tex]
و تعداد درخت دودویی کامل با x سطح برابر:[tex]2^{x-1}[/tex] هستش
برای اونم یه فکری میکنیم
(۰۷ شهریور ۱۳۹۳ ۰۵:۰۲ ب.ظ)miladcr7 نوشته شده توسط: بازم سلام
در رابطه با تعداد درخت های دودویی کامل از این روابط استفاده کنیم راحت تره
اگه سطح رو x و ارتفاع رو h در نظر بگیریم
قبول دارید که :[tex]x=h 1[/tex]
حالا با فرض اینکه حتی ارتفاع رو هم نداشته باشیم، تعداد سطح درخت دودویی با داشتن n گره میشه:[tex]\lfloor\lg n\rfloor 1[/tex]
و تعداد درخت دودویی کامل با x سطح برابر:[tex]2^{x-1}[/tex] هستش
برای اونم یه فکری میکنیم
ببخشید من دقیقا متوجه نشدم این فرمولی که گفتین با مسئله ما چه رتبطی داره. لطفا بیشتر توضیح بدید.
۱) منظورتون از سطح=ارتفاع+۱ چیه؟ دیدگاه شما از واژه های سطح و ارتفاع چیه؟ لطفا توضیح بدید.
۲) سوال اصلی این تاپیک این بود که "تعداد درختهای دودویی با n گره و با ارتفاع h".
--- در کتاب در مورد تعداد درختهای دودویی با n گره بحث شده بود که همان عدد کاتالان میشه.
--- در این تاپیک این مسئله را به سطح h محدود کردیم. یعنی گفتیم با n گره چند درخت دودویی می تونیم بسازیم به شرطی که ارتفاع همه آنها دقیقا h باشه.
--- خب منم اومدم یه فرمولی گفتم که دقیقا برای درخت های دودویی کامل یا پر جواب میده (حالا شاید هم مشکل داره. اما تا حالا که مشکلی نداره). یعنی اومدیم گفتیم اگه درخت رو کامل یا پر در نظر بگیریم. با n گره می تونیم دقیقا همان فرمول قدر درخت دودویی می تونیم داشته باشیم به شرطی که دقیقا ارتفاع هر درخت h باشه.
حالا دو سوال در مباحث بالا بوجود اومد:
۱- آیا ایده بهتری دارید نسبت به فرمولی که نوشتم: یعنی تعداد درخت هایی دودویی کامل یا پر با n گره محدود شده به دقیقا ارتفاع h
۲- و سوال مهم تر اینکه یه فرمول کلی تر می تونیم بنویسیم که محدودیت کامل یا پر بودن رو بتونیم برداریم؟
الان من دقیقا متوجه نشدم که پاسخ شما به کدام دسته مربوط میشه.
بازم مرسی.
+++ فرمولی که نوشتین کمی منحرف شده. داده های ورودی ما همانطور که در عنوان تاپیک هم میبینید n تعداد گره ها و h ارتفاع است و سوالم هم که معلومه. تعداد درخت های دودویی با n گره محدود شده به دقیقا ارتفاع h.
مرسی.