۴۷ گزینه ۲ میشه به نظر من طبق کتاب clrs
برای سؤال ۴۷ با گزینه یک به شدت موافقم،
به طور ساده سؤال گفته که ۴تا g داده، گفته از این ۴تا چندتاشون رو اگر در تابع T قرار بدیم میشه تتای g ،یعنی دقیقا" خود g , یعنی باید تک تک گزینه هارو در تابع t قرار بدیم و تتا رو با استفاده از قضیه های اصلی به دست بیاریم که این کار به سادگی انجام میشه و ببینیم که به ازای چندتا از gها تابع t دقیقا" تتای خود اون g رو میده.
که فقط در مورد n^3 صــــــدق میکنه و جواب همون گزینه یک هست.
سایر اثبات‌ها میشه لقمه رو دور سر پیچوندن، مسئله‌ی سختی نیست.
(۲۹ بهمن ۱۳۹۰ ۱۲:۳۳ ق.ظ)amino22 نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۰:۱۵ ب.ظ)reynard696969 نوشته شده توسط:برای سؤال ۴۷ با گزینه یک به شدت موافقم،
به طور ساده سؤال گفته که ۴تا g داده، گفته از این ۴تا چندتاشون رو اگر در تابع T قرار بدیم میشه تتای g ،یعنی دقیقا" خود g , یعنی باید تک تک گزینه هارو در تابع t قرار بدیم و تتا رو با استفاده از قضیه های اصلی به دست بیاریم که این کار به سادگی انجام میشه و ببینیم که به ازای چندتا از gها تابع t دقیقا" تتای خود اون g رو میده.
که فقط در مورد n^3 صــــــدق میکنه و جواب همون گزینه یک هست.
سایر اثبات‌ها میشه لقمه رو دور سر پیچوندن، مسئله‌ی سختی نیست.
با اینکه خودم گزینه ۲ زدم ولی جواب گزینه ۳ یعنی ۳ تا هستش!
اثبات n^3 , n^2.lg^2 n که واضح هستش و برای n^2 هم اثباتش و بالا اورودم. ۹۹% سنجش کلید اعلامیش میشه گزینه ۳ که من و شما هر دو اشتباه زدیم.
واقع گرا باشید
بزرگترین عدد ۵۹ هست
۴۹ میشد گزینه ۳
۱۱۵۲۰
(۲۸ بهمن ۱۳۹۰ ۱۰:۳۸ ب.ظ)afshinmu نوشته شده توسط: سوال ۴۷ - fبرای کدام یک از این gnها حداقل یه دونه fn میتونیم بیاریم که جوابمون همون gn بشه .
طبق قضیه ص۷۹ مقسمی/طراحی الگوریتم
برای gn=n^2 میشه fn=n آورد که ۹t(n/3)+n == مرتبه n^2
برای gn=n^3 میشه fn=n^3 آورد که ۹t(n/3)+n^3 == مرتبه n^3
برای gn=n^2Log^2n میشه fn=n^2Log^2n آورد که ۹t(n/3)+n^2Log^2n == مرتبه n^2Log^2n
پس ۳ تا میشه.
درسته؟
قضیه میگه اگه n^Log a b بزرگتر باشه از fn پس همون و اگر کوچیکتر باشه میشه خود fn
درسته ، برای ۳ تا از g ها میشد یک f داشت که t(n)=g(n)
n^2
,
n^2 log n^2
,
n^3
(۲۹ بهمن ۱۳۹۰ ۰۱:۰۵ ق.ظ)temptemp2 نوشته شده توسط: nدرسته میشه گزینه ۳
سلام
سوال ۴۷-۳تا
اگه f(n)=n^3 باشه t(n)=n^3 میشه و اگه f(n)=n^2 log n باشه t(n)=n^2 log^2 n میشه و اگه f(n)=n باشه t(n)=n^2 میشه.
سوال ۴۸- LeafC(t)=LeafC(Left[T])+LeafC(Right[T])+ISLeaf[t]
اینم فکر کنم خیلی واضحه و همه زدن
میگه اگه به گره داخلی رسیدی تعداد برگهاش میشن تعداد برگهای زیردرخت چپش + زیر درخت راستش؛ اگه به گره برگ رسیدی به جاش ۱ بزار
سوال ۴۹- ۱۱۵۲۰تا
سوال میگه این درخت maxTree هست پس باید بزرگترین گره در ریشه قرار بگیره.
حالا ۳تا نود که فرفی نمیکنه چی باشن باید برن تو زیردرخت راستش (ترکیب ۳از۱۰)
از این ۳تا نود بزرگه میشه ریشه اون دوتای دیگرو به دو حالت میشه چید.
اما زیر درخت چپش: ۷تا نود میمونه که بزرگترین باید بشه ریشه از اون ۶تا یکیشو (به ۶حالت) انتخاب میکنیم میزاریم فرزند چپش میمونه ۵تا نود برای زیر درخت راستش که باز بزرگترین میشه ریشه و یکی از ۴تای باقیمونده رو (به ۴طریق) میزاریم زیر درخت راست، در نهایت ۳تا نود میمونن که بزرگه میشه ریشه و اون ۲تای دیگرو به ۲طریق میشه چید.
۱۱۵۲۰=(ترکیب ۳از۱۰)*۲*۶*۴*۲
سوال ۵۰- T(n)=T(n-1)+2n-1
تو هر مرحله یکی به i اضافه میشه پس میشه t(n-1) ؛ j , count هم هرمرتبه i بار ++ میشن یه بار هم خود i ++ میشه اما i بامقدار اخری که میگیره برابرn میشه و از شرط رد نمیشه میشه ۲n-1بار.
.
سوال ۵۱- O(n)
اگه فرض کنیم که وقتی توی s0 مینویسیم یا از s1 برمیداریم و یه جا مینویسیم هزینش رو با t0 محاسبه کنیم,
برای t0=n s0بار این کار رو انجام میدیم.
برای t1=n/2 s1
برای t2=n/4 s2 و به همین ترتیبn+n/2+n/4+n/8+…=n(1+1/2+1/4+1/8+…)=۲n=O(n
توجه کنید که مثلا برای درج عنصر دوم,چهرم,ششم,هشتم... دوعنصر در s1 مینویسیم اما چون یه عنصرش از s0 میاد و اونو تو t0 محاسبه کردیم؛ دیگه دوباره محاسبه نمیکنیم.
سوال۵۲- ۵۸
سطح ۱-۱نود سطح۲-۲نود سطح۳-۴نود سطح۴-۸نود سطح۵-۱۶نود سطح۶-۳۲نود سطح۷-۱نود
۶۴=۱+۲+۴+۸+۱۶+۳۲+۱
از اونجایی که گفته آخرین سطح میشه سطح ۷ام: سطح۱-۶۴ سطح۲-۶۳ سطح۳-۶۲ سطح۴-۶۱ سطح۵-۶۰ سطح۶-۵۹ سطح۷-۵۸
نقل قول: سوال میگه این درخت maxheap هست پس باید بزرگترین گره در ریشه قرار بگیره.
Max Heap نبود عزیزم Max Tree بود.
من ۲ تا ساختمان جواب دادم یکیش سوال ۴۷ بود که ۲ تا میشد و سوال ۵۲ هم عدد ۵۸ میشد
تو سوال ۵۰ مگه به ازای n=1 تعداد ++ برابر یک و به ازای n=2 برابر ۴ نمیشه؟یعنی جواب گزینه ۳ نباید بشه ؟
(۲۹ بهمن ۱۳۹۰ ۱۰:۱۷ ق.ظ)_Milad_ نوشته شده توسط:نقل قول: سوال میگه این درخت maxheap هست پس باید بزرگترین گره در ریشه قرار بگیره.
Max Heap نبود عزیزم Max Tree بود.
درسته maxtree هست اما حل سوال همونه
(۲۹ بهمن ۱۳۹۰ ۱۱:۴۰ ق.ظ)hesam_k_1988 نوشته شده توسط: تو سوال ۵۰ مگه به ازای n=1 تعداد ++ برابر یک و به ازای n=2 برابر ۴ نمیشه؟یعنی جواب گزینه ۳ نباید بشه ؟جرا یه بار دیگه که چک کردم حرف شما درسته میشه گزینه ۳
(۲۹ بهمن ۱۳۹۰ ۰۹:۵۲ ق.ظ)neo.st نوشته شده توسط: سلامتو سوال ۴۷ اگه f(n) یه عدد ثابت یا حتی n باشه n^2 هم جوابش میشه پس میشه ۳ تا
سوال ۴۷- ۲تا
فکر کنم خیلی واضحه, اگه f(n)=n^3 باشه t(n)=n^3 میشه و اگه f(n)=n^2 log n باشه t(n)=n^2 log^2 n میشه.
سوال ۴۸- LeafC(t)=LeafC(Left[T])+LeafC(Right[T])+ISLeaf[t]
اینم فکر کنم خیلی واضحه و همه زدن
میگه اگه به گره داخلی رسیدی تعداد برگهاش میشن تعداد برگهای زیردرخت چپش + زیر درخت راستش؛ اگه به گره برگ رسیدی به جاش ۱ بزار
سوال ۴۹- ۱۱۵۲۰تا
سوال میگه این درخت maxTree هست پس باید بزرگترین گره در ریشه قرار بگیره.
حالا ۳تا نود که فرفی نمیکنه چی باشن باید برن تو زیردرخت راستش (ترکیب ۳از۱۰)
از این ۳تا نود بزرگه میشه ریشه اون دوتای دیگرو به دو حالت میشه چید.
اما زیر درخت چپش: ۷تا نود میمونه که بزرگترین باید بشه ریشه از اون ۶تا یکیشو (به ۶حالت) انتخاب میکنیم میزاریم فرزند چپش میمونه ۵تا نود برای زیر درخت راستش که باز بزرگترین میشه ریشه و یکی از ۴تای باقیمونده رو (به ۴طریق) میزاریم زیر درخت راست، در نهایت ۳تا نود میمونن که بزرگه میشه ریشه و اون ۲تای دیگرو به ۲طریق میشه چید.
۱۱۵۲۰=(ترکیب ۳از۱۰)*۲*۶*۴*۲
سوال ۵۰- T(n)=T(n-1)+2n-1
تو هر مرحله یکی به i اضافه میشه پس میشه t(n-1) ؛ j , count هم هرمرتبه i بار ++ میشن یه بار هم خود i ++ میشه اما i بامقدار اخری که میگیره برابرn میشه و از شرط رد نمیشه میشه ۲n-1بار.
.
سوال ۵۱- O(n)
اگه فرض کنیم که وقتی توی s0 مینویسیم یا از s1 برمیداریم و یه جا مینویسیم هزینش رو با t0 محاسبه کنیم,
برای t0=n s0بار این کار رو انجام میدیم.
برای t1=n/2 s1
برای t2=n/4 s2 و به همین ترتیبn+n/2+n/4+n/8+…=n(1+1/2+1/4+1/8+…)=۲n=O(n
توجه کنید که مثلا برای درج عنصر دوم,چهرم,ششم,هشتم... دوعنصر در s1 مینویسیم اما چون یه عنصرش از s0 میاد و اونو تو t0 محاسبه کردیم؛ دیگه دوباره محاسبه نمیکنیم.
سوال۵۲- ۵۸
سطح ۱-۱نود سطح۲-۲نود سطح۳-۴نود سطح۴-۸نود سطح۵-۱۶نود سطح۶-۳۲نود سطح۷-۱نود
۶۴=۱+۲+۴+۸+۱۶+۳۲+۱
از اونجایی که گفته آخرین سطح میشه سطح ۷ام: سطح۱-۶۴ سطح۲-۶۳ سطح۳-۶۲ سطح۴-۶۱ سطح۵-۶۰ سطح۶-۵۹ سطح۷-۵۸
برای سوال ۴۷ مگه اینطوری نیست که اگر داشته باشیم
[tex]f(n)=n^{2}log^{2}n[/tex]
انگاه
[tex]T(n)=n^{2}log^{3}n[/tex]
پس فقط یکی از اونها درسته که n^3 است
(۲۹ بهمن ۱۳۹۰ ۰۹:۵۲ ق.ظ)neo.st نوشته شده توسط: سلاممنم نظرم برای سوالات ۴۷ ۴۹ ۵۰ با همیناست هر چند که خودم به اشتباه سر جلسه سوال ۴۷ رو زدم سه تا ولی به نظرم اشتباه بوده و همون دو تاست
سوال ۴۷- ۲تا
فکر کنم خیلی واضحه, اگه f(n)=n^3 باشه t(n)=n^3 میشه و اگه f(n)=n^2 log n باشه t(n)=n^2 log^2 n میشه.
سوال ۴۸- LeafC(t)=LeafC(Left[T])+LeafC(Right[T])+ISLeaf[t]
اینم فکر کنم خیلی واضحه و همه زدن
میگه اگه به گره داخلی رسیدی تعداد برگهاش میشن تعداد برگهای زیردرخت چپش + زیر درخت راستش؛ اگه به گره برگ رسیدی به جاش ۱ بزار
سوال ۴۹- ۱۱۵۲۰تا
سوال میگه این درخت maxTree هست پس باید بزرگترین گره در ریشه قرار بگیره.
حالا ۳تا نود که فرفی نمیکنه چی باشن باید برن تو زیردرخت راستش (ترکیب ۳از۱۰)
از این ۳تا نود بزرگه میشه ریشه اون دوتای دیگرو به دو حالت میشه چید.
اما زیر درخت چپش: ۷تا نود میمونه که بزرگترین باید بشه ریشه از اون ۶تا یکیشو (به ۶حالت) انتخاب میکنیم میزاریم فرزند چپش میمونه ۵تا نود برای زیر درخت راستش که باز بزرگترین میشه ریشه و یکی از ۴تای باقیمونده رو (به ۴طریق) میزاریم زیر درخت راست، در نهایت ۳تا نود میمونن که بزرگه میشه ریشه و اون ۲تای دیگرو به ۲طریق میشه چید.
۱۱۵۲۰=(ترکیب ۳از۱۰)*۲*۶*۴*۲
سوال ۵۰- T(n)=T(n-1)+2n-1
تو هر مرحله یکی به i اضافه میشه پس میشه t(n-1) ؛ j , count هم هرمرتبه i بار ++ میشن یه بار هم خود i ++ میشه اما i بامقدار اخری که میگیره برابرn میشه و از شرط رد نمیشه میشه ۲n-1بار.
.
سوال ۵۱- O(n)
اگه فرض کنیم که وقتی توی s0 مینویسیم یا از s1 برمیداریم و یه جا مینویسیم هزینش رو با t0 محاسبه کنیم,
برای t0=n s0بار این کار رو انجام میدیم.
برای t1=n/2 s1
برای t2=n/4 s2 و به همین ترتیبn+n/2+n/4+n/8+…=n(1+1/2+1/4+1/8+…)=۲n=O(n
توجه کنید که مثلا برای درج عنصر دوم,چهرم,ششم,هشتم... دوعنصر در s1 مینویسیم اما چون یه عنصرش از s0 میاد و اونو تو t0 محاسبه کردیم؛ دیگه دوباره محاسبه نمیکنیم.
سوال۵۲- ۵۸
سطح ۱-۱نود سطح۲-۲نود سطح۳-۴نود سطح۴-۸نود سطح۵-۱۶نود سطح۶-۳۲نود سطح۷-۱نود
۶۴=۱+۲+۴+۸+۱۶+۳۲+۱
از اونجایی که گفته آخرین سطح میشه سطح ۷ام: سطح۱-۶۴ سطح۲-۶۳ سطح۳-۶۲ سطح۴-۶۱ سطح۵-۶۰ سطح۶-۵۹ سطح۷-۵۸