المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۲

پدر مسعود به او برنامه‌ي زیر را داده است. مسعود مجاز است به عنوان ورودی به این برنامه دو عدد طبیعی $\underline{کوچکتر از ۳۲}$ بدهد.

  1. اعداد $a$ و $b$ را از ورودی دریافت کن.
  2. متغیر $i$ را برابر با ۱ و متغیر $s$ را برابر با ۰ قرار بده.
  3. اگر باقیمانده‌ي تقسیم $a$ بر ۲ با باقیمانده‌ي تقسیم $b$ بر ۲ متفاوت بود٬ به $s$ به اندازه‌ي $i$ واحد اضافه کن.
  4. $i$ را یک واحد افزایش بده.
  5. $a$ را برابر خارج قسمت تقسیم خودش بر ۲ و $b$ را برابر خارج قسمت تقسیم خودش بر ۲ قرار بده.
  6. اگر حداقل یکی از $a$ یا $b$ بزرگتر از ۰ بود به خط ۳ برو.
  7. اگر $s$ برابر با ۳ بود به اندازه‌ي حاصل ضرب مقادیر اولیه‌ی ورودی $a$ و $b$ به حسام شکلات بده.
  8. پایان

هدف مسعود این است که اعدادی را به عنوان ورودی به این برنامه بدهد که حداکثر تعداد شکلات را بگیرد! برای مثال اگر مسعود اعداد ۲۳ و ۱۹ را به این برنامه بدهد در پایان ۴۳۷ شکلات می گیرد. اما اگر اعداد ۱۴ و ۱۷ را به عنوان ورودی به برنامه بدهد هیچ شکلاتی نمی گیرد. حداکثر تعداد شکلاتی که مسعود می تواند از این برنامه بگیرد چند تاست؟

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

پاسخ

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

در این گونه سوالات الگوریتمی سعی می‌کنیم با نوشتن متغیر های الگوریتم و اجرا کردن الگوریتم روی آن‌ها بفهمیم که الگوریتم دقیقا چه کاری انجام می‌دهد. با کمی بررسی می‌فهمیم که بهتر است اعداد را در مبنای دو بررسی کنیم! این الگوریتم این کار را می‌کند:

عدد $a$ و $b$ را می‌گیرد و اگر رقم $i$ ام این اعداد در مبنای دو با هم متفاوت بود به $s$، $i$ واحد اضافه می‌کند.

پس برای اینکه $s$، 3 شود، باید تنها دو رقم سمت راست این دو عدد در مبنای دو با هم متفاوت باشد و از آ‌‌ن‌جا که می‌خواهیم ضربشان ماکسیمم شود پس سایر رقم هارا 1 در نظر می‌گیریم. پس می‌شود $29 \times 30 = 870$


ابزار صفحه