المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۲۱:سوالات ۱۵ و ۱۶ و ۱۷

سوالات ۱۵ و ۱۶ و ۱۷

دستگاه «ایکس-اُر» (XOR) دو عدد می‌گیرد و یک عدد برمی‌گرداند. این دستگاه ابتدا دو عدد ورودی را به مبنای ۲ می‌برد و با افزودن تعداد مناسبی صفر به سمت چپ عدد کوتاه‌تر٬ تعداد رقم‌های آن دو عدد را برابر می‌کند. سپس عدد دوم را زیر عدد اول (در دو سطر٬ شبیه وقتی که بخواهیم آن‌ها را جمع کنیم) می‌نویسد به صورتی که رقم $i$ام عدد اول بالای رقم $i$ام عدد دوم قرار بگیرد. حال هر دو رقم را که در یک ستون قرار دارند مقایسه می‌کند: اگر مساوی بودند زیر آن‌ها و در سطر سوم یک رقم ۰ می‌نویسد٬ و در صورتی که یکسان نبودند زیر آن‌ها رقم ۱ می‌گذارد. در انتها با تبدیل عدد دودویی نوشته شده در سطر سوم از مبنای ۲ به مبنای ۱۰ و تحویل آن در خروجی٬ کار پایان می‌یابد. مثلا اگر به دستگاه اعداد ۵ و ۱۲ را بدهیم٬‌دستگاه با تبدیل آن‌ها به مبنای دو٬ عددهای $(0101)_2$ و $(1100)_2$ را تولید کرده در دو سطر می‌نویسد و با توجه به آن‌ها عدد $(1001)_2$ در سطر سوم درج خواهد شد و لذا دستگاه عدد ۹ را به عنوان خروجی برمی‌گرداند.

با توجه به توضیح بالا به سه سوال زیر پاسخ دهید:

سوال ۱۵

علی ۳۱ کارت با شماره‌های ۱ تا ۳۱ دارد. او هر بار یک جفت کارت را که مجموع شماره‌ی آن‌ها برابر ۳۲ است انتخاب و شماره‌ی آن دو کارت را به ورودی دستگاه می‌دهد. اگر علی این کار را برای تمامی زوج‌ کارت‌هایی که مجموع شماره‌شان ۳۲ است انجام دهد٬‌ بزرگترین عددی که در خروجی دستگاه XOR ظاهر می‌شود چقدر است؟

  1. ۳۰
  2. ۹۳۰
  3. ۲۹
  4. ۳۱
  5. ۳۲

پاسخ

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

اعداد ما حداکثر ۵ بیتی هستند. پس خروجی هم ۵ بیتی است. همچنین اگر دو عدد در تمام بیت‌ها متمایز باشند جمع آن‌ها۳۱ می‌شود (چرا؟).

پس‌اعدادی که علی به دستگاه می‌دهد حداقل در یک بیت یکسان‌اند و در نتیجه عدد خروجی نمی‌تواند ۳۱ باشد.

حال اگر اعداد ۱ و ۳۱ را به دستگاه بدهد عدد خروجی ۳۰ می‌شود. پس ۳۰ بیش‌ترین مقدار خروجی است.

سوال ۱۶

برنامه‌ی زیر چه عددی را چاپ خواهد کرد؟

۱) $s$ را برابر ۰ قرار بده.

۲) برای $i$ از ۱ تا ٬۱۳۹۰ دو دستور زیر را اجرا کن:

۱.۲) اعداد $i$ و $i+۱$ را به ورودی دستگاه بده و عدد خروجی را در $x$ قرار بده.

۲.۲) اعداد $x$ و $s$ را به ورودی دستگاه بده و عدد خروجی را در $s$ قرار بده.

۳) مقدار $s$ را چاپ کن.

  1. ۱۳۹۱
  2. ۱۳۹۲
  3. ۱۳۹۰
  4. ۰
  5. ۱

پاسخ

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

مقدار s در هر مرحله این‌گونه به‌دست می‌آید:

می‌دانیم درصورتی که در $XOR$ یک عدد دوبار ظاهر شود خنثی می‌شود و همانند آن است که ظاهر نشده است. در نتیجه در طی این عملیات تمامی اعداد به جز عدد آخر دوبار ظاهر می‌شوند و در نتیجه در انتها عدد نهایی یعنی ۱۳۹۰ باقی می‌ماند.

سوال ۱۷

برنامه‌ی زیر چه عددی را چاپ خواهد کرد؟

۱) $s$ را برابر ۰ قرار بده.

۲) برای $i$ از ۱ تا ٬۹۰ دو دستور زیر را اجرا کن:

۱.۲) اعداد $i$ و $i+۱$ را به ورودی دستگاه بده و عدد خروجی را در $x$ قرار بده.

۲.۲) مقدار $s+x$ را در $s$ قرار بده.

۳) مقدار $s$ را چاپ کن.

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

پاسخ

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

این الگوریتم مجموع $XOR$ زوج‌های متوالی از 1 تا 90 راحساب می‌کند.

کم‌ارزش‌ترین بیت دو عدد متوالی با هم متفاوت‌اند. پس $XOR$ آن‌ها حتما فرداست.

مقدار این $XOR$ برای ۱ و ۲ برابر ۳ و برای سایر زوج اعداد نیز بزرگ‌ترازصفر است. پس حاصل جمع $XOR$ ها از ۹۰ بیش‌تر خواهد بود. چون همه‌ی این اعداد فرد‌ هستند و تعداد آن‌ها ۹۰ تا است مجموع آن‌ها زوج می‌شود.

تنها گزینه‌ای که این شرایط را دارد گزینه‌ی (۳) است.


ابزار صفحه