تالار گفتمان مانشت

دوستان عزیز میشه توضیح بدید چرا گزینه 1 میشه!؟

ممنون میشم.

on یکم مشکوکه. من نتونستم چیزی با این مرتبه به دست بیارم. چون گفته با هزینه مصرفی ثابت. اگه نمی گفت میشد به دست بیارین. nolgn که مشخصه میشه با مرتب سازی و بعدش پیدا کردن این عنصر با هزینه مصرفی ثابت
یه سوال کی میشه از هش استفاده کرد؟ اگه بگن یا نه و مرتبه اش به طور متوسط چقدره؟

من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی 2n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از 0 تا n/3 ، از n/3 تا 2n/3 و از 2n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا 2n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و 2n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو 2 تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها

(17 بهمن 1391 05:14 ب.ظ)armin_b00ter نوشته شده توسط: [ -> ]من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی ۲n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از ۰ تا n/3 ، از n/3 تا ۲n/3 و از ۲n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا ۲n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها

روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه 1 درسته این مدلی تحلیل می کنیم!قبول داری؟!
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون

(17 بهمن 1391 05:33 ب.ظ)8Operation نوشته شده توسط: [ -> ]روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون

به نظر من که اصلا نباید سر همچین سوالایی واسیتاد. باید ردشون کنی و وقتی وقت اضافه داشتی بیای سرشون. بعدشم باید نگاه کنی به گزینه ها. logn که یه جورایی معلومه نمیشه. nlogn هم که راحت میشه واسش جواب پیدا کرد. پس اینجا می مونه n. حالا باید زور بزنی با استفاده از ابزارایی که داری و بلدی یه راه حل پیدا کنی واسش. اگه تونستی میزنی n اگر نتونستی نمی زنی سوالو

عالی

برای این مثال لطفا توضیح بدین
123456333344335555
123456
333344
335555
n=18
جواب سه هست
الآن بیشینه ها رو باید محاسبه کنیم تو هر بخش؟
یکیش که اصلا مشخص نیست بیشینه چیه. بعدیش میشه سه و بعدیش هم میشه پنج

اون طوری که من فهمیدم، با محاسبه بیشینه در هر بخش، حتما یکی از بیشینه ها عدد موردنظر است که استدلال درستی است.
برای مثالی مثل n=18
3و2و3و4و2و4
5و3و5و3و1و1
3و8و3و8و3و8
که جزو سخت ترین مثالهاست کاری که باید بکنیم اول محاسبه بیشینه است در هر بخش.
که میشه 2و3و4 هر کدام دو در بخش اول، 1و3و5 هر کدام دو در بخش دوم و 3و8 هر کدام سه در بخش سوم با داشتن تعداد آنها و جمعشان سه عدد موردنظر است.
می توان اثبات کرد که برای نگه داری اطلاعات بیشینه ها به تعداد خانه های ثابت نیاز است