سلام.میشه گزینه ای این سوال رو توضیح بدید چرا درست یا اشتباهن؟؟؟
ممنون
![[تصویر: 319109_46453291401037238903.png]](https://img.manesht.ir/319109_46453291401037238903.png)
سلام
این سوال تو جزوه استاد یوسفی جلسه ۶ صفحات ۲و۳ حل شده.
(۰۷ آذر ۱۳۹۳ ۱۲:۰۹ ب.ظ)miladcr7 نوشته شده توسط:خواهش میکنم(07 آذر ۱۳۹۳ ۱۱:۴۶ ق.ظ)Bahar_sh نوشته شده توسط: سلام
این سوال تو جزوه استاد یوسفی جلسه ۶ صفحات ۲و۳ حل شده.
سلام.بله دیدم مرسی از کمکتون
خب حالا شما میشه لطف کنید حالتهای ۳ و ۴ رو توضیح بدین!
مرسی
خب اینم حل شدش جوابشو میگم کسی خواست استفاده کنه
ارتفاع درخت که همون تعریفیه که میدونیم و پهنا رو هم اینطور تعریف کردیم:بیشترین تعداد گره هایی که در یک سطح قرار میگیرن
حالا بریم سراغ گزینه ها
گزینه اول: ارتفاع درخت [tex][tex]\theta(n)[/tex][/tex] و پهنا هم ۱
فرض کنید [tex][tex]n[/tex][/tex] نود داریم حالا یه درخت مورب رسم کنید میبینید ارتفاعش [tex][tex]\theta(n)[/tex][/tex] و پهناش هم ۱(تو هر سطح فقط یک نود داریم)
گزینه دوم: ارتفاع درخت [tex]\theta(Logn)[/tex] و پهنا هم [tex][tex]\theta(n)[/tex][/tex]
اگه با [tex][tex]n[/tex][/tex] نود یه درخت پر رسم کنید میبینید که ارتفاع [tex]Logn[/tex] هستش و بیشترین پهنا رو هم توی سطح اخر داریم(تعداد نود ها در سطح اخر [tex]\lceil\frac{n}{2}\rceil[/tex] هستش ) که از مرتبه [tex][tex]\theta(n)[/tex][/tex] هستش
گزینه سوم: ارتفاع درخت [tex][tex]\theta(n)[/tex][/tex] و پهنا هم [tex][tex]\theta(n)[/tex][/tex]
فرض میکنیم [tex][tex]n[/tex][/tex] تا نود داریم حالا با [tex]\frac{n}{2}[/tex] این نود ها یه درخت کامل رسم میکنیم
در حالت کلی درخت کامل با [tex][tex]n[/tex][/tex] تا نود تو سطح اخرش حداکثر [tex]\frac{n}{2}[/tex] داره
و در سطح ماقبل اخر حداقل [tex]\frac{n}{4}[/tex] نود دارد.
حالا ما با [tex]\frac{n}{2}[/tex] نود درخت کامل کشیدیم پس در سطح اخر حداکثر [tex]\frac{n}{4}[/tex] نود و در سطح ماقبل اخر حداقل [tex]\frac{n}{8}[/tex] نود داریم که با این وجود مرتبه پهنا [tex][tex]\theta(n)[/tex][/tex] میشه.ارتفاع هم تا الان [tex]Logn[/tex] هستش(چون درخت کامل هست)حالا با [tex]\frac{n}{2}[/tex] نود باقیمونده در سطح اخر یه درخت مورب رسم میکنیم که پهناش یک میشه و ارتفاعشم [tex][tex]\theta(n)[/tex][/tex](تو گزینه یک اینو ثابت کردیم)پس الان پهنا همون [tex][tex]\theta(n)[/tex][/tex] میشه و ارتفاع هم که از دو قسمت تشکیل شده:
[tex]\theta(n) \theta(Logn)=c_1n c_2Logn=\theta(n)[/tex]
گزینه چهارم: [tex]\theta(Logn)[/tex] و پهنا هم [tex]\theta(\sqrt{n})[/tex]
فرض میکنیم که [tex][tex]n[/tex][/tex] تا نود داریم ابتدا با این [tex][tex]n[/tex][/tex] تا نود درختی با پهنای [tex]\theta(\sqrt{n})[/tex] میسازیم پس ما تا الان درختی با پهنای [tex]\theta(\sqrt{n})[/tex](ماکزیمم پهنا) ساختیم و در سطوح بعدی هم در هر سطحی ماکزیمم همین تعداد رو را میتونیم داشته باشیم(چون اگه بیشتر داشته باشیم از مقدار ماکزیمم پهنا عبور کردیم و این اشتباهه)ما برای ساختن درختی با پهنای [tex]\theta(\sqrt{n})[/tex] تقریبا [tex]2\sqrt{n}[/tex] از کل نودها رو مصرف کردیم(مثلا ۱۶ یا ۹ یا ۳۲ تا نود رو در نظر بگیرید و امتحان کنید میبینید همین مقدار میشه تقریبا) پس حالا [tex]n-2\sqrt{n}[/tex] از نودها باقیمونده و در سطوح بعدی هم ما ماکزیمم [tex]\sqrt{n}[/tex] تا نود داریم پس از تقسیم [tex]\frac{n-2\sqrt{n}}{\sqrt{n}}[/tex] تعداد سطوح به دست میاد:
[tex]\frac{n-2\sqrt{n}}{\sqrt{n}}=\frac{(n\ast\sqrt{n})-(2\sqrt{n}\ast\sqrt{n})}{(\sqrt{n}\ast\sqrt{n})}=\frac{(n\sqrt{n})-2n}{n}=\sqrt{n}-2=\theta(\sqrt{n})[/tex]
که ارتفاع هم از مرتبه [tex]\theta(\sqrt{n})[/tex] شد
(توجه داشته باشید تو قسمت چهارم به این دلیل اومدیم توی سطوح بعدی ماکزیمم نود رو گذاشتیم چون میخوایم ارتفاح حداقل شه مثلا اگه مورب بچینیم ارتفاع درخت [tex][tex]n[/tex][/tex] میشه یا اگه کمتر از ماکزیمم بذاریم ارتفاع به سمت [tex][tex]n[/tex][/tex] میره و ما نمیخوایم این اتفاق بیفته و ارتفاع باید مینیمم شه)
پس قسمت اول و دوم و سوم درسته ولی قسمت چهارم دیدیم که نمیشه
پس جواب سوال گزینه ۳ میشه
(۱۳ آذر ۱۳۹۳ ۰۹:۳۵ ب.ظ)monji_421 نوشته شده توسط:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اینجا بچه هاروی گزینه ها بحث کردن نگا کنی مطلب برات جا میفته
اگه الان مدیر بود میگفت قبل از تایپیک زحمت بکشید یه جستجو بزنید
دوست عزیز یه نگاه بندازی میبینی همشون جوابایی که دادن اشتباس!!من خودم قبلا دیدم اینو