المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۲۱:سوالات ۲۷ و ۲۸ و ۲۹ و ۳۰

سوالات ۲۷ و ۲۸ و ۲۹ و ۳۰

برنامه‌ی زیر را در نظر بگیرید:

  1. عدد $X$ را از ورودی بگیر.
  2. مقدار عدد $Y$ را برابر صفر قرار بده.
  3. باقی‌مانده‌ی تقسیم عدد $X$ بر ۲ را $B$ بگیر.
  4. مقدار $Y$ را برابر $2\times Y + B$ قرار بده. (مثلا اگر $Y$ مساوی ۵ و $B$ برابر ۱ است٬ مقدار $Y$ برابر ۱۱ خواهد شد).
  5. مقدار $X$ را برابر خارج قسمت تقسیم خودش بر ۲ قرار بده. (مثلا اگر $X$ برابر ۱۳ بود٬ مقدار $X$ به ۶ تغییر خواهد یافت).
  6. اگر $X$ بزرگتر از صفر است٬ به مرحله ۳ برو. در غیر این صورت به مرحله ۷ برو.
  7. مقدار $Y$ را به عنوان خروجی برگردان.
  8. پایان

می‌بینیم اگر مقدار ۱۲ را به عنوان ورودی $X$ بدهیم٬ خروجی برنامه برابر ۳ خواهد بود.

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

سوال ۲۷

فرض می‌کنیم اگر عدد ورودی $X$ را در مبنای دو بنویسیم به صورت $X'$ (متشکل از ۰ و ۱) خواهد بود و اگر خروجی برنامه را در مبنای ۲ بنویسیم به صورت $Y'$ خواهد بود. $Y'$ همواره چه نسبتی با $X'$ دارد؟

  1. تعداد «یک»های رشته‌ی $X'$ است.
  2. تعداد «صفر»های رشته‌ی $X'$ است.
  3. زیررشته‌ای از $X'$ است با حذف تعدادی از ارقام مبنای دوی $X'$.
  4. مقسوم‌علیه‌ای از $X'$ است.
  5. برعکس شده (متقارن) $X'$ است با حذف صفرهای سمت چپ.

پاسخ

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

این الگوریتم برای عدد $x$ آن را بگونه‌ای به مبنای ۲ می‌برد که رقم سمت راست پر‌ارزش‌ترین بیت باشد پس در واقع مقداری دودیی عدد را متقارن می‌کند.

سوال ۲۸

اگر ورودی برنامه مقدار $X$ باشد٬ خروجی متناظر آن را $R(X)$ می‌نامیم؛ مثلا طبق آنچه گفته شد مقدار $R(۱۲)$ برابر ۳ است. مقدار $R(۴۴۴)$ کدام گزینه است؟

  1. ۱۱۱
  2. ۵۵
  3. ۵۹
  4. ۵۷
  5. ۱۲۳

پاسخ

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

طبق۲۷: ۴۴۴در مبنای دو برابر با (۱۱۰۱۱۱۱۰۰) است که برعکس آن (۱۱۱۱۰۱۱) می‌شود که همان۱۲۳است.

سوال ۲۹

عدد $A$ را زیبا می‌نامیم اگر $R(A)\gt A$ باشد. مثلا عدد ۱۱ یک عدد زیبا است چرا که $R(۱۱) = ۱۳$ و $۱۳\gt ۱۱$ است. اما عدد ۱۲ یا عدد ۷ زیبا نیستند. چند عضو از مجموعه‌ی {٫۶۳…۱٫۲٫۳٫} زیبا هستند؟

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

پاسخ

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

ابتدا اعدادی که یکانشان صفر هست را حذف می‌کنیم. چرا که در طی این عملیات تعداد ارقام کم‌تری دارند و در نتیجه عدد نهایی کم‌تر از قبل خواهد شد.

در بین بقیه‌ی اول، اعداد متقارن (عددی که $R(A)=A$) را حذف می‌کنیم. از باقی اعداد دقیقا نصفشان زیبا هستند چرا که دو به دو بایک‌دیگر جفت هستند و پس از اعمال تغییر به دیگری تبدیل می‌شوند.

اعداد فرد: ۳۲ تا

اعداد متقارن فرد: رقم یکان این اعداد یک هست. در نتیجه باتوجه به این‌که طول عدد، بین ۱ تا ۶ باشد به ترتیب ۱، ۱، ۲، ۲، ۴ و ۴تا عدد متقارن داریم. در نتیجه تعداد آن‌ها ۱۴تاست.

پس طبق نکات گفته شده تعداد اعداد زیبا برابر است با $\frac{32-14}{2}=9$.

سوال ۳۰

چند تا از اعداد بین $۲^{۱۲}$ تا $۲^{۱۳}$ (شامل خود این دو عدد) زیبا هستند؟

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

پاسخ

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

طبق نکاتی که در سوال ۲۹ گفته شد:

اعداد فرد: $2^{11}$.

اعداد متقارن فرد: چون رقم سیزدهم این اعداد یک است پس ۱۱ رقم دیگر باقی می‌ماند که $2^6$ عدد بدست می‌آید (۵ رقم دیگر بصورت یکتا مشخص می‌شوند).

در نتیجه تعداد اعداد زیبا برابر است با:$\frac{2^{11}-2^6}{2}=992$.


ابزار صفحه