هرم کامپیوتر ۹۵ - نسخهی قابل چاپ |
هرم کامپیوتر ۹۵ - Hopegod - 24 آذر ۱۳۹۵ ۰۹:۲۹ ب.ظ
بر طبق پاسخ گزینه اول جواب میشه چون بیشینه ی تعداد گره ها در یک هرم یا ارتفاع h وقتی است ک درخت پر باشد اما چطوری عدد تو گزینه یک بذاریم که جواب دربیاد مثلا برا یک هرم هفت عنصری [attachment=21014] ممنون میشم کمکم کنید. |
RE: هرم کامپیوتر ۹۵ - Pure Liveliness - 25 آذر ۱۳۹۵ ۰۱:۴۹ ق.ظ
سلام. درخت پر باید باشه تا بیشترین تعداد گره رو توی هر سطح داشته باشه. منظور سوال اینه که توی ارتفاع h بیشترین تعداد گره چند تا هست؟ مثلا درخت ۷ نودی. توی سطح اول که ریشه هست، ارتفاع ریشه میشه ۲ و یک گره هست. توی سطح دوم ارتفاع میشه ۱ و ۲ تا گره هست. توی سطح سوم ارتفاع میشه ۰ و ۴ تا گره هست. پس کلا واسه درخت با n تا گره میدونیم که توی سطح اول با ارتفاع h یه دونه گره. توی سطح دوم با ارتفاع h-1 دو تا گره. توی سطح سوم با ارتفاع h-2 چهار تا گره. . توی سطح kام با ارتفاع [tex]h-k+1=h-(k-1)[/tex] تعداد [tex]۲^{k-1}[/tex] تا گره هست. توی سطح آخر یعنی برگ ها، با ارتفاع h-h=0، [tex]2^h[/tex] تا گره هست. توی اینجا هم اگه جای n بذاریم ۷، با مقداردهی h به ۰ و ۱ و ۲ میبینیم که تعداد گره ها توی این سطح ها دقیقا برابر ۱، ۲ و ۴ هست و گزینه ی ۱ صحیح هست. پی نوشت: سعی کردم خودم فرمول رو اثبات کنم به مشکل خوردم. هرچند واضح هست ولی اگه بتونم فردا اثباتش رو مینویسم. |
RE: هرم کامپیوتر ۹۵ - Hopegod - 25 آذر ۱۳۹۵ ۰۱:۰۳ ب.ظ
خیلی خیلی ممنونم . |