من با mbayati موافقم!۳ تا میشه
دقیقا" همون یک میشه ...
طبق قضیه ۳/ .
اگه حتی از قضیه ۴ هم استفاده کنیم (که لزومی نداره!)برای n^2log2n ابتدا n^2 بدست میاد که وقتی با n^2log2n مقایسه میکنیم بازم "تتای" خودش نیست و نمیشه.
(۲۹ بهمن ۱۳۹۰ ۰۶:۱۷ ق.ظ)javadyousefi نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۰:۳۸ ب.ظ)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
T(n)=9t(n/2)+g(n)
if (g(n)= n^2) -------> T(n)=n^2 logn
if(g(n)= n^2 logn) -------> T(n)= n^2 Logn^2
if(g(n)=nlog n) ------->T(n)=n^2
if(g(n)= n^3) -------> T(n)= n^3 **********
if (g(n)= n^2) -------> T(n)=n^2 logn
if(g(n)= n^2 logn) -------> T(n)= n^2 Logn^2
if(g(n)=nlog n) ------->T(n)=n^2
if(g(n)= n^3) -------> T(n)= n^3 **********
میشه فقط یکی آخری
(۲۹ بهمن ۱۳۹۰ ۰۱:۲۸ ب.ظ)saeed_435 نوشته شده توسط: میشه فقط یکی آخریکاملا" درسته، فقط اگه n^3 قرار بدیم میشه تتای خودش
(۲۹ بهمن ۱۳۹۰ ۰۶:۳۸ ق.ظ)javadyousefi نوشته شده توسط:(29 بهمن ۱۳۹۰ ۰۱:۰۵ ق.ظ)temptemp2 نوشته شده توسط: nدرسته میشه گزینه ۳
کلید سنجش
۴۷ )گزینه یک
۴۸ )گزینه ۴
۵۰ )گزینه یک
۵۲ )گزینه سه
[/quote]
تو سوال ۴۷ اگه f(n) یه عدد ثابت یا حتی n باشه n^2 هم جوابش میشه پس میشه ۳ تا
[/quote]
بله درست میفرمایید تصحیح میشه
(۲۸ بهمن ۱۳۹۰ ۱۱:۳۶ ب.ظ)LARACROFT0 نوشته شده توسط: ۴۷ ۱
۴۸ ۴
۴۹ ۳
۵۰ ۳
۵۱ ۴
۵۲ ۳
میشه لطفا توضیح بدین سوال ۴۹ رو چطور گزینه ۳ بدست اوردین؟
در سؤال۴۷
متاسفانه بعضی از دوستان فهم درستی از داده ها و خواسته ی مسئله ندارن!
عدد ثابت یا n اصلا" نمیشه و نبــــاید استفاده کرد دوست عزیز، خودش ۴تا گزینه داده برای آزمایش کردن!
از بین اون ۴تا فـــقط به ازای n^3 تتای g میده و بـــــــس.
والســــــلام.
(۲۸ بهمن ۱۳۹۰ ۰۸:۱۹ ب.ظ)باد نوشته شده توسط:۴۷- ۳(28 بهمن ۱۳۹۰ ۰۷:۴۶ ب.ظ)deledivouneh نوشته شده توسط: با تشکر از پشتکار عزیز بابت صفحه سوالات
۴۷-گزینه ۲ دو تا تابع
۴۸-گزینه ۴ راحت
۴۹-bst نبود نزدم.بحث شمارشی بود.
۵۰-؟
۵۱- گزینه ۴ مثل مرتب سازی درجی
۵۲-گزینه ۳ با کشیدن درخت کامل
دوستا نظر بدید.
۴۷ - گزینه ۲
۴۸ -گزینه ۴
۴۹- نزدم. با تابع مولد پیش رفتم ولی وقت کم اوردم
۵۰- هیچ کدام از گزینهها درست نبود( تجربه ۳ سال برنامه نویسی!)
۵۱- نزدم
۵۲- گزینه ۳( سوال برای اولین بار در کنکور ساختمان داده تکراری بود. من نخونده زدم!)
۴۸- ۴
۴۹- نزدم
۵۰- هیچکدام ولی گزینه ۲ نزدیکترین به جواب بود (برای n=2 , n=3 آزمایش کنید) اگه مساوی میداشت این سوال یعنی شروط دو حلقه کوچکتر مساوی بودند گزینه ۳ صحیح بود
۵۱- نزدم
۵۲- ۴
واقعاً برای طراحان سوال متاسفم سوال ۵۰ دیگه ششورشو در آورده بودن
(۲۹ بهمن ۱۳۹۰ ۰۱:۳۱ ب.ظ)amino22 نوشته شده توسط:(29 بهمن ۱۳۹۰ ۰۱:۲۸ ب.ظ)saeed_435 نوشته شده توسط:کاملا" درسته، فقط اگه n^3 قرار بدیم میشه تتای خودش(29 بهمن ۱۳۹۰ ۰۶:۱۷ ق.ظ)javadyousefi نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۰:۳۸ ب.ظ)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
T(n)=9t(n/2)+g(n)
if (g(n)= n^2) -------> T(n)=n^2 logn
if(g(n)= n^2 logn) -------> T(n)= n^2 Logn^2
if(g(n)=nlog n) ------->T(n)=n^2
if(g(n)= n^3) -------> T(n)= n^3 **********
میشه فقط یکی آخری
متاسفانه صورت سوال رو اصلا دقت نکردید دوستان .
در رابطه t(n)=9t(n/3)+fn به ازای چند تا از پائینی ها دست کم یک تابع برای fn وجود دارد که مرتبه tn بشه همون پائینیه . شما اینطور فهمیدید که به ازای کدوم پائینیه اگه بذاریمش جای fn مرتبه میشه همون پائینیه . نگفته گزینه ها رو بذاریم جای fn . گفته از خودمون fn پیدا کنیم و بذاریم تو رابطه . خلاصه حداقل یه fnی پیدا کنیم . امیدوارم تونسته باشم منظورم رو برسونم . همونطور که توضیح دادم برای ۳ تاشون میشه همچین fnی پیدا کرد . پس جواب ۳تا میشه
من متن این سوال رو (سوال ۴۷) رو چند بار در کنکور خوندم به نظرم ایهام داره موافق نیستید؟
به نظرم میشد منظورش رو ساده تر با همون f بیان کنه بدون این که پای تابع g رو وسط بکشه!
به نظر کس دیگه ای هم اینجوری هست؟
(۲۹ بهمن ۱۳۹۰ ۰۹:۵۲ ق.ظ)neo.st نوشته شده توسط: سوال ۴۷-۳تا
اگه 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 میشه.
دقیقا اینطوری حل میشه.
(۲۹ بهمن ۱۳۹۰ ۰۳:۲۹ ب.ظ)موج نوشته شده توسط: من متن این سوال رو (سوال ۴۷) رو چند بار در کنکور خوندم به نظرم ایهام داره موافق نیستید؟
به نظرم میشد منظورش رو ساده تر با همون f بیان کنه بدون این که پای تابع g رو وسط بکشه!
این سوال رو خیلی بد مطرح کرده طراح ، انگار میخواسته تابع بازگشتی براش بنویسه
(۲۸ بهمن ۱۳۹۰ ۰۹:۱۴ ب.ظ)afshinmu نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۳:۴۳ ب.ظ)silver نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۳:۲۳ ب.ظ)f.b نوشته شده توسط: در پایین ترین n-log n که n=64 بود که ۵۸ میشد
فکر کنم تنها سوال بود که جواب دادم
نهههه......جواب میشد ۵۹
سطح اول ۱ نود = ۶۴
سطح دوم ۲ نود = ۶۳
سطح سوم ۴ نود = ۶۲
سطح چهارم ۸ نود = ۶۱
سطح پنجم ۱۶ نود = ۶۰
سطح ششم ۳۲ نود = ۵۹
سطح آخر ۱ نود = ۵۸
پس ۵۸ میشه
دوست عزیز یه سطح زیادی رفتی جلو....!
درختم عمقش ۶ هست پس سطح آخر همون ۵۹میشه
(۲۹ بهمن ۱۳۹۰ ۰۳:۰۷ ب.ظ)amino22 نوشته شده توسط:(29 بهمن ۱۳۹۰ ۰۲:۱۰ ب.ظ)neo.st نوشته شده توسط:
در سؤال۴۷
متاسفانه بعضی از دوستان فهم درستی از داده ها و خواسته ی مسئله ندارن!
عدد ثابت یا n اصلا" نمیشه و نبــــاید استفاده کرد دوست عزیز، خودش ۴تا گزینه داده برای آزمایش کردن!
از بین اون ۴تا فـــقط به ازای n^3 تتای g میده و بـــــــس.
والســــــلام.
منم سر جلسه با اون فشاری که وجود داشت مثل شما فکر کردم
اما وقتی دوباره خوندم دیدم دوستان درست میگن.
سوال دقیقا اینو میگه که آیا جمله ای وجود داره که بزارین به جای F(n) و حاصل معادله بشه یکی از g(n)ها.
سوالش نه مشکل شرعی داره نه اخلاقی کاملا درسته.
منو امثال من هم که اشتباه متوجه شدن و اشتباه زدن باید بیشتر دقت میکردن, هرچی نباشه کنکوره ارشده دیگه!