(۲۱ بهمن ۱۳۹۱ ۱۲:۴۳ ب.ظ)arash16 نوشته شده توسط: (20 بهمن ۱۳۹۱ ۰۵:۱۵ ب.ظ)somaye_tex نوشته شده توسط: (20 بهمن ۱۳۹۱ ۰۴:۵۴ ب.ظ)fsi2013 نوشته شده توسط:
راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا
شما هر جایگشتی دوست دارین بدین من با این روش براتون حل می کنم. 
البته بین ۱۱ و ۱۲ شک دارم. کامل وقت نشد حلش کنم.
راه حل من:
۵ تا جعبه با شماره های زیر رو باز می کنیم:
۱ و ۸ و ۱۶ و ۲۴ و ۳۱
از بین اینها یکی از بقیه بزرگتره. اگه ۱ و ۳۱ باشه بدترین حالت نمیشه . پس به فرض میگیریم شماره ۲۳/ پس حتماً از ۱۶ تا ۳۱ جعبه ای وجود داره که حاوی عددیه که از ۲ جعبه کناریش نا کوچکتر باشه. (البته این وجود یه همچین جعبه ای رو در نیمه اول نقض نمیکنه! ولی در این نیمه هم حتماً خواهیم داشت.....)
لطفاً حالتهای مختلف رو خودتون بررسی کنید چون یه کم توضیحش اینجا سخته. ولی به راحتی قابل اثباته و مثال نقضی وجود نداره!
و سپس ۲۰ و ۲۷ رو باز می کنیم و دوباره از بین این ۵ عدد بزرگترین رو پیدا و دوباره طبق الگوریتم بالا نصف دیگر از جعبه ها رو حذف میکنیم و به همین ترتیب این الگوریتم رو به صورت تکراری انجام میدیم. که برای هر مرحله ۲ جعبه باز می کنیم. به جز اول کار که برای ۵ جعبه باز کردیم.
با یه حساب سرانگشتی جمع جعبه هایی که باز میشه در بدترین حالت اگه جعبه ها رو به صورت هوشمندانه انتخاب کنیم میشه ۱۱ تا!
البته الگوریتم رو از خودم درآوردم ولی فکر میکنم کار میکنه.....
دوست عزیز اگر همه ی این اعداد این جعبه ها که میگید مساوی باشه چی؟؟ بعدش کجا رو باز میکنید؟؟ آخه شما وقتی یه الگوریتمی رو دقیق بیان کنید، من مطمئنم بازم میشه مثال نقض واسش در آورد که مجبور به باز کردن همه ی جعبه ها باشی.. اما شما اعداد رو مینویسی بعد با توجه به اعداد (جعبه های باز شده) الگوریتم رو داری بیان میکنی..
خوب......
تصمیم گرفتم این مسأله رو حل کنم.
البته روش باینری سرچ که دوستمون گفتن از اساس و بنیاد غلطه! چون اینکه صعودی یا نزولی باشه من با دو حرکت بهتون جوابو میگم..... که خب چون خیلی غلطه بهتره راجع بهش بحث نکنیم....
خب. همیشه برای هر الگوریتم یه اصل بنیادی وجود داره که برای اینکه متوجه بشیم الگوریتم چطور کار می کنه ابتدا باید اونو متوجه بشیم تا دچار پیچیدگیهای جزئی الگوریتم نشیم.
اصل بنیادی که راه حل من بر اون اساس کار می کنه:
اگه ۵ عدد مجهول داشته باشیم و از اعداد شماره ۱ و ۳ و ۵ اطلاع داشته باشیم و ۳ از ۱ و ۵ بزرگتر باشه به سادگی چون حالات محدوده میشه ثابت کرد حتماٌ حداقل یکی از بین ۲ و ۳ و ۴ دارای مشخصات خواسته شده در سؤال هست. حالات مختلف رو می تونید چک کنید.
در این سؤال ما به دنبال عضوی می گردیم که از جعبه های مجاورش ناکوچک تر باشه. مساوی یا بزرگ تر!
اتفاقاً اینکه همه جعبه ها مساوی باشند حتی نیاز به ۱۱ بار باز کردن جعبه هم نداره! با تعداد کمتری میشه حلش کرد.
خوب............
فرض می کنیم در یه آرایه ۱۰ تایی دنبال این عضو می گردیم:
- - - - - - - - - -
۵ خونه رو باز می کنیم. دقت کنین باز کردن ۵ تا خونه به این دلیل هست که حداقل بتونیم به اندازه ی کف n/2 از جعبه ها رو حذف کنیم.
۵ تا خونه شامل خونه های ۱ و ۱۰ و خونه ۵ و خونه ۳ و خونه ۷ میشه.
پس تا اینجا داریم:
x - y - w - z - - n
حالا این ۵ عدد رو با هم مقایسه می کنیم:
در این حالت بالا قبول دارین که بدترین حالت میشه وقتی که z از همه بزرگتر باشه. پس از x تا w رو حذف می کنیم. نمی گم که در این نیمه که حذف کردیم امکان نداره که جعبه ای با شرایط خواسته شده داشته باشیم. اما در قسمتی که نگه داشتیم حتماً طبق اصل بالا یک جعبه با شرایط خواسته شده داریم.
خوب حالا خونه ۶ و خونه ۸ رو باز می کنیم. اگه خونه ۶ یا ۷ از همه بزرگتر باشه که مسأله حل شده است توجه داشته باشید که n و w نمی تونن از همه بزرگتر باشن چون قبلاً با z مقایسه شدن و از z کوچکتر بودن.
بدترین حالت وقتی میشه که ۸ از همه بزرگتر باشه که مجبور به باز کردن خونه ۹ هم میشیم. حتی در مثال ساده بالا با ۱۰ عنصر هم مشاهده کردید که نیازی به باز کردن تمام جعبه ها نیست! و ما به راحتی به جواب می رسیم. اگه همین الگوریتم رو برای ۳۱ عنصر انجام بدین در بدترین حالت به عدد ۱۱ می رسین. به همین سادگی....
بازم اگه دوستان مایلند هر جایگشتی می خوان بدن من با حداکثر ۱۱ حرکت براشون یه عضو با مشخصات خواسته پیدا می کنم. امیدوارم خوب توضیح داده باشم......
)
