سوال ۳۲

اعداد ۱ تا ۱۰۰ روی محیط یک دایره٬ با ترتیبی تصادفی چیده‌ شده‌اند. ما از محل هیچ عددی اطلاع نداریم. دستگاهی در اختیار داریم که با تعیین مکان ۵۰ عدد متوالی روی دایره٬ کوچک‌ترین آن‌ها را به ما اعلام می‌کند. توجه‌ کنید که دستگاه محل کوچک‌ترین عدد را به ما نشان نمی‌دهد٬ بلکه فقط مقدار کوچک‌ترین عدد را اعلام می‌کند. با حداکثر چند بار استفاده از این دستگاه٬ می‌توان محل عدد ۱ را پیدا کرد؟

  1. ۷
  2. ۹
  3. ۲۵
  4. ۴۹
  5. ۵۰

پاسخ

گزینه‌ی (1) درست است.

با استفاده از الگوریتم جست‌و‌جوی دودویی پیش می‌رویم.ابتدا مکان ۱ تا ۵۰ را مورد سوال قرار می‌دهیم. درصورتی‌که عدد ۱ در بین این ۵۰ مکان بود، کار را با این نیمه ادامه می‌دهیم و در غیر این‌صورت سراغ نیمه‌ی دیگر می‌رویم.

با این کار از نامطلوب بودن نیمی از مکان‌های دور دایره مطمئن می‌شویم.در ادامه هر سوالی که بپرسیم آن خانه‌ها تاثیری در جواب دستگاه ندارند.پس می‌توان از وجودشان صرف نظر کرد (نیمه‌ی سیاه).

در هر مرحله نیمی از خانه‌های سفید (و به تعداد مورد نیاز خانه‌ی سیاه) را می‌پرسیم و با اطمینان نیمی از سفیدها را کنار می‌گذاریم.با طی ۷ مرحله‌ی زیر به عدد ۱ می‌رسیم: (هر عدد، تعداد خانه‌های باقی مانده که یکی از آن‌ها مکان عدد ۱ است را نشان می‌دهد.)

$50\rightarrow25\rightarrow13\rightarrow7\rightarrow4\rightarrow2\rightarrow1$