سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:19:31 -0600 امیر شکریآمار پرسش:
- پرسیده شده: 2016-05-13 15:55:58 -0600
- مشاهده شده: 255 بار
- بروز شده: 2016-05-14 10:23:22 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
یافتن کارت درست از بین ۱۰۰۰ کارت با حداکثر یک دروغ!
روبروی ما ۱۰۰۰ کارت به ترتیب از چپ به راست روی یک میز (خیلی طولانی) چیده شده. روی هر کارت عددی نوشته که ما آن را نمی‌بینیم اما می‌دانیم اعداد کارت‌ها از چپ به راست اکیدا صعودی است. همچنین می‌دانیم عدد ۱۳۹۵ روی یکی از کارت‌ها نوشته شده. می‌خواهیم جایگاه آن را پیدا کنیم.
می‌توانیم هر دفعه یک کارت را انتخاب کنیم و دوستمان به ما می‌گوید که آیا عدد نوشته شده روی آن کارت از ۱۳۹۵ بیشتر است یا خیر (فقط بله یا نه). دوستمان حداکثر می‌تواند ۱ بار دروغ بگوید. آیا می‌توانیم با حداکثر ۱۵ پرسش، کارت مورد نظر را پیدا کنیم؟
2016-05-13 15:55:58 -0600
کلاه قرمزی 3097 ● 21 ● 34 ● 57
نظرات
1 پاسخ
سلام به همگی !
بنظرم با ۱۵ میشه . یعنی برای هر $n$ با $3\lceil log_4 n \rceil$ با این تعداد راحت میشه پیدا کرد .
به جایی اینکه توی هر گام بیایم دو قسمت کنیم توی هر گام بیایم ۴ قسمت کنیم بعنی ۳ تا عدد بپرسیم که که بینشون $\frac{n}{3}$ تا عدد باشه بعد اگه توی یکی از این ۳ عدد دروغ وجود داشته میشه فهمید چرا که اگه یه جواب ها با هم تناقض نداشته باشن یعنی دروغ نگفته و اگه دروغ گفته باشه اونی که دروغ گفته با دوتا در تناقضه پس مشخص میشه .
چون $n=1000$ پس با $3\lceil log_4 1000 \rceil = 15$ تا عمل میشه دیگه !
2016-05-14 10:23:22 -0600
چشمک 2291 ● 29 ● 67 ● 119
نظرات
سلام. در بعضی از حالات میشه، ولی به طور کلی فکر نکنم بشه از روی سه تا سوال قضاوت کرد دروغی وجود داره یا نه.
2016-05-14 12:45:35 -0600 کلاه قرمزی