(۲۸ بهمن ۱۳۹۰ ۰۹:۳۶ ب.ظ)M.karimian نوشته شده توسط: در سوال ۵۲ n-logn+1 که ۵۹ میشه
بالارو ببین رسم کردم شکلو . همچین سوالایی که میشه خیلی راحت شکلشو کشید چه نیازی به log هست که حساب کنید؟را مطمئن‌تر شاید فقط ۱ دقیقه بیشتر طول بکشه . ۵۸
(۲۸ بهمن ۱۳۹۰ ۰۹:۵۵ ب.ظ)afshinmu نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۹:۳۶ ب.ظ)M.karimian نوشته شده توسط: در سوال ۵۲ n-logn+1 که ۵۹ میشه
بالارو ببین رسم کردم شکلو . همچین سوالایی که میشه خیلی راحت شکلشو کشید چه نیازی به log هست که حساب کنید؟را مطمئن‌تر شاید فقط ۱ دقیقه بیشتر طول بکشه . ۵۸
دوستان این سوالی که ۵۸ میشد،تکراری سالای پیش بود .کاش میشد ساختمان و الگوریتم نرم منو با به جای آی تی بذارن درصداشو
(۲۸ بهمن ۱۳۹۰ ۰۹:۳۶ ب.ظ)M.karimian نوشته شده توسط: در سوال ۵۲ n-logn+1 که ۵۹ میشه
این سوال تکراری بودش.
سوال مال سال ۱۳۸۳ هستش که توی پارسه هم در قسمت ماکزیمم اول و دوم و ... دقیقا نوشته شده و حل شده و دقیقا گفته شده که عدد مذکور ۵۸ هستش.
(۲۸ بهمن ۱۳۹۰ ۰۹:۳۰ ب.ظ)afshinmu نوشته شده توسط: ۴۷ مطمئنید گزینه ۲ ؟؟؟ اخه گه fn=n^2log^2 باشه چی؟؟؟ اگه fn=nباشه چی؟ اگه fn=n^3 باشه چی؟ به نظر شما ۳ تا تابع نمیشه؟من همچین فکر می کنم البته بدون اطمینان . میشه جواب رو در این ۳ حالت بگید؟
-=-=-=-=-=-=-==-=-=-=-=-=--==--=-=-==--=
بنظر من می شه گزینه یک.سوال گفته باید بشه تتا خوده همون تابع.اولی از سمت چپو بزاریم جواب کلی می شه n^2.بعدیش می شه n^2logn بعدیشم می شه n^2logn^3 بعدی میشه n^3.با این شرایط فقط یه تابعست که خودش میشه جواب مسئله.درسته یا من چایو دارم استباه می کنم؟این استدلال من سر جلسه بود
سوال ۴۹ چی میشد ؟ کسی حل کرده ؟
با تشکر از دوستان
۹T(n/3)+nlgn---->nlg^2 n غلط
۹T(n/3)+n^2---->n^2 lg n غلط
۹T(n/3)+n^2lg^2n---->n^2lg^3n غلط
۹T(n/3)+n^3---->n^3 درست
سوال اینو میگه که جایی که تابع f رو تو رابطه میذاریم جوابش هم مساوی g باشه
f=g
(۲۸ بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)deledivouneh نوشته شده توسط: ۹T(n/3)+nlgn---->nlg^2 n غلط
۹T(n/3)+n^2---->n^2 درست
۹T(n/3)+n^2lg^2n---->n^2lg^3n غلط
۹T(n/3)+n^3---->n^3 درست
سوال اینو میگه که جایی که تابع f رو تو رابطه میذاریم جوابش هم مساوی g باشه
f=g
=-==--=-=-=-==-=-=-=--=-=-=-=-==-
دومی غلطه.قیضه مستر.میشه n^2logn
۴۷ ۱
۴۸ ۴
۵۰ ۳
۵۲ ۳
(۲۸ بهمن ۱۳۹۰ ۰۳:۱۸ ب.ظ)shervinrs نوشته شده توسط: در این تاپیک سوالات ساختمان داده ۹۱ بررسی خواهد شد.
سوالات پیوست شدن.
گزینه های صحیحدر حال حاضر)
۴۷- ۲
۴۸- ۴
۴۹-
۵۰- ۳
۵۱-
۵۲- ۳
منم اینطوری زدم به غیر از اینکه سوال ۴۷ نزدم و سوال ۵۱ زدم که یادم نیست چی زدم
سوال ۴۷ - 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
(۲۸ بهمن ۱۳۹۰ ۱۰:۲۰ ب.ظ)saba1000 نوشته شده توسط: سوال ۴۹ چی میشد ؟ کسی حل کرده ؟
گزینه ۳ یعنی ۱۱۵۲۰
۱۱ رو، روی ریشه می ذاریم( عدد ماکزیمم )، بعد از اون انتخاب سه از ده تابرای زیردرخت سه تایی داریم و بقیه برای هفت تایی می شن
زیر درخت سه تایی، ماکزیمم اون سه عدد باید ریشه‌ی زیردرخت باشه، و دوتای دیگه به دوحالت می تونن بیان
برای هفت تایی هم ماکزیمم توی ریشه قرار می گیره و ۶ حالت برای تکی داریم، که ۵ تا می مونه ... همین طور ادامه می دیم
می شه انتخاب ۳ از ۱۰ * ۲ * ۶ * ۴ * ۲ = ۱۱۵۰
ولی من سوال ۴٧ زدم ٣. فقط به ازای n log n تابعی نداشتیم!
۴۷ ۱
۴۸ ۴
۴۹ ۳
۵۰ ۳
۵۱ ۴
۵۲ ۳
(۲۸ بهمن ۱۳۹۰ ۱۰:۳۵ ب.ظ)reynard696969 نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۰:۲۵ ب.ظ)deledivouneh نوشته شده توسط: ۹T(n/3)+nlgn---->nlg^2 n غلط
۹T(n/3)+n^2---->n^2 درست
۹T(n/3)+n^2lg^2n---->n^2lg^3n غلط
۹T(n/3)+n^3---->n^3 درست
سوال اینو میگه که جایی که تابع f رو تو رابطه میذاریم جوابش هم مساوی g باشه
f=g
=-==--=-=-=-==-=-=-=--=-=-=-=-==-
دومی غلطه.قیضه مستر.میشه n^2logn
توی این سوال فرض کنید f(n) = n( چون گفته حداقل یک f پیدا بشه)
حالا با این فرض [tex]T(n) = \Theta (n^{2})[/tex]
حالا اگه [tex]g(n) = n^{2}[/tex] باشه اون وقت [tex]T(n) = \Theta (g(n))[/tex]
پس برای [tex]g(n) = n^{3}[/tex] , [tex]g(n) = n^{2}[/tex] درست هستش و مطمئنا گزینه ۱ غلط هستش
دفترچه منم ۵۱۰ A بود
۴۸ - ۴
۵۰ - ۳