المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۲:سوالات ۲۲ و ۲۳ و ۲۴

سوالات ۲۲ و ۲۳ و ۲۴

الگوریتم زیر را در نظر بگیرید:

  1. مقدار $x$ را برابر با عدد $A$ قرار بده.
  2. مقدار $y$ را برابر با صفر قرار بده.
  3. تا وقتی که $x$ بزرگتر از صفر است عملیات زیر را انجام بده:
    1. $B$ را برابر با باقیمانده‌ي تقسیم $x$ بر ۱۰ در نظر بگیر.
    2. $y$ را برابر با مقدار $y\times ۱۰ + B$ قرار بده.
    3. $x$ را برابر با خارج قسمت تقسیم $x$ بر ۱۰ قرار بده.
  4. $x$ را برابر با $y + A$ قرار بده.

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

سوال ۲۲

فرض کنید اعداد ۱ تا ۱۰۰۰۰ را به عنوان $A$ به الگوریتم بدهیم. به ازای چند مقدار از آنها عدد خروجی بر ۳ بخش پذیر است؟

  1. ۱۶۶۶
  2. ۱۰۰۰۰
  3. ۳۳۳۳
  4. ۶۶۶۷
  5. ۶۶۶۶

پاسخ

گزینه‌ی «۳» درست است.

با بررسی این الگوریتم متوجه می‌شویم که عدد را وارونه می‌کند(یعنی مثلا وارون ۱۲۳ می‌شود ۳۲۱) و صفرهای پشت عدد را نیز پاک می‌کند. از آن‌جاکه باقی‌مانده هر عددی بر ۳ برابر باقی‌مانده وارون آن بر ۳ است، پس تنها الگوریتم به ازای آن اعدادی که بر ۳ بخش‌پذیرند، عددی بخش‌پذیر بر ۳ می‌دهد. درنتیجه جواب می‌شود: ۳۳۳۳

سوال ۲۳

فرض کنید اعداد ۱ تا ۱۰۰۰۰ را به عنوان $A$ به الگوریتم بدهیم. به ازای چند مقدار از آنها عدد خروجی بر ۲ بخش پذیر است؟

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

پاسخ

گزینه‌ی «۴» درست است.

از آن‌جا که تنها در صورتی خروجی الگوریتم زوج می‌شود که جمع رقم اول و آخر عدد ورودی زوج شود، پس می‌آییم این تعداد را می‌شماریم.

9 عدد یک رقمی داریم با این ویژگی.

تعداد اعداد دو رقمی با این ویژگی برابر است با : $5\times5+5\times4=45$

و اعداد سه رقمی همان قبلی با یک ضریب ۱۰ و اعداد ۴ رقمی نیز ۱۰۰ برابر اعداد دو رقمی. پس در کل داریم :

$9+45+450+4500=5004$

سوال ۲۴

فرض کنید اعداد ۱۰۰۰ تا ۹۹۹۹ را به عنوان $A$ به الگوریتم بدهیم. به ازای چند مقدار از آنها عدد خروجی یک عدد اول است؟

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

پاسخ

گزینه‌ی «۴» درست است.

با توجه به قاعده بخش پذیری بر عدد ۱۱ در می‌یابیم که تمام اعداد خروجی بر ۱۱ بخش‌پذیر هستند، پس هیچ عدد اولی تولید نمی‌شود.


ابزار صفحه