سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 10:07:59 -0600 امیر شکریآمار پرسش:
- پرسیده شده: 2015-08-10 05:42:12 -0600
- مشاهده شده: 94 بار
- بروز شده: 2015-08-13 08:36:29 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
انتخاب 1001 امین وزنه با 11 حرکت
2000 تا وزنه داریم به این صورت:
a1 < a1 < ....< a1000
و
b1 < b2 < .... < b1000
1001 امین وزنه را با 11 بار وزن کردن بیابید.
2015-08-10 05:42:12 -0600
رادیواکتیو 159 ● 2 ● 2 ● 11
نظرات
1 پاسخ
خب کاندیدو خونه هایی تعریف میکنیم ک میتونن 1001 امین وزنه باشن
هر دفه میایم کاندیدای a و کاندیدای b رو نصف میکنیم خونه ی وسطشونو میگیریم(مثلا خونه وسط a "وی" باشه خونه وسط b هم "یو")(اگه فرد بودن اگه واسه یکی کف n/2رو گرفتیم واسه یکی دیگه سقفو میگیریم) اگه مساوی بودن ک مساوین جواب هم یکی از اوناست اگه ک نه فرض کنیم وی بزرگتر از یوئه کاندیدای بزرگ تر از v رو تو a و کوچیکتر از uرو تو b حذف میکنیم حالا اگه یو بزرگ تر از ویه برعکس میشه دیگ
فرض کنیم آخرین مقایسه ای ک انجام شد بین x,y باشه هر کروم بزرگتر بودن جواب مسئله است
اثباتش:با استقرا و به سختی اثبات میشه هر خونه ای با 1000 منهای شماره همون خونه مقایسه میشه
پس وقتی بعد از مقایسه مثلا یو بزرگتر از ویه اعداد بزرگتر از u دیگ نمیتونن جز کاندیدا باشن چون حداقل 1000 نفر کوچیکتر از u هستن.دیگ فوقش u بتونه 1001 امین عدد باشه
اعداد کوچیکتر از v هم نمیتونن باشن چون حداکثر 1000 امین عددن چون اعداد کوچیکتر از u +اعداد کوچیکتر از vمیشه1000
حالا چون هر دفه نصف کردیم تعداد راهها یه چیزی حول و حوش(!املاشو نمیدونم)10 میشه میگی 11 حتما میشه دیگ
2015-08-13 08:36:29 -0600
هادیزاده 264 ● 4