۰
subtitle
ارسال: #۱
  
سوالی از max-heap
ممنون میشم راهنمایی کنید
۱
ارسال: #۲
  
سوالی از max-heap
نکته ای که خودم بهش رسیدم اینه :
اگه ما در یک ماکس هیپ، n گره داشته باشیم به طوری که n، (توانی از ۲ ) منهای یک باشد(مثلا ۲^۴ -۱ = ۱۵) ،درخت حتما پر خواهد بود .لازم نیست این مطلبو حفظ کنیم.بلکه با کشیدن یک شکل ساده می تونیم درکش کنیم.
اگه ما در یک ماکس هیپ، n گره داشته باشیم به طوری که n، (توانی از ۲ ) منهای یک باشد(مثلا ۲^۴ -۱ = ۱۵) ،درخت حتما پر خواهد بود .لازم نیست این مطلبو حفظ کنیم.بلکه با کشیدن یک شکل ساده می تونیم درکش کنیم.
ارسال: #۳
  
RE: سوالی از max-heap
(۲۷ دى ۱۳۹۱ ۰۹:۳۰ ب.ظ)csharpisatechnology نوشته شده توسط: نکته ای که خودم بهش رسیدم اینه :
اگه ما در یک ماکس هیپ، n گره داشته باشیم به طوری که n، (توانی از ۲ ) منهای یک باشد(مثلا ۲^۴ -۱ = ۱۵) ،درخت حتما پر خواهد بود .لازم نیست این مطلبو حفظ کنیم.بلکه با کشیدن یک شکل ساده می تونیم درکش کنیم.
این ۱۴ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
۰
ارسال: #۴
  
RE: سوالی از max-heap
هیپ درخت کامله.و چون ۱۰۲۳ تا نود داره پس پره. نودهای نارنجی و سبز رنگ برگتر از ۱۰۰۰ هستند
ارسال: #۵
  
RE: سوالی از max-heap
(۱۴ آذر ۱۳۹۱ ۰۶:۴۱ ب.ظ)svk7 نوشته شده توسط: هیپ درخت کامله.و چون ۱۰۲۳ تا نود داره پس پره. نودهای نارنجی و سبز رنگ برگتر از ۱۰۰۰ هستند
ممنون
میشه یه کم توضیح هم بدید!(نود هاتون رو هم عدد بذارید.ممنون
سمت راست گره ها هم نود هست دیگه؟
هیپ درخت تقریبا کامله! چون میتونه یه گره داشته باشه که فقط فرزند چپ داره.
۰
ارسال: #۶
  
سوالی از max-heap
به نظر من:
در سطح ۰ که گره ریشه است ۱ گره دارد ، ۰^۲=۱
درسطح ۱ ، تعداد گرهها [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]گره در درخت موجود است
پس این درخت تا سطح ۹ کلا دارای ۱۰۲۳ گره است که از این تعداد ، ۵۱۲ تای آنها برگ هستند (و مسلما گرههای با اندیس بزرگتر مساوی ۱۰۰۰ هم در همین سطح هستند ) پس ۲۳ عدد برگ بیشتر از ۱۰۰۰ هست
بخش دوم سئوال رو متوجه نمیشم.بعدا روش فکر میکنم
در سطح ۰ که گره ریشه است ۱ گره دارد ، ۰^۲=۱
درسطح ۱ ، تعداد گرهها [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]گره در درخت موجود است
پس این درخت تا سطح ۹ کلا دارای ۱۰۲۳ گره است که از این تعداد ، ۵۱۲ تای آنها برگ هستند (و مسلما گرههای با اندیس بزرگتر مساوی ۱۰۰۰ هم در همین سطح هستند ) پس ۲۳ عدد برگ بیشتر از ۱۰۰۰ هست
بخش دوم سئوال رو متوجه نمیشم.بعدا روش فکر میکنم
۰
ارسال: #۷
  
سوالی از max-heap
(۱۴ آذر ۱۳۹۱ ۱۰:۳۶ ب.ظ)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!!!
۰
ارسال: #۸
  
سوالی از max-heap
(۱۴ آذر ۱۳۹۱ ۱۱:۲۰ ب.ظ)sir_ams نوشته شده توسط: خب درست میگید اما فکر کنم که شما دارید Minheap در نظر میگیرید ها!دراون صورت میشه ۱۵ گره
صورت سوال گفته Haxheap!!!
چون درخت برای ایجاد کلیدهای ۱ تا ۱۰۲۳ باید تا سطح ۹ رشد داته باشه . و اگربه ترتیب از ریشه شروع کنیم و بزرگترین مقدار را به ریشه بدهیم (۱۰۲۳) و به همین ترتیب پایین بیاییم و به هرگره فرزند ، یکی کمتر از پدر خودش مقدار بدیم(مثلا در سطح دوم عدد ۱۰۲۲ و در سطح سوم عدد ۱۰۲۱ و... به همین ترتیب تا سطح ۹ پایین بیاییم )در سطح آخر عدد ۱۰۱۵ قرار میگیرد ، و سایر کلیدهای بزرگتر از ۱۰۰۰ (۱۰۱۴،۱۰۱۳ و...) هم میتوانند به عنوان برگ در آخرین سطح قرار بگیرند . پس تعداد کلیدهای بیشتر از ۱۰۰۰ که برگ هم هستند میشود ۱۵تا
ارسال: #۹
  
RE: سوالی از max-heap
(۱۵ آذر ۱۳۹۱ ۰۴:۱۳ ب.ظ)fatima1537 نوشته شده توسط: دراون صورت میشه ۱۵ گره
چون درخت برای ایجاد کلیدهای ۱ تا ۱۰۲۳ باید تا سطح ۹ رشد داته باشه . و اگربه ترتیب از ریشه شروع کنیم و بزرگترین مقدار را به ریشه بدهیم (۱۰۲۳) و به همین ترتیب پایین بیاییم و به هرگره فرزند ، یکی کمتر از پدر خودش مقدار بدیم(مثلا در سطح دوم عدد ۱۰۲۲ و در سطح سوم عدد ۱۰۲۱ و... به همین ترتیب تا سطح ۹ پایین بیاییم )در سطح آخر عدد ۱۰۱۵ قرار میگیرد ، و سایر کلیدهای بزرگتر از ۱۰۰۰ (۱۰۱۴،۱۰۱۳ و...) هم میتوانند به عنوان برگ در آخرین سطح قرار بگیرند . پس تعداد کلیدهای بیشتر از ۱۰۰۰ که برگ هم هستند میشود ۱۵تا
این ۱۵ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
۰
ارسال: #۱۰
  
سوالی از max-heap
[/quote]
پاسخنامه ها رو که بررسی کردم اینجوری نوشتن تا سطح ۹ همه باید بزرگتر از ۱۰۰۰ باشنه که میشه ۹تا بعدش ۲۳-۹ میکنن بعد میگن خوب بقیه رو که ۱۴ یا ۱۵ تاس رو میریزیم سطح آخر مگه میشه (مگه به قوله دوستمون واسط نمیخوان)
(۰۹ دى ۱۳۹۱ ۰۷:۴۵ ب.ظ)mp1368 نوشته شده توسط: این ۱۵ تا گره ی سطح آخر که از ۱۰۰۰ بزرگترن، به نظر شما پدرشون باید کیا باشن ؟؟؟؟!!!!!!!!!من که حساب میکنم میشه ۸ تا ولی کتابا میگن ۱۵ تا.
آیا گره ی مونده که بزرگتر از اینا باشه و به عنوان پدر واسشون انتخاب کنیم ؟؟؟؟!!!!!!!
پاسخنامه ها رو که بررسی کردم اینجوری نوشتن تا سطح ۹ همه باید بزرگتر از ۱۰۰۰ باشنه که میشه ۹تا بعدش ۲۳-۹ میکنن بعد میگن خوب بقیه رو که ۱۴ یا ۱۵ تاس رو میریزیم سطح آخر مگه میشه (مگه به قوله دوستمون واسط نمیخوان)
ارسال: #۱۱
  
RE: سوالی از max-heap
(۱۰ دى ۱۳۹۱ ۱۰:۵۶ ب.ظ)svk7 نوشته شده توسط: من که حساب میکنم میشه ۸ تا ولی کتابا میگن ۱۵ تا.کتابا یه جوری میگن انگار که در خت دودویی نیس
سلام .
همیشه هرچی کتاب گفت رو نباید قبول کرد و بیای همونو تکرار کنی .
دوست من تحلیلت کاملا درسته چون اصولی جواب دادی.
پ.ن : اینم یادت باشه که معلوم نیست طراح اون لحظه چی تو کَلَش بوده و این سوال رو طرح کرده . باید پیداش کنیم و بیاریم مانشت بینم جواب این تست رو خودشم میدونه یا نه !!!!!!!!!!
۰
ارسال: #۱۲
  
سوالی از max-heap
ارتفاع درخت ۹ است.پس مقدار هر برگ باید از ۹ عنصر دیگر کمتر باشد. .پس اعداد ۱۰۰۱ تا ۱۰۱۴ ممکن است در برگ باشند.اما عدد ۱۰۱۵ و اعداد دیگر نمی توانند.
یعنی ۱۴ تا.
یعنی ۱۴ تا.
ارسال: #۱۳
  
RE: سوالی از max-heap
۰
ارسال: #۱۵
  
RE: سوالی از max-heap
۰
ارسال: #۱۶
  
RE: سوالی از max-heap
اینکه آقای skv میگن من حساب میکنم ۸تا میشه و این دوستمون میگن ۱۴تا ،واسه این هست که یکی تعدادسطوح رو ۹گرفته یکی ۱۰
واسه ارتفاع هیپ داریم: log 1023 +1=10 (حدپاییین لگاریتم رو در نظر میگیریم )
پس ما ۱۰تا سطح داریم
آقامحمد اگه طبق مثال خودتون هم بریم با توجه به مثالی که واسه ۷تا گره زدین و۳سطح داشتیم پس واسه ۱۰۲۳ هم ۱۰ میشه یعنی logn+1
پس با ۱۰ تا گره طبق اون شکلی که آقای skvگذاشتن پیش میریم
که من با اجازه شون اعداد رو هم توی شکل گذاشتم که با توجه به شکل فقط ۸تا برگ بزرگتر از ۱۰۰۰هستند
واسه ارتفاع هیپ داریم: log 1023 +1=10 (حدپاییین لگاریتم رو در نظر میگیریم )
پس ما ۱۰تا سطح داریم
آقامحمد اگه طبق مثال خودتون هم بریم با توجه به مثالی که واسه ۷تا گره زدین و۳سطح داشتیم پس واسه ۱۰۲۳ هم ۱۰ میشه یعنی logn+1
پس با ۱۰ تا گره طبق اون شکلی که آقای skvگذاشتن پیش میریم
که من با اجازه شون اعداد رو هم توی شکل گذاشتم که با توجه به شکل فقط ۸تا برگ بزرگتر از ۱۰۰۰هستند
۰
ارسال: #۱۷
  
سوالی از max-heap
اصلا ربطی به سطوح نداره جناب maryam.raz.
--
من همه چیزو اثبات کردم.
---
چند نکته طبق کتاب پروفسور قدسی:
سطح ریشه یک است و بقیه ی سطوح به ترتیب یکی یکی زیاد میشن.
دقت کنید که منظور از عمق همون سطح هست.
و دقت کنید که عمق(سطح) ، با ارتفاع فرق داره.
ارتفاع درخت میشه ارتفاع ریشه. یعنی طول بلندترین مسیر رو به پایین تا برگ.
عمق درخت میشه عمق (سطح)آخرین برگ.
ارتفاق درخت، یکی کمتر از عمق درخت هست.
------------
جوابی که دادم کامل هست.
لطفا دوباره بخونیدش
ضمنا ما ۱۰ سطح داریم و ارتفاع ۹ هست. و هیچ جایی رو اشتباه نکردم.
ضمنا جناب skv7 ، پدر گره ها هم مهم نیست.هر چی باشه فقط گره های ۱ تا ۱۰۱۴ می تونن برگ باشن. در صورتی که ادعا می کنید گره ی دیگه ای می تونه برگ باشه مثال من رو نقض کنید. در ضمن سطح ریشه حتما باید ۱ فرض بشه و ارتفاع برگ ها هم صفر هست و ارتفاع درختی با ۱۰۲۳ گره اگه maxHeap باشه میشه ۹ و تعداد سطوحش میشه ۱۰/
اگه در مورد سطح و ارتفاع می خواید بدونیدفقط جزوه ی دکتر قدسی از دانشگاه شریف رو بخونید.
هر سوال دیگه ای هم بود یا تاپیک بزنید یا خصوصی بپرسید رفع ابهام کنم.زیرا جوابی که دادم کامل هست.
--
من همه چیزو اثبات کردم.
---
چند نکته طبق کتاب پروفسور قدسی:
سطح ریشه یک است و بقیه ی سطوح به ترتیب یکی یکی زیاد میشن.
دقت کنید که منظور از عمق همون سطح هست.
و دقت کنید که عمق(سطح) ، با ارتفاع فرق داره.
ارتفاع درخت میشه ارتفاع ریشه. یعنی طول بلندترین مسیر رو به پایین تا برگ.
عمق درخت میشه عمق (سطح)آخرین برگ.
ارتفاق درخت، یکی کمتر از عمق درخت هست.
------------
جوابی که دادم کامل هست.
لطفا دوباره بخونیدش
ضمنا ما ۱۰ سطح داریم و ارتفاع ۹ هست. و هیچ جایی رو اشتباه نکردم.
ضمنا جناب skv7 ، پدر گره ها هم مهم نیست.هر چی باشه فقط گره های ۱ تا ۱۰۱۴ می تونن برگ باشن. در صورتی که ادعا می کنید گره ی دیگه ای می تونه برگ باشه مثال من رو نقض کنید. در ضمن سطح ریشه حتما باید ۱ فرض بشه و ارتفاع برگ ها هم صفر هست و ارتفاع درختی با ۱۰۲۳ گره اگه maxHeap باشه میشه ۹ و تعداد سطوحش میشه ۱۰/
اگه در مورد سطح و ارتفاع می خواید بدونیدفقط جزوه ی دکتر قدسی از دانشگاه شریف رو بخونید.
هر سوال دیگه ای هم بود یا تاپیک بزنید یا خصوصی بپرسید رفع ابهام کنم.زیرا جوابی که دادم کامل هست.
۰
ارسال: #۱۸
  
سوالی از max-heap
maryam.raz که گفتید : که من با اجازه شون اعداد رو هم توی شکل گذاشتم که با توجه به شکل فقط ۸تا برگ بزرگتر از ۱۰۰۰هستند
----------
پاسختون :
دقت کنید که ما می تونیم جابجاییهارو انجام بدیم به طوری که باز هم هر گره از فرزندانش بزرگتر باشه و درخت ماکس هیپ بشه.یعنی بعضی برگ ها می تونند تغییر کنند.ولی در کل همون گره های تا ۱ تا ۱۰۱۴ طبق نکاتی که گفتم باید بتونند توی برگ های قرار بگیرند در غیر اینصورت درخت maxHeap نخواهد بود. می تونید نکته ای رو که توی عکس نشون دادم توی یه مثال طبق همون شکل که گفتم تست کنید.
----------
پاسختون :
دقت کنید که ما می تونیم جابجاییهارو انجام بدیم به طوری که باز هم هر گره از فرزندانش بزرگتر باشه و درخت ماکس هیپ بشه.یعنی بعضی برگ ها می تونند تغییر کنند.ولی در کل همون گره های تا ۱ تا ۱۰۱۴ طبق نکاتی که گفتم باید بتونند توی برگ های قرار بگیرند در غیر اینصورت درخت maxHeap نخواهد بود. می تونید نکته ای رو که توی عکس نشون دادم توی یه مثال طبق همون شکل که گفتم تست کنید.
۰
ارسال: #۱۹
  
سوالی از max-heap
این مطلبی که میگین درسته
من قبول دارم که گره با شماره ۱۰۱۴ هم میتونه برگ باشه
ولی نمیتونیم بگیم از ۱تا ۱۰۱۴ هم میتونه برگ باشه
آخه اگه ۱۴ تا برگ داریم اونم توی سطح ۱۰، چه جوری میتونیم فقط با ده تا گره واسشون والدهایی بذاریم که تا ریشه برسه؟
اگه طبق گفته خودتون ۱۰تا سطح داریم پس شکل ما درسته دیگه
شما اگه لطف کنید از روی همین شکل این ۱تا ۱۰۱۴ رو بنویسید با والدهایی که بزرگترن ممنون میشیم
بالاخره باید به جواب یکسان برسیم
من قبول دارم که گره با شماره ۱۰۱۴ هم میتونه برگ باشه
ولی نمیتونیم بگیم از ۱تا ۱۰۱۴ هم میتونه برگ باشه
آخه اگه ۱۴ تا برگ داریم اونم توی سطح ۱۰، چه جوری میتونیم فقط با ده تا گره واسشون والدهایی بذاریم که تا ریشه برسه؟
اگه طبق گفته خودتون ۱۰تا سطح داریم پس شکل ما درسته دیگه
شما اگه لطف کنید از روی همین شکل این ۱تا ۱۰۱۴ رو بنویسید با والدهایی که بزرگترن ممنون میشیم
بالاخره باید به جواب یکسان برسیم
۰
ارسال: #۲۰
  
سوالی از max-heap
دوست من ، من نمی گم ۱۴ تا گره بزرگتر از ۱۰۰۰ همزمان می تونه برگ باشه.
بلکه می گم گره هایی که می تونند توی این ماکس هیپ جزو برگ ها باشن فقط می تونن از بین گره های ۱ تا ۱۰۱۴ انتخاب بشن. یعنی فقط این گره ها می تونن برگ باشن.
حالا سوال خواسته از بین این گره ها مشخص کنیم چند تاشون از ۱۰۰۰ بزرگ ترن که از ۱۰۰۱ میشه تا ۱۰۱۴ دیگه.
توی سوال گفته کدوم گره ها می تونه برگ باشن(و تعداد برگ ها رو نخواسته)(تعداد گره های هر سطح میشه ۲ به توان (سطح منهای ۱)(دقت کنید که سطح ریشه حتما از ۱ شروع خواهد شد)
فقط گفته کدوم گره ها می تونن برگ باشن.
منم جواب دقیق رو دادم و صد در صدر جوابی که من دادم بر طبق سوالی که مطرح فرمودن درست هست.
اگه خوب دقت کنید و سوال رو بخونید می بینید جواب من از همه کامل تره.خواهش می کنم از همه ی دوستان تمام جواب های من رو خوب بخونید و عکسی که گذاشتم رو هم ببینید.
شما میاد ابتدا ۱۰۲۳ رو با ۱ جمع می کنید میشه ۱۰۲۴ حالا لگاریتمشو در مبنای ۲ می گیرید میشه ۱۰ پس ۱۰ سطح داریم حالا میاید از ۱۰۲۳ میشمارید تا سطح ۱۰ میشه :
چپ ترین گره سطح ۱: ۱۰۲۳
چپ ترین گره سطح ۲: ۱۰۲۲
چپ ترین گره سطح ۳: ۱۰۲۱
چپ ترین گره سطح ۴: ۱۰۲۰
چپ ترین گره سطح ۵: ۱۰۱۹
چپ ترین گره سطح ۶: ۱۰۱۸
چپ ترین گره سطح ۷: ۱۰۱۷
چپ ترین گره سطح ۸: ۱۰۱۶
چپ ترین گره سطح ۹: ۱۰۱۵
چپ ترین گره سطح ۱۰: ۱۰۱۴
----------------
می فهمیم که بزرگترین برگ باید ۱۰۱۴ باشه.
پس گره های ۱ تا ۱۰۱۴ فقط می تونن برگ باشن.(نمی گم همه ی اینا همزمان_بلکه میگم بعضی از اینها می تونن با هم برگ باشن و فقط برگ ها باید از همین مجموعه باشه و عدد دیگه ای نخواهد بود)
------------
نکته :قانون داریم که ثابت شده گره های ۱ تا بزرگترین برگ می تونند توی ماکس هیپ برگ باشن.
اگه باور ندارید مثالی میزنم :
یه ماکس هیپ با ۱۵ گره رسم کنید(دقت کنید که طبق این سوال تعداد گره های ماکس هیپمون باید توانی از ۲ منهای یک باشه مثل ۲ به توان ۴ منهای ۱ که میشه ۱۶-۱=۱۵ )
حالا ۱۵+۱ میشه ۱۶ از ۱۶ لگاریتم می گیریم میشه ۴ سطح.
حالا میاید از ۱۵میشمارید تا سطح ۴میشه :
چپ ترین گره سطح ۱: ۱۵
چپ ترین گره سطح ۲: ۱۴
چپ ترین گره سطح ۳: ۱۳
چپ ترین گره سطح ۴: ۱۲
-----
می فهمیم که بزرگترین برگ باید ۱۲باشه.
پس گره های ۱ تا ۱۲ فقط می تونن برگ باشن
همچنین در سطح آخر باید ۲ به توان(۴-۱) گره یا ۸ گره داشته باشیم.
این ۸ برگ فقط باید از توی اعداد ۱ تا ۱۲ انتخاب بشن تا درختمون maxHeap باشه(یعنی هر گره از فرزندانش بزرگتر باشه)
اثباتشم توی سه مدل شکل دیگه نشون میدم(تورو خدا قبول کنید حرفام درسته خسته شدم از دستتون):
همونطور که معلومه گره های ۱ تا ۱۲ باید برگ باشن و ۱۳و۱۴و۱۵ نمی تونن.
هرجورم جابجایی میخواید انجام بدید به شرطی که هرگره از فرزنداش بزرگتر باشه.
بلکه می گم گره هایی که می تونند توی این ماکس هیپ جزو برگ ها باشن فقط می تونن از بین گره های ۱ تا ۱۰۱۴ انتخاب بشن. یعنی فقط این گره ها می تونن برگ باشن.
حالا سوال خواسته از بین این گره ها مشخص کنیم چند تاشون از ۱۰۰۰ بزرگ ترن که از ۱۰۰۱ میشه تا ۱۰۱۴ دیگه.
توی سوال گفته کدوم گره ها می تونه برگ باشن(و تعداد برگ ها رو نخواسته)(تعداد گره های هر سطح میشه ۲ به توان (سطح منهای ۱)(دقت کنید که سطح ریشه حتما از ۱ شروع خواهد شد)
فقط گفته کدوم گره ها می تونن برگ باشن.
منم جواب دقیق رو دادم و صد در صدر جوابی که من دادم بر طبق سوالی که مطرح فرمودن درست هست.
اگه خوب دقت کنید و سوال رو بخونید می بینید جواب من از همه کامل تره.خواهش می کنم از همه ی دوستان تمام جواب های من رو خوب بخونید و عکسی که گذاشتم رو هم ببینید.
شما میاد ابتدا ۱۰۲۳ رو با ۱ جمع می کنید میشه ۱۰۲۴ حالا لگاریتمشو در مبنای ۲ می گیرید میشه ۱۰ پس ۱۰ سطح داریم حالا میاید از ۱۰۲۳ میشمارید تا سطح ۱۰ میشه :
چپ ترین گره سطح ۱: ۱۰۲۳
چپ ترین گره سطح ۲: ۱۰۲۲
چپ ترین گره سطح ۳: ۱۰۲۱
چپ ترین گره سطح ۴: ۱۰۲۰
چپ ترین گره سطح ۵: ۱۰۱۹
چپ ترین گره سطح ۶: ۱۰۱۸
چپ ترین گره سطح ۷: ۱۰۱۷
چپ ترین گره سطح ۸: ۱۰۱۶
چپ ترین گره سطح ۹: ۱۰۱۵
چپ ترین گره سطح ۱۰: ۱۰۱۴
----------------
می فهمیم که بزرگترین برگ باید ۱۰۱۴ باشه.
پس گره های ۱ تا ۱۰۱۴ فقط می تونن برگ باشن.(نمی گم همه ی اینا همزمان_بلکه میگم بعضی از اینها می تونن با هم برگ باشن و فقط برگ ها باید از همین مجموعه باشه و عدد دیگه ای نخواهد بود)
------------
نکته :قانون داریم که ثابت شده گره های ۱ تا بزرگترین برگ می تونند توی ماکس هیپ برگ باشن.
اگه باور ندارید مثالی میزنم :
یه ماکس هیپ با ۱۵ گره رسم کنید(دقت کنید که طبق این سوال تعداد گره های ماکس هیپمون باید توانی از ۲ منهای یک باشه مثل ۲ به توان ۴ منهای ۱ که میشه ۱۶-۱=۱۵ )
حالا ۱۵+۱ میشه ۱۶ از ۱۶ لگاریتم می گیریم میشه ۴ سطح.
حالا میاید از ۱۵میشمارید تا سطح ۴میشه :
چپ ترین گره سطح ۱: ۱۵
چپ ترین گره سطح ۲: ۱۴
چپ ترین گره سطح ۳: ۱۳
چپ ترین گره سطح ۴: ۱۲
-----
می فهمیم که بزرگترین برگ باید ۱۲باشه.
پس گره های ۱ تا ۱۲ فقط می تونن برگ باشن
همچنین در سطح آخر باید ۲ به توان(۴-۱) گره یا ۸ گره داشته باشیم.
این ۸ برگ فقط باید از توی اعداد ۱ تا ۱۲ انتخاب بشن تا درختمون maxHeap باشه(یعنی هر گره از فرزندانش بزرگتر باشه)
اثباتشم توی سه مدل شکل دیگه نشون میدم(تورو خدا قبول کنید حرفام درسته خسته شدم از دستتون):
همونطور که معلومه گره های ۱ تا ۱۲ باید برگ باشن و ۱۳و۱۴و۱۵ نمی تونن.
هرجورم جابجایی میخواید انجام بدید به شرطی که هرگره از فرزنداش بزرگتر باشه.
۰
ارسال: #۲۱
  
سوالی از max-heap
دمش گرم fatima1537،که فقط ایشون حرفمو قبول کرد.دیگه توضیح نمیدم.چون جوابم کامل بود.بقیه رو خودتون فکر کنید.مطمئنم جوابم کامله.خواهش می کنم دقت کنید روی توضیحاتم
۰
ارسال: #۲۲
  
سوالی از max-heap
کاملا حرف csharpisatechnology درسته میشه ۱۴ تا. به همین دلیل که بزرگترین مقدار باید تو ریشه باشه و دومین مقدار بزرگ می تونه در سطح ۲ باشه و سومین مقدار بزرگ می تونه در سطح دو یا سه باشه، چهارمین میتونه در سطح دو،سه یا چهار باشه و الی آخر بنابراین. بنابراین در سطح آخر میشه ۱۰۱۴ قرار بگیره، همچنین اعداد کوچکتر که میشه ۱۴ تا
فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.
فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.
۰
ارسال: #۲۳
  
سوالی از max-heap
(۲۹ دى ۱۳۹۱ ۰۳:۰۸ ب.ظ)mahdiii نوشته شده توسط: فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.دقیقا همینطوره
من هم اون موقعی که جواب دادم منظورم پاسخ قسمت اول بود که توی ارسالم هم گفته بودم.روی بخش دوم سئوال فکر نکرده بودم.
۰
ارسال: #۲۴
  
سوالی از max-heap
(۲۹ دى ۱۳۹۱ ۰۳:۰۸ ب.ظ)mahdiii نوشته شده توسط: فکر کنم یه سوء تفاهم ایجاد شده. سوال دو قسمت داره یکی گفته به طور همزمان و دیگری نگفته خوب اگه به طور همزمان نخواد که گره های بیشتر از ۱۰۰۰ تو برگ باشن میشه همون ۱۴ (از ۱۰۰۱ تا ۱۰۱۴) اما اگه به طور همزمان بخواد همون ۸ تا میشه به نظر منم.
ممنون ابهامو برطرف کردی ، چند نفر داشتن قسمت اول سوالو حل میکردن ما هم قسمت دومو .در اصل بی دقتی از دو طرف بوده که منظوره همو نمیگرفتیم.
به امید پیشرفت علم
۰
ارسال: #۲۵
  
سوالی از max-heap
سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
۰
ارسال: #۲۶
  
سوالی از max-heap
(۳۰ دى ۱۳۹۱ ۰۱:۴۱ ق.ظ)csharpisatechnology نوشته شده توسط: سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
دوست عزیز .خوب سوال دو قسمته .تازه قسمت دوم به صورت صریح گفته همزمان.اگه این سوال همین شکلی تو کنکور میومد من ۸ میزدم (اگه تو گزینه ها بود)و گرنه نمیزدم.
احتمالا این تست نبوده وتمرین بوده
۰
ارسال: #۲۷
  
سوالی از max-heap
عکس قبلی هم یه جا سطح رو ۹ نوشته بودم اینم اصلاح کامل :
ضمنا در هر انجمن سعی میشه یه سوال پرسیده بشه.
اون سوالی که می گید همزمان یه چیز دیگست که مهم تر از این بحث هست و نیاز هست یه تاپیک جدای کامل رو هم به اون اختصاص بدیم.
همینطوری هم ننویسید ۸ تا چون اثباتش خیلی مهمه.
پیروز باشید.
از skv گل هم عذر می خوام.من قسمت دوم سوالو به خاطر بی دقتی خودم ندیده بودم.
اما اون ۸ باید یه فرمول کلی هم براش بدست آورد.خیلی مهمه اگه دوستان نکته ی دیگه ای راجع به اون ۸ یاد دارن اضافه کنن ممنون میشم.
(۳۰ دى ۱۳۹۱ ۱۱:۰۶ ق.ظ)svk7 نوشته شده توسط:انشاءا... طراح سوال جواباشو طوری میده که ابهام نباشه.در غیراینصورت اگه سوال دیگه ای دادن اعتراض می کنن دوستان.(30 دى ۱۳۹۱ ۰۱:۴۱ ق.ظ)csharpisatechnology نوشته شده توسط: سوال هیچ اشکالی نداره و ابهامی هم در کار نیست دوستان.تحلیل دوستان اشتباست.موفق باشید.
دوست عزیز .خوب سوال دو قسمته .تازه قسمت دوم به صورت صریح گفته همزمان.اگه این سوال همین شکلی تو کنکور میومد من ۸ میزدم (اگه تو گزینه ها بود)و گرنه نمیزدم.
احتمالا این تست نبوده وتمرین بوده
ضمنا در هر انجمن سعی میشه یه سوال پرسیده بشه.
اون سوالی که می گید همزمان یه چیز دیگست که مهم تر از این بحث هست و نیاز هست یه تاپیک جدای کامل رو هم به اون اختصاص بدیم.
همینطوری هم ننویسید ۸ تا چون اثباتش خیلی مهمه.
پیروز باشید.
از skv گل هم عذر می خوام.من قسمت دوم سوالو به خاطر بی دقتی خودم ندیده بودم.
اما اون ۸ باید یه فرمول کلی هم براش بدست آورد.خیلی مهمه اگه دوستان نکته ی دیگه ای راجع به اون ۸ یاد دارن اضافه کنن ممنون میشم.
ارسال: #۲۸
  
RE: سوالی از max-heap
(۰۵ بهمن ۱۳۹۱ ۰۲:۰۳ ق.ظ)csharpisatechnology نوشته شده توسط: انشاءا... طراح سوال جواباشو طوری میده که ابهام نباشه.در غیراینصورت اگه سوال دیگه ای دادن اعتراض می کنن دوستان.باز میگین اثبات کنیم که ۸تاست؟؟اینهمه اون بالا توضیح دادیم!
ضمنا در هر انجمن سعی میشه یه سوال پرسیده بشه.
اون سوالی که می گید همزمان یه چیز دیگست که مهم تر از این بحث هست و نیاز هست یه تاپیک جدای کامل رو هم به اون اختصاص بدیم.
همینطوری هم ننویسید ۸ تا چون اثباتش خیلی مهمه.
پیروز باشید.
از skv گل هم عذر می خوام.من قسمت دوم سوالو به خاطر بی دقتی خودم ندیده بودم.
اما اون ۸ باید یه فرمول کلی هم براش بدست آورد.خیلی مهمه اگه دوستان نکته ی دیگه ای راجع به اون ۸ یاد دارن اضافه کنن ممنون میشم.
واسه این درخت با این تعداد گره بصورت همزمان دیگه کامل توضیح دادیم وشکل هم رسم شدکه ۸تاست نیازی نیست که حتما فرمول کلی پیدا کنیم تا جواب قابل قبول باشه!
البته پیدا کردن یه فرمول کلی چیز خوبیه ولی خب کار راحتی نیست حالا اگه دوستان فرصت کردن و پیدا کردن ممنون میشیم اونوقت اگه نمونش تو کنکور بیاد میشه راحت تر زد
۰
۰
ارسال: #۳۰
  
سوالی از max-heap
منظورتون رو متوجه نمیشم.
این درخت نشون میده که نهایتا ۸ تا گره بزرگتر یا مساوی ۱۰۰۰ رو میشه در برگها به طور همزمان قرار داد
این درخت نشون میده که نهایتا ۸ تا گره بزرگتر یا مساوی ۱۰۰۰ رو میشه در برگها به طور همزمان قرار داد
۰
۰
ارسال: #۳۲
  
سوالی از max-heap
(۰۵ بهمن ۱۳۹۱ ۰۲:۰۳ ق.ظ)csharpisatechnology نوشته شده توسط: از skv گل هم عذر می خوام.من قسمت دوم سوالو به خاطر بی دقتی خودم ندیده بودم.خواهش میکنم دوست خوبم (مشکل از بی دقتی من هم بود)این بحث ها باعث میشه دیگه هر چی هست بچسبه تو مغزو راهه در رویی هم نداشته باشه
انشالله چهارشنبه یا پنج شنبه روز خوبی برامون باشه
موفق باشید
۰
ارسال: #۳۳
  
RE: سوالی از max-heap
نکته مهمی هست اونم اینه که در یک max heap (بزرگترین عنصر که در ریشه هست)، kامین بزرگترین عنصر میتونه از عمق ۲ تا k قرار بگیره.
اینجاهم کلا عمق ۱۰ و تعداد اعداد بزرگتر از ۱۰۰۰ ، ۲۲ عدد میباشد.
۱۰۰۰ بیست و سومین بزرگترین عدده و ۱۰۰۱ بیست و دومین عدد(از سطر ۲ تا ۲۲ میتواند باشد) و ... . با توجه به نکته از ۱۰۱۴ تا ۱۰۲۲ میتونن در عمق ۱۰ قرار بگیرن. که در کل ۱۴ عدد
اینجاهم کلا عمق ۱۰ و تعداد اعداد بزرگتر از ۱۰۰۰ ، ۲۲ عدد میباشد.
۱۰۰۰ بیست و سومین بزرگترین عدده و ۱۰۰۱ بیست و دومین عدد(از سطر ۲ تا ۲۲ میتواند باشد) و ... . با توجه به نکته از ۱۰۱۴ تا ۱۰۲۲ میتونن در عمق ۱۰ قرار بگیرن. که در کل ۱۴ عدد
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سوالی از دنباله ها و قوانین سیگما | fendi | ۱ | ۳,۰۶۷ |
۰۶ اردیبهشت ۱۳۹۸ ۰۲:۱۱ ق.ظ آخرین ارسال: Saman |
|
سوالی از sql | wskf | ۱ | ۱,۸۷۰ |
۰۱ بهمن ۱۳۹۵ ۱۱:۵۸ ب.ظ آخرین ارسال: alireza01 |
|
سوالی در خصوص کتاب بهروز قلی زاده | agha_Yahya | ۱ | ۲,۳۳۸ |
۰۳ مرداد ۱۳۹۵ ۰۴:۵۹ ب.ظ آخرین ارسال: Pure Liveliness |
|
سوالی در مورد تولید جمعیت اولیه الگوریتم ژنتیک | نازین | ۶ | ۵,۵۸۵ |
۰۹ تیر ۱۳۹۵ ۰۳:۱۳ ق.ظ آخرین ارسال: kingxerxes |
|
سوالی از گرامر های LL1 | saberz | ۱ | ۲,۳۸۰ |
۱۲ اسفند ۱۳۹۴ ۱۰:۵۰ ب.ظ آخرین ارسال: flower1 |
|
سوالی از ضرب آرایه ای | saberz | ۲ | ۲,۲۰۹ |
۱۲ اسفند ۱۳۹۴ ۰۴:۲۳ ب.ظ آخرین ارسال: Farzamm |
|
سوالی از مبحث حافظه | saberz | ۳ | ۲,۵۶۶ |
۰۴ اسفند ۱۳۹۴ ۰۹:۲۷ ب.ظ آخرین ارسال: saberz |
|
حل سوالی از وابستگی تابعی | saberz | ۱ | ۲,۰۹۰ |
۲۷ بهمن ۱۳۹۴ ۱۱:۳۶ ب.ظ آخرین ارسال: sixsixsix |
|
سوالی در مورد معافیت تحصیلی | alirezafchh | ۲ | ۲,۱۷۷ |
۱۱ شهریور ۱۳۹۴ ۰۱:۳۸ ب.ظ آخرین ارسال: mmm1374 |
|
سوالی از رادیکال تو در تو یا مسلسل | ali17 | ۱ | ۵,۶۲۶ |
۱۸ خرداد ۱۳۹۴ ۰۸:۳۳ ب.ظ آخرین ارسال: sammaneh |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close