سلام دوستان
میشه لطف کنید بگید این سوال تو قسمت ۵ و ۶ چی میگه؟گزینه ها چی میگن کلا؟گزینه هایی که ماهان داده بجای - علامت + گذاشته!حتی اگه اینا = هم باشه من جوابو متوجه نمیشم.صورت سوال و گزینه های ماهان هم با اینی که پارسه گذاشته متفاوته!تنها جوابیم که پارسه داده اینه که گزینه ۱ درسته
لطفا اگه کسی بلده جواب بده منم با این سوالا مشکل داشتم ، پیشاپیش سپاسگذارم
سلام
اگه برا هر مجموعه یه مثال بزنین راحت میتونین متوجه منظور سوال بشین
در واقع اگه برا {a{2,5,7 برا {b{1,3,8 در نظر بگیرین حالا k میشه ۱ و x برابر ۵ i برابر ۲ میشه و شرط اول در این مجموعه صدق نمیکنه باید با دومی حل بشه
توضیحش یکم سخته اما جواب به نظرم این طوری به دست میاد که میانه مجموعه اول میتونه از همه مجموعه دوم بزرگتر باشه که میشه (T(n,m و یا نه میانه اولی از نصف مجموعه دوم بزگتر باشه که میشه (T(n/2,m و در مورد رابطهی بازگشتی مجموعه با جواب log m به دست میاد
ولی (O(1 نمیدونم چرا در نظر گرفته شاید اگه دو تا مجموعه یکسان باشن همون اول جواب به دست میاد به همین دلیل در نظر گرفته دلیل غیر این به ذهنم نرسید
حالا این نظر خودمه دوستان اگه نظری دارن خوشحال میشم متوجه اشتباهم بشم
(۱۵ بهمن ۱۳۹۲ ۰۱:۴۴ ب.ظ)*afsoon* نوشته شده توسط: سلام
اگه برا هر مجموعه یه مثال بزنین راحت میتونین متوجه منظور سوال بشین
در واقع اگه برا {a{2,5,7 برا {b{1,3,8 در نظر بگیرین حالا k میشه ۱ و x برابر ۵ i برابر ۲ میشه و شرط اول در این مجموعه صدق نمیکنه باید با دومی حل بشه
توضیحش یکم سخته اما جواب به نظرم این طوری به دست میاد که میانه مجموعه اول میتونه از همه مجموعه دوم بزرگتر باشه که میشه (T(n,m و یا نه میانه اولی از نصف مجموعه دوم بزگتر باشه که میشه (T(n/2,m و در مورد رابطهی بازگشتی مجموعه با جواب log m به دست میاد
ولی (O(1 نمیدونم چرا در نظر گرفته شاید اگه دو تا مجموعه یکسان باشن همون اول جواب به دست میاد به همین دلیل در نظر گرفته دلیل غیر این به ذهنم نرسید
حالا این نظر خودمه دوستان اگه نظری دارن خوشحال میشم متوجه اشتباهم بشم
من متاسفانه متوجه توضیحتون برای قسمت ۵و۶ نشدم
O(1) برای کارای به دست اوردن r و k هست.Log m هم برای جستجو در ارایه B
با مثال میتونین متوجه بشین
در واقع r داره کمک میکنه که بدونیم میانه اشتراک دو مجموعه از مجموعه aانتخاب میشه یا b
اگه r کمتر باشه مقدارش از n/2+i یعنی میانه اشتراک مجموعه ها از بین مجموعه {a{1...n/2 , و {b{1...iبه دست میاد ر غیر این صورتم که از مرحله ۶
(۱۵ بهمن ۱۳۹۲ ۰۶:۰۳ ب.ظ)*afsoon* نوشته شده توسط: با مثال میتونین متوجه بشین
در واقع r داره کمک میکنه که بدونیم میانه اشتراک دو مجموعه از مجموعه aانتخاب میشه یا b
اگه r کمتر باشه مقدارش از n/2+i یعنی میانه اشتراک مجموعه ها از بین مجموعه {a{1...n/2 , و {b{1...iبه دست میاد ر غیر این صورتم که از مرحله ۶
اون صفرها نقطه س؟؟
هی من میگم این ۱۰۰m ینی چی چیه آخه!دستتون درد نکنه
ببخشید من همش مشکلم اینه که متوجه نمیشم اون اندیسهای A, B چی هستن؟میشه محدوده A,B رو تو مرحله ۶ بگید؟
شما منظورتون اینه که با مثال متوجه اون محدوده بشم چون تایپش اشتباس؟؟
جوابی که تو گزینه ۱ هست T(n/20m) منظورش T(n/2,m) هست؟؟T(n,m) رو برای مرحله ۶ نوشته و T(n/2,m) برای مرحله ۵/و چون فقط یکیشون قابل انجام هست منها کرده؟
خیلی ممنون میشم به این سوالا هم پاسخ بدین.
صورت درست سوال:
Sent from my C5303 using Tapatalk
(۱۶ بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط: صورت درست سوال:
Sent from my C5303 using Tapatalk
دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو
۱ در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m
در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶
که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)
(۱۷ بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)Good! نوشته شده توسط:(16 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط: صورت درست سوال:
Sent from my C5303 using Tapatalk
دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۷ بهمن ۱۳۹۲ ۱۰:۴۲ ب.ظ)nafas_70 نوشته شده توسط:(17 بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)Good! نوشته شده توسط:(16 بهمن ۱۳۹۲ ۱۰:۳۸ ب.ظ)nafas_70 نوشته شده توسط: صورت درست سوال:
Sent from my C5303 using Tapatalk
دوست عزیز دستت درد نکنه ولی نمیتونم ببینم تصویرو
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
دستت درد نکنه خیلی لطف بزرگی کردی
(۱۷ بهمن ۱۳۹۲ ۰۹:۴۰ ب.ظ)tayebe68 نوشته شده توسط: 1 در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m
در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶
که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)
دستت درد نکنه خیلی لطف بزرگی کردی.ممنونم از همه تون
(۱۷ بهمن ۱۳۹۲ ۰۹:۴۰ ب.ظ)tayebe68 نوشته شده توسط: 1 در زمان ۱
۲ چون مرتبه در زمانه ۱
۳ با جستجوی دودویی در زمان log m
۴ در زمان ۱
۵ اگر شرط برقرار باشه A(1..n/2یعنی نصف آرایه A و B(1..i (که در بدترین حالت i می تونه برابر m باشه)؛ این دو تا رو صدا می زنه. پس اینجا میشه T(n/2,m
۶ اگه شرط برقرار نباشه این قسمت رو اجرا می کنه که دوباره نصف A و در بدترین حالت کل B صدا زده می شوند. یعنی T(n/2,m
در ضمن خط ۵ و ۶ همزمان اجرا نمیشن، یا ۵ اجرا می شه یا ۶
که جمع بالایی ها میشه
T[n,m]=T[n/2,m]+logm+O(1)
دستت درد نکنه خیلی لطف بزرگی کردی.ممنونم از همه تون