سوال ۶
فرض کنید $n$ یک عدد طبیعی $(n>2)$ و $r$ یک عدد حقیقی $(0\leq r \leq 1)$ باشد.
دو نفر با نام‌های $A$ و $B$ با یک‌دیگر بازی زیر را انجام می‌دهند: $A$ یک عدد طبیعی $x$ $(1\leq x \leq n)$ را در نظر می‌گیرد. $B$ باید عدد $x$ را پیدا کند. برای این منظور، سوال‌هایی از $A$ می‌پرسد. سوال‌هایی که $B$ از $A$ می‌پرسد به این صورت هستند که «آیا $x$ از $k$ بزرگ‌تر است؟» ($k$ می‌تواند هر عدد طبیعی بین ۱ و $n$ باشد و توسط $B$ انتخاب می‌شود). جواب‌های $A$ به صورت «بله» یا «خیر» است. $A$ ممکن است در جواب بعضی از سوالات دروغ بگوید. اما می‌دانیم که برای هر عدد طبیعی $i$ تعداد دروغ‌هایی که $A$ می‌تواند در جواب سوالات اول تا $i$ ام بگوید از $\lfloor ri \rfloor$ تجاوز نمی‌کند. ( منظور از $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیح نابیش‌تر از $x$ است).
الف) الگوریتمی بنویسید که با فرض $r< \frac{1}{2}$ عدد طبیعی $n$ و عدد حقیقی $r$ را از ورودی دریافت کرده و به جای $B$ بازی کند. یعنی سوالاتی به شکل «$Is \quad x >k?$» در خروجی چاپ کرده پاسخ‌های $A$ را از ورودی دریافت نماید و با توجه به این پاسخ‌ها و این شرط که $A$ نمی‌تواند به بیش از $\lfloor ri \rfloor$ تا از $i$ سوال اول پاسخ دروغ دهد، عدد $x$ را پیدا کند.
در مورد ایده‌ی الگوریتم حرز توضیح داده و متغیرهای آن‌را معرفی نمایید. مثال:
$Bnter \quad n: \quad 10 \\ Bnter \quad r: \quad 0.25 \\ \quad \\ IS \quad x \quad > \quad 5 \quad ? \quad Yes \\ IS \quad x \quad > \quad 8 \quad ? \quad No \\ IS \quad x \quad > \quad 7 \quad ? \quad No \\ IS \quad x \quad > \quad 6 \quad ? \quad Yes \\ IS \quad x \quad > \quad 5 \quad ? \quad No \\ \quad \\ The \quad number \quad (x) \quad is \quad 7$
ب) ثابت کنید که اگر $r \geq \frac{1}{2}$ باشد $A$ می‌تواند طوری به سوالات $B$ جواب دهد که $B$ هیچ‌گاه نتواند عدد $x$ را پیدا کند. (یعنی همواره بیش از یک امکان برای عدد $x$ موجود باشد).
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
