صفحه‌ها: ۱ ۲
سلام.
سوال زیر فاقد گزینه ست,ممنون میشم جواب بدین.
سوال:
یک هرم بیشینه حاوی همه اعداد ۱ تا ۱۰۲۳ است.چه تعداد از اعداد بیشتر از ۱۰۰۰ می توانند برگ باشند؟
حداکثر چه تعداد از این اعداد میتوانند هم زمان برگ باشند؟
ممنونم از سوال قشنگتون. بهتره برای رسیدن به جواب درخت رو ترسیم کنید. البته همه درخت رو لازم نیست ترسیم کنید بلکه شاخه‍های پایینی رو رسم کنید.
در max-heap بزرگترین عدد در ریشه قرار می‍گیرد و فرزندها دارای مقدار کمتری هستند. به همین دلیل شما مجبور هستید که در یکی از شاخه‍ها(حداقل) از ۱۰۲۳ شروع کنید و تا ریشه که در ردیف ۱۰ام درخت قرار دارد پایین بیایید. حالا با اعداد باقی مانده سعی کنید که یک max-heap بسازید که اعداد بالاتر از ۱۰۰۰ را داشته باشد.
متاسفانه من الان نمی تونم شکلش رو براتون ترسیم کنم. با محاسبات من جواب برابر با ۸ خواهد بود.
(۰۵ دى ۱۳۸۹ ۰۹:۱۲ ب.ظ)fateme66 نوشته شده توسط: سلام.
سوال زیر فاقد گزینه ست,ممنون میشم جواب بدین.
سوال:
یک هرم بیشینه حاوی همه اعداد ۱ تا ۱۰۲۳ است.چه تعداد از اعداد بیشتر از ۱۰۰۰ می توانند برگ باشند؟
حداکثر چه تعداد از این اعداد میتوانند هم زمان برگ باشند؟
ارتفاع درخت ۱۰ میباشد(ریشه در سطح ۱ فرض شده) چراکه میدانیم یک هرم بیشینه یک درخت متوازن است پس باید ارتفاع آن ۱۰ باشد(برگها در عمق ۱۰) . با توجه به تعریف هرم بیشینه باید والد هر گره از خود گره بزرگتر باشد پس برای داشتن بیشترین تعداد عنصر بزرگتر از ۱۰۰۰ باید یک مسیر (زیر درخت چپ)داشته باشیم بطول ۹ (غیر ریشه ۱ -۱۰ =۹) که عناصر با افزایش ارتفاع کوچکتر شوند، مسیر دیگر یا در واقع زیر درخت دیگر مهم نیست فرض کنید از ۹۹۹ شروع به کم شدن میکند( از بالا به پایین عناصر کوچکتر میشود) . در واقع ۹ مقدار را باید از دست بدهیم تا به سطح برگها برسیم و از خود دهمین مقدار شروع میشود (۱۰-۱۰۲۳) تا به ۱۰۰۰ برسیم
نتیجه: تعداد عناصر برگ بزرگتر از ۱۰۰۰ برابر است با ۱۴ = ۹ - ۲۳
توجه: مقدار ۲۳ در بالا تعدا عناصر بزرگتر از ۱۰۰۰ است
منم برای حالت همزمان ۸ بدست آوردم.
همونطور که Masoud05 گفت ارتفاع ۱۰ هست و ۹ مقدار از دست میدهیم که به برگ برسیم و دو تا رو توی برگ قرار دهیم.۱ مقدار دیگر هم در ارتفاع ۹ از دست میدهیم و دو تای دیگه رو در برگ قرار میدهیم.با از دست دادن دو مقدار در ارتفاع های ۸ و ۹ باز می توانیم دو تای دیگه رو در برگ قرار میدهیم.و در نهایت باز دست دادن یک مقدار در ارتفاع ۹ می توانیم دو تای دیگه رو در برگ قرار میدهیم.که در مجموع میشود ۸ تا در حالت هم زمان.
نقل قول: ارتفاع درخت ۱۰ میباشد(ریشه در سطح ۱ فرض شده) چراکه میدانیم یک هرم بیشینه یک درخت متوازن است پس باید ارتفاع آن ۱۰ باشد(برگها در عمق ۱۰) . با توجه به تعریف هرم بیشینه باید والد هر گره از خود گره بزرگتر باشد پس برای داشتن بیشترین تعداد عنصر بزرگتر از ۱۰۰۰ باید یک مسیر (زیر درخت چپ)داشته باشیم بطول ۹ (غیر ریشه ۱ -۱۰ =۹) که عناصر با افزایش ارتفاع کوچکتر شوند، مسیر دیگر یا در واقع زیر درخت دیگر مهم نیست فرض کنید از ۹۹۹ شروع به کم شدن میکند( از بالا به پایین عناصر کوچکتر میشود) . در واقع ۹ مقدار را باید از دست بدهیم تا به سطح برگها برسیم و از خود دهمین مقدار شروع میشود (۱۰-۱۰۲۳) تا به ۱۰۰۰ برسیم
نتیجه: تعداد عناصر برگ بزرگتر از ۱۰۰۰ برابر است با ۱۴ = ۹ - ۲۳
توجه: مقدار ۲۳ در بالا تعدا عناصر بزرگتر از ۱۰۰۰ است.
دوست عزیز جوابتون درست نیست.
درسته که با فدا کردن ۹ تا می رسیم به برگ اما این تنها برای برگ شدن یکی از اعداد بین ۱۰۰۰ تا ۱۰۲۳ کافیه. برای ساخت برگ بعدی مجبور می‍شیم که از مسیرهای کناری برسیم به برگ. و برای رسیدن به اونها هم برخی از اعداد بین ۱۰۰۰ تا ۱۰۲۳ تلف خواهند شد.
من در جوابی که به سوال دادم کوچکترین شکی رو ندارم.
راستی توجه داشته باشید که max-heap یک درخت کامل است.
من راه حل خودم رو گفتم .
توی کتاب پوران هم شبیه به حل من و جوابی که من دادم اومده اصلاً این تست کنکور علوم ۸۳ بوده.
البته توی صورت سوال گفته در پایین ترین سطح و نه برگ . مگه منظور از آخرین سطح برگ نیست؟
در ضمن توی گزینه‌ها حداقل گزینه ۱۰ هست!!!
(۰۵ دى ۱۳۸۹ ۱۱:۴۴ ب.ظ)Masoud05 نوشته شده توسط: من راه حل خودم رو گفتم .سوال علوم کامپیوتر همون قسمت اول سوال اینجا هست و منظورش تعداد اعدادی هست که توی پایین ترین سطح می تونند باشند.ولی حرفی از همزمانی نیاورده.و جوابی که شما هم دادید برای این قسمت بود.
توی کتاب پوران هم شبیه به حل من و جوابی که من دادم اومده اصلاً این تست کنکور علوم ۸۳ بوده.
البته توی صورت سوال گفته در پایین ترین سطح و نه برگ . مگه منظور از آخرین سطح برگ نیست؟
در ضمن توی گزینه‌ها حداقل گزینه ۱۰ هست!!!
ولی جوابی که من و دکتر دادیم برای قسمت دوم سوال بود که گفته بود که همزمان برگ باشند.من دیدم قسمت اول ساده است و شما هم جوابشو دادید برای همین فقط قسمت دومو جواب دادم.
(۰۶ دى ۱۳۸۹ ۱۲:۱۲ ق.ظ)حامد نوشته شده توسط:پس راه حلم برای قسمت اول درست بود؟ آخه من زیر سوال رو نگاه نکردم که ۲ قسمت داره و از اونجایی که تازه تست رو حل کردم سریع برای جواب رفتم.!!!(05 دى ۱۳۸۹ ۱۱:۴۴ ب.ظ)Masoud05 نوشته شده توسط: من راه حل خودم رو گفتم .سوال علوم کامپیوتر همون قسمت اول سوال اینجا هست و منظورش تعداد اعدادی هست که توی پایین ترین سطح می تونند باشند.ولی حرفی از همزمانی نیاورده.و جوابی که شما هم دادید برای این قسمت بود.
توی کتاب پوران هم شبیه به حل من و جوابی که من دادم اومده اصلاً این تست کنکور علوم ۸۳ بوده.
البته توی صورت سوال گفته در پایین ترین سطح و نه برگ . مگه منظور از آخرین سطح برگ نیست؟
در ضمن توی گزینه‌ها حداقل گزینه ۱۰ هست!!!
ولی جوابی که من و دکتر دادیم برای قسمت دوم سوال بود که گفته بود که همزمان برگ باشند.من دیدم قسمت اول ساده است و شما هم جوابشو دادید برای همین فقط قسمت دومو جواب دادم.
بی دقتی درد بزرگ منه
من فکر می‍کردم تنها حالت همزمانی مد نظر بوده. جواب شما برای سوال اولش درسته و تعداد همونیه که شما گفتین.
(۰۵ دى ۱۳۸۹ ۱۱:۲۰ ب.ظ)حامد نوشته شده توسط: منم برای حالت همزمان ۸ بدست آوردم.ممنون از توضیحتون خیلی جامع و کامل بود.
همونطور که Masoud05 گفت ارتفاع ۱۰ هست و ۹ مقدار از دست میدهیم که به برگ برسیم و دو تا رو توی برگ قرار دهیم.۱ مقدار دیگر هم در ارتفاع ۹ از دست میدهیم و دو تای دیگه رو در برگ قرار میدهیم.با از دست دادن دو مقدار در ارتفاع های ۸ و ۹ باز می توانیم دو تای دیگه رو در برگ قرار میدهیم.و در نهایت باز دست دادن یک مقدار در ارتفاع ۹ می توانیم دو تای دیگه رو در برگ قرار میدهیم.که در مجموع میشود ۸ تا در حالت هم زمان.
(۰۶ دى ۱۳۸۹ ۰۱:۱۱ ق.ظ)Masoud05 نوشته شده توسط: البته تعداد همزمان هم ۸ نمیشه( بهترین مقدار ۸ هست )
چراکه اگر ۸ تا نود در پایین ترین سطح باشه یعنی اونا ۴ تا والد دارن( همشون با هم، هر والد ۲ فرزند) و این ۴ تا ۲ والد دارن و از سطح بالاتر همگی ۱ والد دارن پس داریم:
۸+۴+۲+۱+۱+۱+۱+۱+۱+۱= ۲۱
طول رشته بالا ۱۰ که همون ارتفاع درخت می باشد .
در ضمن جواب هم ۹ نمی تونه باشه چون تعداد از ۲۳ بالا می زنه
دوست عزیز به صورت سوال دقت کن. ما دقیقاً دنبال بزرگترین مقدار هستیم. و این مقدار برابر با ۸ است.
(۰۵ دى ۱۳۸۹ ۱۰:۳۳ ب.ظ)admin نوشته شده توسط: ممنونم از سوال قشنگتون. بهتره برای رسیدن به جواب درخت رو ترسیم کنید. البته همه درخت رو لازم نیست ترسیم کنید بلکه شاخه‍های پایینی رو رسم کنید.
در max-heap بزرگترین عدد در ریشه قرار می‍گیرد و فرزندها دارای مقدار کمتری هستند. به همین دلیل شما مجبور هستید که در یکی از شاخه‍ها(حداقل) از ۱۰۲۳ شروع کنید و تا ریشه که در ردیف ۱۰ام درخت قرار دارد پایین بیایید. حالا با اعداد باقی مانده سعی کنید که یک max-heap بسازید که اعداد بالاتر از ۱۰۰۰ را داشته باشد.
متاسفانه من الان نمی تونم شکلش رو براتون ترسیم کنم. با محاسبات من جواب برابر با ۸ خواهد بود.
ممنون آقای دکتر, به جواب رسیدم.
خیلی خوبه که تو مانشت سوال بی جواب نمی مونه.
من هم به همون جواب هشت رسیدم
ممنون از همه دوستان!!
با توجه به شکل فقط ۸ برگ داریم که می توانند اعداد بیشتر از ۱۰۰۰ باشند.
دوست عزیز min-heap نیست! این شکلی که کشیدین min-heap هست.