در یک درخت دودویی T ، برای هر برگ x واقع در عمق d تابع [tex]\omega (x)= 2^{-d}[/tex] را تعریف می کنیم . کدام یک از گزینه های زیر برابر است با [tex]\alpha = \sum_{leaf x}\omega (x)^{}[/tex] است ؟
[tex]1) \alpha \leq 1[/tex]
[tex]2) \alpha =1[/tex]
[tex]3) \alpha > 1[/tex]
[tex]4) \alpha < 1[/tex]
------
خب با استقرا به گزینه ۲ می رسیم ، آیا با روشی دیگر می توان این مسئله را حل کرد ؟
سلام.
من فکر می کنم گزینه یک درست باشه !
درصورتی درخت دودویی پر باشه آلفا برابر ۱ . و درصورتی درخت غیر پر باشه آلفا کوچکتر از یک خواهد بود.
گزینه ۳ تحت هیچ شرایطی درست نیست.
ممکنه توضیح بفرمایید چرا ۲ ؟
(۲۱ خرداد ۱۳۹۲ ۰۶:۲۶ ب.ظ)Pakniat نوشته شده توسط: در یک درخت دودویی T ، برای هر برگ x واقع در عمق d تابع [tex]\omega (x)= 2^{-d}[/tex] را تعریف می کنیم . کدام یک از گزینه های زیر برابر است با [tex]\alpha = \sum_{leaf x}\omega (x)^{}[/tex] است ؟
[tex]1) \alpha \leq 1[/tex]
[tex]2) \alpha =1[/tex]
[tex]3) \alpha > 1[/tex]
[tex]4) \alpha < 1[/tex]
------
خب با استقرا به گزینه ۲ می رسیم ، آیا با روشی دیگر می توان این مسئله را حل کرد ؟
با یک مثال ساده ثابت میشه که گزینه ۱ درسته :
حالتی که یک نود داریم که هم ریشه و هم برگ که جواب سیگما میشه ۱
استقرایی که بگم : حالا به ازای هر بچه ای که برای اولین بار به برگی در لول x اضافه میشه و اونو تبدیل به یک والد می کنه ،
[tex]2^(-x)[/tex]
به سیگما اضافه میشه و بجاش دوبرابر اون عدد از حاصل سیگما کم میشه (خود والد دیگه برگ نیست) و برای بچه دوم حداکثر عدد مربوط به والد به جمع سیگما اضافه میشه که قبلا کم کردیم . (یعنی ۲ برابر عدد فوق که میشه برابر با عددی که قبلا به ازای برگی در لول x به سیگما اضافه شده بود)
پس حداکثر نتیجه سیگما ۱ خواهد بود.
حداکثر برگهای درخت دودویی در عمق d یعنی حالتی که درخت فول باشه برابر [tex]2^{_{d}}[/tex] هست. به این ترتیب جواب سیگما میشه: [tex]2^{^{d}}\times 2^{^{-d}}[/tex]
که جواب یک هست و گزینه دو صحیحه.
اصلاح: الان که با دقت نگاه کردم گزینه ۱ درسته. درخت اگه فول باشه حداکثر مقدار یک هست ولی درخت میتونه فول نباشه بنابراین کمتر از یک هم میتونه باشه.