به نظر منم ابهام داشت
بچه ها من سر جلسه خیلی رو این سئوال فکر کردم.الانم که دارم جوابای شمارو میبینم بازم قانع نمیشم.به نظر منم فقط یکیش درسته
(۲۸ بهمن ۱۳۹۰ ۰۳:۴۳ ب.ظ)silver نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۳:۲۳ ب.ظ)f.b نوشته شده توسط: در پایین ترین n-log n که n=64 بود که ۵۸ میشد
فکر کنم تنها سوال بود که جواب دادم
نهههه......جواب میشد ۵۹
در مورد این سوال ۶۴ رو باید بذاریم به عنوان ریشه،فرض کنیم ۶۳ فرزند چپش باشه،۶۲ هم فرزند چپ ۶۳ و همینطور تا ۵۹/
تا اینجا جای ۶ گره مشخص شد.الان باید در زیردرخت سمت راست ۶۴، ۵۸ گره جا بدیم و عمق درخت هم نباید از ۵ بیشتر بشه چون اگه بشه ۶،با احتساب ریشه ۵۹ دیگه در آخرین سطح درخت نیست. ماکسیمم تعداد گره ای هم که میشه تو یک درخت دودویی به عمق ۵ جا داد ۳۱ گره بیشتر نیست.پس ۵۹ نمیتونه جواب صحیح باشه
(۲۸ بهمن ۱۳۹۰ ۰۷:۳۱ ب.ظ)temptemp2 نوشته شده توسط: به نظرم LeafC = Leafc + Leafc + ISLEAF نمیشد، مثلا یک درخت با ۳ تا ند رو بگیریم، یعنی یک ند و دو تا برگ، طبق این ۲ برمیگردونه، ولی جواب اصلیش میشه: LeafC = Leafc + Leafc + 1، یعنی تعدا برگهای سمت چپ+ تعداد پرک های سمت راست + خودش (۱)
دوست عزیز توجه داشته باشید که تابع LEAFC(T) قراره تعداد برگهارو برگردونه نه تعداد گره ها رو
[
(۲۹ بهمن ۱۳۹۰ ۰۳:۳۳ ب.ظ)yaali نوشته شده توسط:(29 بهمن ۱۳۹۰ ۰۹:۵۲ ق.ظ)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 میشه.
دقیقا اینطوری حل میشه.
و به نظرم سوال خوبیه.
نه ایهام نداش جوابش میشه یکی فقط
به دلایل زیر (همشو قضیه اصلی و مکملش گفته):
[tex]T(n)= 9T(n/2) g(n)[/tex]
گزینه درست:
[tex]if( g(n)= n^{3} )[/tex]
طبق قضیه اصلی جواب درسته.(بدیهی بود)
گزینه های غلط:
(۱)
[tex]if( g(n)= n ^{2} )[/tex]
[tex]if(g(n)= n ^{2}) \rightarrow T(n)=\theta (n^{2} log(n))[/tex]
(۲)
[tex]if( g(n)= n ^{2} log(n)) \rightarrow T(n)=n^{2}log^{2}(n)[/tex]
(۳)
بازم طبق قضیه اصلی چون:
[tex]if(g(n)= n ^{2}) \rightarrow T(n)=\theta (n^{2} log(n))[/tex]
که مخالف [tex]g(n)[/tex]
(۲)
[tex]if( g(n)= n ^{2} log(n)) \rightarrow T(n)=n^{2}log^{2}(n)[/tex]
مکمل قضیه اصلی:
[tex]T(n)= aT(n/b) g(n)[/tex]
[tex]if(g(n)= n^{loga_{b}}log^{k}) \rightarrow T(n)= n^{loga_{b}}log^{k 1}[/tex]
[tex]if(g(n)= n^{loga_{b}}log^{k}) \rightarrow T(n)= n^{loga_{b}}log^{k 1}[/tex]
(۳)
[tex]if (g(n)=nlog(n)) \rightarrow T(n)=\theta (n^{2})[/tex]
من سئوال ۴۷ رو گزینه ۲ زدم ولی الان که فکر میکنم به نظر خودم اشتباه رفتم. چون صورت سئوال گفته به ازای چه مقداری از تابع( f(n برابر[tex]\Theta (g(n))[/tex] است. با قضیه اصلی میشه [tex] f(n)= n^{log_{b}^{a}}[/tex]
به نظر شما نمیشه گزینه ۱ ؟
سوال اصلا این رو نگفته که بیا یکی یکی g ها رو بگذار به جای f و تست کن که آیا جواب با g برابر می شه یانه.
یعنی
سوال نگفته بیا عینا و فقط از همین g ها که داریم برای f استفاده کن. بلکه:
سوال گفته آیا می تونید حداقل یک f (از خودتون) مثال بزنید بطوریکه جواب بشه g .
که برای سه تا از g ها می شه این کار رو کرد.
به عبارت دیگه:
سوال گفته برای چند تا از توابع زیر (همون g ها )می شه حداقل یک f مثال زد بطوریکه پاسخ بشه g .
خلاصه اش اینه که آیا می شه هیچ f ی رو مثال زد بطوریکه جواب بشه g .
خوب اگه ما بتونیم حتی یک مثال هم بیاریم ، کافیه.
اگه f=n بگیریم جواب می شه تتای n^2 .
اگه f= n^3 بگیریم جواب می شه تتای n^3
اگه f=n^2logn بگیریم جواب می شه تتای n^2logn^2
اما هیچ f ی رو نمی شه مثال زد بطوریکه جواب بشه nlogn
در نتیجه ۳ تا درسته.
و می بینید که سوال هیچ ابهامی هم نداره .
موفق باشید.
(۲۹ بهمن ۱۳۹۰ ۰۵:۰۶ ب.ظ)yaali نوشته شده توسط: دوست عزیز مشکل حل شما اینه که دارین یکی یکی g ها رو میگذارید به جای f و تست می کنید که آیا جواب با g برابر می شه یانه.واقعا اینطوریه؟ اگر اینجوری باشه که می شه ۳ تا اما
یعنی شما دارید عینا g رو میگذارید جای f و ...
در حالیکه سوال اصلا این رو نخواسته.
سوال نگفته بیا عینا از همین g ها که داریم برای f استفاده کن. بلکه:
سوال گفته آیا می تونید حداقل یک f (از خودتون) مثال بزنید بطوریکه جواب بشه g .
که برای سه تا از g ها می شه این کار رو کرد.
ارسال قبلی من (ارسال ۱۸) رو ببینید.
(۲۹ بهمن ۱۳۹۰ ۰۳:۳۷ ب.ظ)variant20002000 نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۹:۱۴ ب.ظ)afshinmu نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۳:۴۳ ب.ظ)silver نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۳:۲۳ ب.ظ)f.b نوشته شده توسط: در پایین ترین n-log n که n=64 بود که ۵۸ میشد
فکر کنم تنها سوال بود که جواب دادم
نهههه......جواب میشد ۵۹
سطح اول ۱ نود = ۶۴
سطح دوم ۲ نود = ۶۳
سطح سوم ۴ نود = ۶۲
سطح چهارم ۸ نود = ۶۱
سطح پنجم ۱۶ نود = ۶۰
سطح ششم ۳۲ نود = ۵۹
سطح آخر ۱ نود = ۵۸
پس ۵۸ میشه
دوست عزیز یه سطح زیادی رفتی جلو....!
درختم عمقش ۶ هست پس سطح آخر همون ۵۹میشه
ببین دوست من ۱+۲+۴+۸+۱۶+۳۲=۶۳ ولی چون صورت سوال گفته ۶۴ تا نود داریم پس باید سطح یکی بیشتر بشه( یادتون که هست heap درخت کامله نه درخت پر )پس تعداد سطوح میشه ۷ نه ۶ پس مطمئنا جاب ۵۸ هستش . ۶۴ - ۶۳ - ۶۲ - ۶۱ - ۶۰ - ۵۹ - ۵۸
مشخصه نمیدونم چرا انقد روش بحث میشه
(۲۹ بهمن ۱۳۹۰ ۰۳:۲۸ ب.ظ)afshinmu نوشته شده توسط: متاسفانه صورت سوال رو اصلا دقت نکردید دوستان .
در رابطه t(n)=9t(n/3)+fn به ازای چند تا از پائینی ها دست کم یک تابع برای fn وجود دارد که مرتبه tn بشه همون پائینیه . شما اینطور فهمیدید که به ازای کدوم پائینیه اگه بذاریمش جای fn مرتبه میشه همون پائینیه . نگفته گزینه ها رو بذاریم جای fn . گفته از خودمون fn پیدا کنیم و بذاریم تو رابطه . خلاصه حداقل یه fnی پیدا کنیم . امیدوارم تونسته باشم منظورم رو برسونم . همونطور که توضیح دادم برای ۳ تاشون میشه همچین fnی پیدا کرد . پس جواب ۳تا میشه
کاملا درسته ۳ تا میشه
من استدلالهای دوستان خوبم رو با دقت خوندم به نظرم این استدلال پایین از دوستمون از همه محکم تر بود
ایشون منظور سوال رو هم قشنگ تعبیر کردند که اون ایهام توی ذهن من رفع شد
به نظرم جوابشون قانع کنندست اگه با دقت بخونید
(۲۹ بهمن ۱۳۹۰ ۰۴:۰۲ ب.ظ)yaali نوشته شده توسط: سوال گفته برای چند تا از توابع زیر (همون g ها )می شه حداقل یک f مثال زد بطوریکه پاسخ بشه g .
خلاصه اش اینه که آیا می شه هیچ f ی رو مثال زد بطوریکه جواب بشه g .
خوب اگه ما بتونیم حتی یک مثال هم بیاریم ، کافیه.
اگه f=n بگیریم جواب می شه تتای n^2 .
اگه f= n^3 بگیریم جواب می شه تتای n^3
اگه f=n^2logn بگیریم جواب می شه تتای n^2logn^2
اما هیچ f ی رو نمی شه مثال زد بطوریکه جواب بشه nlogn
حالا طراح میمرد دو بار اسم تابع جی رو نیاره از اول همینو بگه
"خلاصه اش اینه که آیا می شه هیچ f ی رو مثال زد بطوریکه جواب بشه g ."
در مورد سوال ۵۲ که واقعا اسون تر از این نمیشد سوال داد همون گزینه ۳ یعنی ۵۸ درسته.
دوستان کسی سوال ۴۹ رو جواب نداده؟؟؟چند میشه؟هرکی جواب داده با راه حل بگه لطفا
(۲۹ بهمن ۱۳۹۰ ۰۸:۳۹ ب.ظ)fmka2f نوشته شده توسط: در مورد سوال ۵۲ که واقعا اسون تر از این نمیشد سوال داد همون گزینه ۳ یعنی ۵۸ درسته.۱۱ رو میذاری ریشه (مجبور هستیم)
دوستان کسی سوال ۴۹ رو جواب نداده؟؟؟چند میشه؟هرکی جواب داده با راه حل بگه لطفا
زیر درخت سمت راست:
سه عنصر برای سمت راست از ده تا انتخاب میکنید * دو حالتی که این عناصر میتونند قرار بگیرند (عنصر بزرگتر ریشه و دو حالت برای عناصر زیری
زیر درخت سمت چپ:
به همون روال قبلی
ادامه میدی و کل حالات رو در هم ضرب میکنی پاسخ ۱۱۵۲۰
[/quote]
۱۱ رو میذاری ریشه (مجبور هستیم)
زیر درخت سمت راست:
سه عنصر برای سمت راست از ده تا انتخاب میکنید * دو حالتی که این عناصر میتونند قرار بگیرند (عنصر بزرگتر ریشه و دو حالت برای عناصر زیری
زیر درخت سمت چپ:
به همون روال قبلی
ادامه میدی و کل حالات رو در هم ضرب میکنی پاسخ ۱۱۵۲۰
[/quote]
خوب این روش با اینکه درسته ولی کل جلسه زمان میبره...راه حلش همینه فقط؟؟؟روش خاصی نداشت احیانا؟
(۲۹ بهمن ۱۳۹۰ ۰۳:۳۶ ب.ظ)Masoud05 نوشته شده توسط: این سوال رو خیلی بد مطرح کرده طراح ، انگار میخواسته تابع بازگشتی براش بنویسهواقعا" این طراحی که خودش سؤال رو نمیتونه درست بیان کنه از کجا آوردن! فکر کنم استاد ادبیات بوده خواسته ایهام بکار ببره ببینه ما میفمیم یا نه!!!
واقعا" متاسفم برای سازمان سنجش، سال به سال کج سلیقگی و نا همگونی و غلط و اشتباه جای کم شدن داره بیشتر میشه!
البته کلا" تو این سیستم توقعی هم نمیشه داشت، اگه همه چی خوب و منظم و عالی باشه باید تعجب کرد!
واقعا از دوستانی که در تفهیم سوال ۴۷ به بقیه کمک کردن ممنونم.
دو روزه دارم به یکی توضیح میدم که برادر من صورت سوال این نیست که تو میگی اما تو کتش نمیرفت.
تا اینکه از توضیحات دوستان استفاده کردم و قانعش کردم که جواب ۳ میشه !
(۲۹ بهمن ۱۳۹۰ ۰۹:۳۳ ب.ظ)fardin_ss نوشته شده توسط: واقعا از دوستانی که در تفهیم سوال ۴۷ به بقیه کمک کردن ممنونم.
دو روزه دارم به یکی توضیح میدم که برادر من صورت سوال این نیست که تو میگی اما تو کتش نمیرفت.
تا اینکه از توضیحات دوستان استفاده کردم و قانعش کردم که جواب ۳ میشه !
ولی شک نکن که یک میشه کلید بیاد میفهمی
