به نظر من طراح همون درخت گلوگاه رو گفته که کاملا مشخصه ،درخت پوشای گلوگاه بزرگترین یالش نسبت به سایر درختان پوشا کمترین باشه ، یعنی همین سوال اما طراح خواسته با کلمات بازی کنه تا طرف فقط حفظ نکرده باشه یا میخواسته بپیچونه !!
هر درخت فراگیر کمینه هم یک گلوگاه هست حتما ، پس هر دو گلوگاه رو می دن(مسائل آخر فصل MST)
(۲۸ بهمن ۱۳۹۰ ۱۰:۴۹ ب.ظ)باد نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۰:۴۷ ب.ظ)mp1368 نوشته شده توسط: بچهها اون سوالی رو که گفته بود برای پیدا کردن میانه یک سری اعداد اونها رو به دسته های پنج تایی تقسیم کرده سپس میانه هر لیست رو محاسبه و سرانجام میانه میانهها رو به صورت بازگشتی محاسبه می کنیم.
اول در مورد روش حل به یه توافق برسیم بعد بریم سر زمان حلش؟
من خودم که اینجوری حسابش کردم برنامش رو هم تقریبا نوشتم .اگه ما یه لیست ۱۵ تایی در نظر بگیریم و اونو تو هر مرحله به یه سری دسته ۵ تایی تقسیم کنیم تو مرحله اول میانه این دستهها به ترتیب ۳ -۸ -۱۳ میشه که این رو می تونیم به راحتی تو یه زمان ثابت به دست بیاریم.
بعد فراخوانی رو با اعداد بین این سه تا دستگیره فرواخوانی می کنیم و به همین ترتیب مثلا تو مرحله بعد ما فقط یه لیست ۵ تایی رو داریم که باید میانه اونها رو حساب کنیم.
اگر کسی سوال رو حل کرده لطف کنه روش حلش رو تو وحله اول بگه.
این توی جزوه دکتر سید جوادی فرمولش رو گفته بود:
می شه t(n/3) +T(2n/3)
اگر هدف فقط میانه باشه که با t(n/3)+n بدست می آید ولی اگر هدف الگوریتم partition باشد
t(n/3)+t(2n/3)+n بدست می آید
نظر سایر دوستان چیه؟
بحث سقفه
تابلوست که میشه nk
سوال ۹۶ میشه o(n)
سوال ۹۷ نمی دونم میگفتن ۴ میشه
سوال ۹۸ میشه nk این سوال شکلش عوض شده تکراری بود تو سوالات گذشته دیدم گفته بود مقدار بهینه K چقدره؟
سوال ۹۹ میشه هرذو مورد (من اشتباه زدم)
سوال ۱۰۰ میشه log n ترتیبش اینجوریه که حلقه اول یه بار بعد ۲ بار بعد..
۱+۲+۱+۳+۱+۲+۱+۴+۱+۲+۳+۱+۵+...=n/2 1+ n/4 2 + n/6 3+...=1/2=
۱/۲n logn که سرشکنش میشه ۱/۲ log n
بازم اشتباه زدم
سوال ۱۰۱ من زدم درست نادرست نمی دونم درست یا نه اما هرجور حساب که کنی برا ۶ عنصر حداقل ۱۲ مقایسه نیاز داره اگه کسی جواب قطعی داره من منتظرم
(۰۴ اسفند ۱۳۹۰ ۱۱:۳۰ ب.ظ)hussein.sh نوشته شده توسط: سوال ۹۶ میشه o(n)دوست خوبم شما سوال ۱۰۱ رو اشتباه زدین
سوال ۹۷ نمی دونم میگفتن ۴ میشه
سوال ۹۸ میشه nk این سوال شکلش عوض شده تکراری بود تو سوالات گذشته دیدم گفته بود مقدار بهینه K چقدره؟
سوال ۹۹ میشه هرذو مورد (من اشتباه زدم)
سوال ۱۰۰ میشه log n ترتیبش اینجوریه که حلقه اول یه بار بعد ۲ بار بعد..
۱+۲+۱+۳+۱+۲+۱+۴+۱+۲+۳+۱+۵+...=n/2 1+ n/4 2 + n/6 3+...=1/2=
۱/۲n logn که سرشکنش میشه ۱/۲ log n
بازم اشتباه زدم
سوال ۱۰۱ من زدم درست نادرست نمی دونم درست یا نه اما هرجور حساب که کنی برا ۶ عنصر حداقل ۱۲ مقایسه نیاز داره اگه کسی جواب قطعی داره من منتظرم
قسمت الف درسته و اما قسمت ب که دقیقا ۸ سوال در این مورد بدر آزمون های دانشگاه MIT مطرح شده. این مسئله مربوط به درخت تصمیمه جوابش اینه که درخت تصمیم دقیقا ۶ فاکتوریل برگ داره یعنی ۷۲۰ برگ و ما با ۱۰ مقایسه می تونیم مرتب سازی رو انجام بدیم به خاطر اینکه ۲ به توان ۱۰ مقایسه داریم که ۱۰۲۴ می شه و ۷۲۰ از ۱۰۲۴ کوچکتره و از ۲ به توان ۹ که ۵۱۲ می شه بزرگتر که عدد ۱۰ حداقل مقدار جستجو هستش.
من هم nk زدم ولی مدرسان گزینه nlog n زده خیلی خیلی ناراحتم چون جوابهای مدرسا ن که دیدم
انگارهمش[/align] غلط زدم