ممنون میشم راهنمایی کنید
[attachment=8256]
هیپ درخت کامله.و چون ۱۰۲۳ تا نود داره پس پره. نودهای نارنجی و سبز رنگ برگتر از ۱۰۰۰ هستند
(۱۴ آذر ۱۳۹۱ ۰۶:۴۱ ب.ظ)svk7 نوشته شده توسط: هیپ درخت کامله.و چون ۱۰۲۳ تا نود داره پس پره. نودهای نارنجی و سبز رنگ برگتر از ۱۰۰۰ هستند
ممنون
میشه یه کم توضیح هم بدید!(نود هاتون رو هم عدد بذارید.ممنون
سمت راست گره ها هم نود هست دیگه؟
هیپ درخت تقریبا کامله! چون میتونه یه گره داشته باشه که فقط فرزند چپ داره.
به نظر من:
در سطح ۰ که گره ریشه است ۱ گره دارد ، ۰^۲=۱
درسطح ۱ ، تعداد گرهها [tex]2^{1}[/tex] - و مجموعا تا اینجا [tex]2^{1 1} - 1[/tex] گره در درخت موجود است
سطح ۲ ، [tex]2^{2}[/tex]- و مجموعا تا اینجا [tex]2^{2 1} - 1[/tex] گره در درخت موجود است
(اگر شماره هر سطح را n فرض کنیم ، در هر سطح تعداد گرهها برابر [tex]2^{n}[/tex] است و تعداد کل گرههای موجود [tex]2^{n 1}-1[/tex] است )
پس سطح ۹ ، ۵۱۲ برگ دارد چون ۹^۲= ۵۱۲ و مجموعا تا اینجا [tex]2^{9 1}-1[/tex]گره در درخت موجود است
پس این درخت تا سطح ۹ کلا دارای ۱۰۲۳ گره است که از این تعداد ، ۵۱۲ تای آنها برگ هستند (و مسلما گرههای با اندیس بزرگتر مساوی ۱۰۰۰ هم در همین سطح هستند ) پس ۲۳ عدد برگ بیشتر از ۱۰۰۰ هست
بخش دوم سئوال رو متوجه نمیشم.بعدا روش فکر میکنم
(۱۴ آذر ۱۳۹۱ ۱۰:۳۶ ب.ظ)fatima1537 نوشته شده توسط: به نظر من:خب درست میگید اما فکر کنم که شما دارید Minheap در نظر میگیرید ها!
در سطح ۰ که گره ریشه است ۱ گره دارد ، ۰^۲=۱
درسطح ۱ ، تعداد گرهها [tex]2^{1}[/tex] - و مجموعا تا اینجا [tex]2^{1 1} - 1[/tex] گره در درخت موجود است
سطح ۲ ، [tex]2^{2}[/tex]- و مجموعا تا اینجا [tex]2^{2 1} - 1[/tex] گره در درخت موجود است
(اگر شماره هر سطح را n فرض کنیم ، در هر سطح تعداد گرهها برابر [tex]2^{n}[/tex] است و تعداد کل گرههای موجود [tex]2^{n 1}-1[/tex] است )
پس سطح ۹ ، ۵۱۲ برگ دارد چون ۹^۲= ۵۱۲ و مجموعا تا اینجا [tex]2^{9 1}-1[/tex]گره در درخت موجود است
پس این درخت تا سطح ۹ کلا دارای ۱۰۲۳ گره است که از این تعداد ، ۵۱۲ تای آنها برگ هستند (و مسلما گرههای با اندیس بزرگتر مساوی ۱۰۰۰ هم در همین سطح هستند ) پس ۲۳ عدد برگ بیشتر از ۱۰۰۰ هست
بخش دوم سئوال رو متوجه نمیشم.بعدا روش فکر میکنم
صورت سوال گفته Haxheap!!!
(۱۴ آذر ۱۳۹۱ ۰۹:۱۲ ب.ظ)sir_ams نوشته شده توسط:(14 آذر ۱۳۹۱ ۰۶:۴۱ ب.ظ)svk7 نوشته شده توسط: هیپ درخت کامله.و چون ۱۰۲۳ تا نود داره پس پره. نودهای نارنجی و سبز رنگ برگتر از ۱۰۰۰ هستند
ممنون
میشه یه کم توضیح هم بدید!(نود هاتون رو هم عدد بذارید.ممنون
سمت راست گره ها هم نود هست دیگه؟
هیپ درخت تقریبا کامله! چون میتونه یه گره داشته باشه که فقط فرزند چپ داره.
برگی که از ۱۰۰۰ بزرگتر باشه ،باید نودهای از ریشه تا این برگ هم از هزار بیستر و از مقدار خود برگ هم بیشتر باشه
اره چون دیگه احتیاجی بهشون نبود نکشیدم
چرا تقریبا کامل؟ هیپ در خته کاملی است چه میخواد max heap باشه یا min heap .
چون این درخت ۱۰۲۳ تا نود داره و هیپ هم هست بهمین دلیل این درخت پر میشه (و ارتفاعش هم ۱۰ ،البته اگه ارتفاع سطح اول رو یک در نظر بگیریم )
(۱۴ آذر ۱۳۹۱ ۱۱:۲۰ ب.ظ)sir_ams نوشته شده توسط: خب درست میگید اما فکر کنم که شما دارید Minheap در نظر میگیرید ها!دراون صورت میشه ۱۵ گره
صورت سوال گفته Haxheap!!!
چون درخت برای ایجاد کلیدهای ۱ تا ۱۰۲۳ باید تا سطح ۹ رشد داته باشه . و اگربه ترتیب از ریشه شروع کنیم و بزرگترین مقدار را به ریشه بدهیم (۱۰۲۳) و به همین ترتیب پایین بیاییم و به هرگره فرزند ، یکی کمتر از پدر خودش مقدار بدیم(مثلا در سطح دوم عدد ۱۰۲۲ و در سطح سوم عدد ۱۰۲۱ و... به همین ترتیب تا سطح ۹ پایین بیاییم )در سطح آخر عدد ۱۰۱۵ قرار میگیرد ، و سایر کلیدهای بزرگتر از ۱۰۰۰ (۱۰۱۴،۱۰۱۳ و...) هم میتوانند به عنوان برگ در آخرین سطح قرار بگیرند . پس تعداد کلیدهای بیشتر از ۱۰۰۰ که برگ هم هستند میشود ۱۵تا
(۱۵ آذر ۱۳۹۱ ۰۴:۱۳ ب.ظ)fatima1537 نوشته شده توسط: دراون صورت میشه ۱۵ گره
چون درخت برای ایجاد کلیدهای ۱ تا ۱۰۲۳ باید تا سطح ۹ رشد داته باشه . و اگربه ترتیب از ریشه شروع کنیم و بزرگترین مقدار را به ریشه بدهیم (۱۰۲۳) و به همین ترتیب پایین بیاییم و به هرگره فرزند ، یکی کمتر از پدر خودش مقدار بدیم(مثلا در سطح دوم عدد ۱۰۲۲ و در سطح سوم عدد ۱۰۲۱ و... به همین ترتیب تا سطح ۹ پایین بیاییم )در سطح آخر عدد ۱۰۱۵ قرار میگیرد ، و سایر کلیدهای بزرگتر از ۱۰۰۰ (۱۰۱۴،۱۰۱۳ و...) هم میتوانند به عنوان برگ در آخرین سطح قرار بگیرند . پس تعداد کلیدهای بیشتر از ۱۰۰۰ که برگ هم هستند میشود ۱۵تا
این ۱۵ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
[/quote]
(۰۹ دى ۱۳۹۱ ۰۷:۴۵ ب.ظ)mp1368 نوشته شده توسط: این ۱۵ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!من که حساب میکنم میشه ۸ تا ولی کتابا میگن ۱۵ تا.
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
پاسخنامه ها رو که بررسی کردم اینجوری نوشتن تا سطح ۹ همه باید بزرگتر از ۱۰۰۰ باشنه که میشه ۹تا بعدش ۲۳-۹ میکنن بعد میگن خوب بقیه رو که ۱۴ یا ۱۵ تاس رو میریزیم سطح آخر مگه میشه (مگه به قوله دوستمون واسط نمیخوان)
(۱۰ دى ۱۳۹۱ ۱۰:۵۶ ب.ظ)svk7 نوشته شده توسط: من که حساب میکنم میشه ۸ تا ولی کتابا میگن ۱۵ تا.کتابا یه جوری میگن انگار که در خت دودویی نیس
سلام .
همیشه هرچی کتاب گفت رو نباید قبول کرد و بیای همونو تکرار کنی .
دوست من تحلیلت کاملا درسته چون اصولی جواب دادی.
پ.ن : اینم یادت باشه که معلوم نیست طراح اون لحظه چی تو کَلَش بوده و این سوال رو طرح کرده . باید پیداش کنیم و بیاریم مانشت بینم جواب این تست رو خودشم میدونه یا نه !!!!!!!!!!
ارتفاع درخت ۹ است.پس مقدار هر برگ باید از ۹ عنصر دیگر کمتر باشد. .پس اعداد ۱۰۰۱ تا ۱۰۱۴ ممکن است در برگ باشند.اما عدد ۱۰۱۵ و اعداد دیگر نمی توانند.
یعنی ۱۴ تا.
(۲۶ دى ۱۳۹۱ ۰۱:۱۵ ب.ظ)csharpisatechnology نوشته شده توسط: ارتفاع درخت ۹ است.پس مقدار هر برگ باید از ۹ عنصر دیگر کمتر باشد. .پس اعداد ۱۰۰۱ تا ۱۰۱۴ ممکن است در برگ باشند.اما عدد ۱۰۱۵ و اعداد دیگر نمی توانند.
یعنی ۱۴ تا.
سوال گفته همزمان
میشه بگید کدوم کتاب گفته ۱۵ تا ؟
(۲۷ دى ۱۳۹۱ ۰۱:۰۲ ق.ظ)csharpisatechnology نوشته شده توسط: میشه بگید کدوم کتاب گفته ۱۵ تا ؟
با ۱۴ یا ۱۵ مشکلی ندارم من میگم میشه ۸تا .درختش رو هم کشیدم ۸ تا بیشتر نتونستم جا بدم حالا نمیدونم شما چطوری به ۱۴ یا ۱۵ رسیدی اگه درختش رو نشون بدی ابهامات برطرف میشه
نکته ای که خودم بهش رسیدم اینه :
اگه ما در یک ماکس هیپ، n گره داشته باشیم به طوری که n، (توانی از ۲ ) منهای یک باشد(مثلا ۲^۴ -۱ = ۱۵) ،درخت حتما پر خواهد بود .لازم نیست این مطلبو حفظ کنیم.بلکه با کشیدن یک شکل ساده می تونیم درکش کنیم.
![[تصویر: big_leaf.gif]](https://img.manesht.ir/big_leaf.gif)