المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۴:سوال ۹

سوال ۹

برای دو عدد صحیح $a$ و $b$٬ مقدار $x= a \oplus b$ را به این صورت به دست می‌آوریم: ابتدا $a$ و $b$ را به مبنای ۲ می‌بریم و این دو عدد دودویی را طوری زیر هم می‌نویسیم که ارقام هم‌ارزش آن‌ها زیر هم قرار گیرند. حال برای هر دو رقمی که زیر هم نوشته شده‌اند٬ اگر آن دو رقم برابر بودند زیر آن‌ها صفر٬ و اگر برابر نبودند زیر آن‌ها یک می‌نویسیم. به این ترتیب عدد $x$ (در مبنای ۲) در زیر دو عدد $a$ و $b$ به دست می‌آید. اگر کمی دقت کنید متوجه می‌شوید که $ a \oplus b = b \oplus a$ و نیز $a \oplus b \oplus c = (a \oplus b) \oplus c= a \oplus (b \oplus c)$ . مثلاً $\oplus$ بر روی اعداد ۲۰۴٬۲۴۰٬۲۵۶ و ۱۷۰ برابر ۴۰۶ است٬ چون $100000000 \oplus 11110000 \oplus 11001100 \oplus 10101010= 110010110$.

مقدار $\oplus$ بر روی اعداد ٬۱۳۸۲ ٬۱۳۸۳…٬ ٬۲۰۰۳ ۲۰۰۴ کدام است؟

  1. ۳۱۱
  2. ۶۰۹
  3. ۱۰۲۴
  4. ۱۳۸۱
  5. ۲۰۰۵

پاسخ

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

تبدیل یافته تمام اعداد از ۱۰۲۴ تا ۲۰۴۳ در مبنای ۲ عددی ۱۱ رقمی می‌شوند. بنابراین تبدیل یافته تمام اعداد داده شده در مبنای ۲ عددی ۱۱ رقمی می‌شود. از طرف دیگر معلوم می‌شود که رقم $i$ ام عدد حاصل از عمل یاد شده برای اعداد داده شده برابر ۱ است اگر تعداد ۱های موجود در جایگاه $i$ام کل آن اعداد فرد باشد و در غیر این صورت رقم برابر ۰ است. تعداد اعداد داده شده برابر ۶۲۳ است که عددی فرد است٬ بنابراین در جایگاه یازدهم به تعداد ۶۲۳ رقم ۱ وجود دارد به این معنا که رقم یازدهم از عدد حاصل ۱ است و در نتیجه آن عدد بین ۱۰۲۴ و ۲۰۴۳ می‌باشد. رقم دهم از اعداد معادل اعداد ۱۰۲۴ تا ۱۵۳۵ در مبنای ۲ برابر ۰ و آن رقم در معادل‌های اعداد از ۱۵۳۶ تا ۲۰۴۳ برابر ۱ می‌باشد$(1023+\frac{1024}{2}=1535$ ٬‌ بنابراین رقم دهم از معادل‌های اعداد از ۱۳۸۲ تا ۱۵۳۵(که تعداد آن‌ها زوج است) برابر ۰ و آن رقم در معادل‌های اعداد از ۱۵۳۶ تا ۲۰۰۴(که تعداد آن‌ها فرد است) برابر ۱ می‌باشد و در نتیجه چون در تعداد فردی از ۶۲۳ عدد داده شده رقم دهم برابر ۱ باشد٬ بزرگ‌تر یا مساوی $1024+512$ می‌باشد که در بین گزینه‌ها فقط گزینه آخر در این محدوده می‌گنجد.


ابزار صفحه