انجمنصفحه اولجستجوی انجمن

[Masoud05]

[رضا_ایرانی]

گزینه دو میشه به نظرم.
درخت دودیی با بیشترین ارتفاع باید به صورت گره های تک فرزندی (مثلا اریب) باشه، یعنی برای داشتن یک درخت با ارتفاع h ما باید h گره داخلی تک عنصری (چون ارتفاع از صفر شروع میشه) و یک برگ به صورت آرایه با حداکثر ۲^h عنصر داشته باشیم. چون آرایه حداکثر عنصرش میشه ۲^h‌، پس تعداد گره‌ها باید کوچکتر مساوی باشه با:

۲^h + h

اگه اشتباه کردم دوستان که جواب تشریحی دارن بگن کدوم گزینه درسته.

(البته توی این توضیحم " h به توان دو " به معنی " دو به توان h " هست که وقت تایپ کردن نمیشه نوشتش. )

[mamat]

اما به نظر من گزینه یک درسته
سایر توضیحات مساله نقاط انحرافی هستن
در هر حالت حتی اگه ما درخت رو اوریب در نظر نگیریم یعنی با کمترین ارتفاع ممکن جواب یک صحیح است
حالا اگه ارتفاع ریادتر بشه یعنی h باز هم گزینه یک مناسب برای جواب است.
اشتباه نکنیم که همه جوابها صحیح هستند ولی گزینه ۱ به نظرم از همه گزینه‌ها صحیحتر است

[رضا_ایرانی]

(۲۲ شهریور ۱۳۹۰ ۰۲:۵۲ ب.ظ)mamat نوشته شده توسط:  اما به نظر من گزینه یک درسته
سایر توضیحات مساله نقاط انحرافی هستن
در هر حالت حتی اگه ما درخت رو اوریب در نظر نگیریم یعنی با کمترین ارتفاع ممکن جواب یک صحیح است
حالا اگه ارتفاع ریادتر بشه یعنی h باز هم گزینه یک مناسب برای جواب است.
اشتباه نکنیم که همه جوابها صحیح هستند ولی گزینه ۱ به نظرم از همه گزینه‌ها صحیحتر است

استدلال من بر این اساس بود که سوال صریحا درختی با بیشترین ارتفاع رو خواسته. اگر درخت با بیشترین ارتفاع در نظر گرفته بشه جواب دو درسته.

[mamat]

دوست عزیز فکر کنم شما دچار اشتباه شدید
ببینید مقدار n که هیچ تغییری نخواهد کرد اگه h زیاد بشه طرف دوم نامعادله یعنی( ۲ بتوان h )خیلی بیشتر از مقدار از h ای هستش که در زمان کمترین ارتفاع در نظر گرفته شده است.
برای مثال شما یک درخت دو دویی کامل رو در نظر بگیرین که n=7 است در این صورت h=2 در صورت صفر گرفتن غمق ریشه است است .حال جواب برابر ۷ کوچکتر مساوی ۲ بتوان ۲+۱ (یعنی ۳) است. یعنی ۸=>7
حالا فرض کن h بزرگتر شود مسلما این ۷ باز کمتر از طرف دیگر نامعادله خواهد بود.

[رضا_ایرانی]

(۲۲ شهریور ۱۳۹۰ ۰۴:۱۵ ب.ظ)mamat نوشته شده توسط:  دوست عزیز فکر کنم شما دچار اشتباه شدید
ببینید مقدار n که هیچ تغییری نخواهد کرد اگه h زیاد بشه طرف دوم نامعادله یعنی( ۲ بتوان h )خیلی بیشتر از مقدار از h ای هستش که در زمان کمترین ارتفاع در نظر گرفته شده است.
برای مثال شما یک درخت دو دویی کامل رو در نظر بگیرین که n=7 است در این صورت h=2 در صورت صفر گرفتن غمق ریشه است است .حال جواب برابر ۷ کوچکتر مساوی ۲ بتوان ۲+۱ (یعنی ۳) است. یعنی ۸=>7
حالا فرض کن h بزرگتر شود مسلما این ۷ باز کمتر از طرف دیگر نامعادله خواهد بود.

شما برگ آرایه ای رو در نظر نمیگیرید؟
شما فرض کنید که یک درخت کامل داریم با ارتفاع ۲، که در عمق ۲ یک برگ آرایه ای داره با تعداد چهار عنصر (دو به توان دو که حداکثر تعداد عناصر آرایه هست). یعنی جمعا در این درخت به تعداد چهار (عناصر موجود در آرایه )+ شش (که شش تعداد دیگر عناصر این درخت کامل هست). پس در این درخت ۱۰ گره وجود داره و n=10 . با توجه به گزینه ای که شما میگید درسته، داریم: ۸=>10 . پس گزینه رد میشه.

در ضمن به سوال توجه کنید: "در بین همه‌ی درختها با n عنصر، درختی با بیشترین ارتفاع رو در نظر بگیرید. اگر ارتفاع این درخت h باشد...". ما کاری به درخت کامل نداریم، ارتفاع درخت دودویی کامل logn هست و یک درخت دودویی میتونه بیشترین ارتفاع یعنی n رو داشته باشه.

لطفا اگر کسی جواب تشریحی رو داره بزاره، من خودم ندارمش.

[mamat]

البته من اون برگ آرایه ای رو در نظر نگرفته بودم
ولی حالا بازم فکر کنم گزینه ۱ صحیح باشه چون اینجا تو صورت مساله گفته

(۲۲ شهریور ۱۳۹۰ ۰۷:۲۰ ب.ظ)رضا_ایرانی نوشته شده توسط:  در بین همه‌ی درختها با n عنصر، درختی با بیشترین ارتفاع رو در نظر بگیرید. اگر ارتفاع این درخت h باشد...".

(۲۲ شهریور ۱۳۹۰ ۰۷:۲۰ ب.ظ)رضا_ایرانی نوشته شده توسط:  درختی با بیشترین ارتفاع رو در نظر بگیرید. اگر ارتفاع این درخت h باشد

یعنی اگه دوباره بخواییم با n تا عنصر یک درخت دودویی مورب رسم کنیم حالا دیگه اون عناصر موجود در برگ رو تو گره های مجزا بکشیم درختی با بیشترین ارتفاع ممکن را داریم حالا در این صورت باز گزینه یک میتونه صحیح باشه.
حالا اگه کسی دلیل قانع کننده تری برای سایر گزینه‌ها داره بگه.
درضمن حالا که نگاه میکنم به کلید سوالان کنکور گزینه ۱ رو صحیح زده

[hadi_m]

تعداد گره های برگ طبق صورت سئوال برای این درخت خاص برابر با ۲ به توان d هست لذا تعداد گره های داخلی برابر با‌: (۲^d)-1 و تعداد کل گرهای درخت باید برابر باشد با‌:
۲^d + 2^d -1 = 2 ^(d+1) -1
لذا به نظر من یا گزینه یک درست هست یا گزینه سه اما با تو جه به این که گزینه سه کوچکتر از این مقدار گفته و تعداد نودها نمی تواند از این کمتر باشد لذا تنها گزینه یک درست است یعنی:
N<= 2 ^(d+1)
مثلا برای d=2 تعداد گرها ۷ است (۴ گره برگ و ۳ گره داخلی با یک عنصر)و برای d=3 تعداد گرها باید ۱۵ باشد که تنها در گزینه ۱ صادق است یعنی ۱۵<=16
نکته‌: این درخت صرفا درخت دودویی نیست(صورت مسئله هم گفته درخت خاص) و به نظرم باید اسمش رو گذاشت siminary یعنی شبه باینری چون اخرین گره میتواند بیش از دو گره داشته باشد .

[shahrooz]

ببخشید وسط بحث شما می پرم.
به نظر من جواب ۲ درست میباشد .

اولا از توضیحات سوال معلوم میشود که درخت اریب است پس بحث درخت کامل و این حرفا اصلا مطرح نیست.دوما چون b برگ درخت است و در عمق d است پس h=d و چون گفته در برگ b بجای برگ ارایه با طول [tex]2^{d}[/tex] عنصر داریم پس جدای از اینکه ریشه را برابر ۰ با برابر ۱ در نظر بگیریم تعداد ارایه برابر [tex]2^{h}[/tex] میشود.
سوما تعداد گره در درخت اریب در صورتی که ریشه را در سطح صفر فرض کنیم برابر h+1 میشود
ولی چوان بجای b ارایه است پس تعداد گره‌ها بجز ارایه ای که بجای گره b است برابر h میشود.
پس n =< 2^h + h میشود.

[hadi_m]

برهان خلف:
فرض میکنیم گزینه دو درست است
با این حساب برای n=7 با توجه به مشخصات مسئله چهار فرزند برگ داریم و با سه گره داخلی که گره b (صورت مسئله) در عمق ۲ قرار گرفته(۲ به توان ۲ =۴ تعداد فرزندان زیر ارایه یا گرهای برگ )با توجه به گزینه دو باید رابطه زیر برقرار باشه یعنی:
۲^۲+۲
که برابر با ۶ میشود و در رابطه فوق صدق نمیکند یعنی ۷ کوچکتر یا مساوی ۶ نیست لذا فرض ما اشتباست و گزینه دو درست نیست.

---

---

ببینید استدلال شما درسته اما مسئله اینه که اولا شما جواب شما زمانی درسته که عمق ریشه رو ۱ بگیری و در ثانی شما داری حداقل نودها رو بدست میاری .وقتی شما حدااقل نودها رو بدست میاری مقدار n نمیتونه کمتر از حدااقل نودها باشه.
مقدار حداقل نودها با توجه به شرایط مسئله برابر با‌: ۲ به توان h به اضافه h به اضافه ۱ هست .

[hadi_m]

البته شک من بین گزینه های یک و سه هستش

[shahrooz]

فرض میکنیم گزینه دو درست است
با این حساب برای n=7 با توجه به مشخصات مسئله چهار فرزند برگ داریم و با سه گره داخلی که گره b (صورت مسئله) در عمق ۲ قرار گرفته(۲ به توان ۲ =۴ تعداد فرزندان زیر ارایه یا گرهای برگ )با توجه به گزینه دو باید رابطه زیر برقرار باشه یعنی:
۲^۲+۲
که برابر با ۶ میشود و در رابطه فوق صدق نمیکند یعنی ۷ کوچکتر یا مساوی ۶ نیست لذا فرض ما اشتباست و گزینه دو درست نیست.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

اگر b=2 =hبگیرید n=6 میشود و اگر b=3=h در نظر بگیریدn=11 میشود. اگر n=7 باشد b در عمق ۳ میرود یعنی b=3 میشود و باز گرینه ۲ صحیح میباشد.چون گفته بهترین گزینه پس میننم مقداری که در رابطه درست باشد را باید برای سمت راست در نظر بگیریم.

[mamat]

به نظر من که گزینه ۳ رو n کوچکتر مساوی ۲ بتوان h-1 می دونستم ولی الان میبینم گزینه ۳ هم میتونه درست باشه حالا از نظر طراح گزینه لهتر بین این دو کدوم بوده رو نمیدونم.
به این عکس که حل کردم و با موبایل عقب افتادم گرفتم نگاه کنین.
حالا معذرت میخوام کیفیت پایینه دیگه.

[hadi_m]

(۲۳ شهریور ۱۳۹۰ ۰۱:۵۱ ق.ظ)shahrooz نوشته شده توسط:  فرض میکنیم گزینه دو درست است
با این حساب برای n=7 با توجه به مشخصات مسئله چهار فرزند برگ داریم و با سه گره داخلی که گره b (صورت مسئله) در عمق ۲ قرار گرفته(۲ به توان ۲ =۴ تعداد فرزندان زیر ارایه یا گرهای برگ )با توجه به گزینه دو باید رابطه زیر برقرار باشه یعنی:
۲^۲+۲
که برابر با ۶ میشود و در رابطه فوق صدق نمیکند یعنی ۷ کوچکتر یا مساوی ۶ نیست لذا فرض ما اشتباست و گزینه دو درست نیست.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

اگر b=2 =hبگیرید n=6 میشود و اگر b=3=h در نظر بگیریدn=11 میشود. اگر n=7 باشد b در عمق ۳ میرود یعنی b=3 میشود و باز گرینه ۲ صحیح میباشد.چون گفته بهترین گزینه پس میننم مقداری که در رابطه درست باشد را باید برای سمت راست در نظر بگیریم.

اشتباه شما اینجاست که h رو از یک میگیرید
یعنی اینجور حساب میکنید
یک گره در عمق ۱ یا همان گره ریشه
یک گره هم در عمق ۲
تعداد فرزندان گره b در عمق ۲ هم برابر با ۴ هست
و در مجموع میشود ۶ گره
اما شما باید h را از ۰ بگیرید نه از ۱
اما با توجه به صورت مسئله اگر d رو از صفر بگیریم داریم:
یک گره در عمق ۰ ====گره ریشه
یک گره در عمق ۱
یک گره در عمق ۲
حالا تعداد فرزندان گره b یا گره با عمق ۲ هم برابر است با ۴
جمعا ۷ گره میشود
حالا شما چجوری ۶ رو بدست اوردی.
از طرفی دیگه اصلا گزینه دو را درست میگیریم اما مسئله اینه که این گزینه حدااقل گره‌ها رو میده و n نمیتونه از این مقدار حدااقل کمتر باشه یعنی اگر هم میخواد درست باشه باید علامت بزرگتر رو به کار میبرد نه کوچکتر.
امیدوارم تونسته باشم خوب توضیح داده باشم .

---

متاسفانه اشتباه تمام دوستان اینه که عمق ریشه رو یک میگیرید در صورتی که در صورت سئوال گفته عمق ریشه صفرر هستش

[رضا_ایرانی]

(۲۳ شهریور ۱۳۹۰ ۰۲:۱۵ ق.ظ)mamat نوشته شده توسط:  به نظر من که گزینه ۳ رو n کوچکتر مساوی ۲ بتوان h-1 می دونستم ولی الان میبینم گزینه ۳ هم میتونه درست باشه حالا از نظر طراح گزینه لهتر بین این دو کدوم بوده رو نمیدونم.
به این عکس که حل کردم و با موبایل عقب افتادم گرفتم نگاه کنین.
حالا معذرت میخوام کیفیت پایینه دیگه.

سوال تاکید کرده کرده که بهترین جواب رو انتخاب کنید.
بهترین جواب یعنی دقیقترین حد.
گزینه‌ی یک حد دقیقی از تعداد گره هارو نمیده.
در مقایسه گزینه یک و گزینه دو مثالهای شما در این تصویر‌:
مثال اول: گزینه یک: ۴=>3 گزینه دو: ۳=>3
مثال دوم: گزینه یک: ۸=>6 گزینه دو: ۶=>6

و اگر مثال رو با ارتفاع بیشتر ادامه بدیم:

برای ارتفاع ۳:
گزینه یک: ۱۶=>3+8 گزینه دو: ۳+۸=>3+8

برای ارتفاع ۴:
گزینه یک: ۳۲=>3+8 گزینه دو: ۴+۱۶=>4+16

برای ارتفاع ۵:
گزینه یک: ۶۴=>4+16 گزینه دو: ۵+۳۲=>5+32

برای ارتفاع ۶:
گزینه یک: ۱۲۸=>4+16 گزینه دو: ۶+۶۴=>6+64

برای ارتفاع ۱۰:
گزینه یک: ۲۰۴۸=>1024+10 گزینه دو: ۱۰۲۴+۱۰=>1024+10

برای ارتفاع ۱۶:
گزینه یک: ۱۳۱۰۷۲=>65536+16 گزینه دو: ۶۵۵۳۶+۱۶=>65536+16

کاملا معلومه گزینه یک حد دقیقی نمیده و داره به صورت نمایی فاصله میگیره! اما گزینه دو کاملا دقیقه و همیشه تعداد مساوی عناصر رو میده مگر در زمانی که آرایه به حداکثر نرسه. با توجه به صورت سوال هم دقیقترین گزینه خواسته شده.
مثالها به صورت شهودی اینو نشون میده،از نظر اثباتی هم واضحه، گزینه یک "۲ به توان h" رو دو برابر میکنه اما گزینه دو با h جمعش میکنه.

در مورد گزینه سه هم همین طور، با یک عنصر کمتر به صورت نمایی فاصله میگیره.

در ضمن با توجه به اینکه ارتفاع ریشه صفر گرفته شده، نیازی به منهای یک در گزینه‌ها نیست، چون هر درخت داری h+1 گره داخلی خواهد بود، یعنی: ۱-(h+1)+(دو به توان h)

---

(۲۳ شهریور ۱۳۹۰ ۱۲:۰۴ ق.ظ)hadi_m نوشته شده توسط:  برهان خلف:
فرض میکنیم گزینه دو درست است
با این حساب برای n=7 با توجه به مشخصات مسئله چهار فرزند برگ داریم و با سه گره داخلی که گره b (صورت مسئله) در عمق ۲ قرار گرفته(۲ به توان ۲ =۴ تعداد فرزندان زیر ارایه یا گرهای برگ )با توجه به گزینه دو باید رابطه زیر برقرار باشه یعنی:
۲^۲+۲
که برابر با ۶ میشود و در رابطه فوق صدق نمیکند یعنی ۷ کوچکتر یا مساوی ۶ نیست لذا فرض ما اشتباست و گزینه دو درست نیست.

با هفت گره چطور میشه ارتفاع دو داشته باشیم؟ با ارتفاع دو در این درخت خاص حداکثر شش گره داریم. چنین درختی که شما مثال میزنید نمیتونه ساخته بشه، مگر اینکه ارتفاع سه بشه و در آرایه به جای ۸ گره چهار گره قرار بگیره. از هفت گره تا ۱۱ گره ارتفاع میشه سه.