سوال ۱۲
پدر مسعود به او برنامهی زیر را داده است. مسعود مجاز است به عنوان ورودی به این برنامه دو عدد طبیعی $\underline{کوچکتر از ۳۲}$ بدهد.
- اعداد $a$ و $b$ را از ورودی دریافت کن.
- متغیر $i$ را برابر با ۱ و متغیر $s$ را برابر با ۰ قرار بده.
- اگر باقیماندهی تقسیم $a$ بر ۲ با باقیماندهی تقسیم $b$ بر ۲ متفاوت بود٬ به $s$ به اندازهی $i$ واحد اضافه کن.
- $i$ را یک واحد افزایش بده.
- $a$ را برابر خارج قسمت تقسیم خودش بر ۲ و $b$ را برابر خارج قسمت تقسیم خودش بر ۲ قرار بده.
- اگر حداقل یکی از $a$ یا $b$ بزرگتر از ۰ بود به خط ۳ برو.
- اگر $s$ برابر با ۳ بود به اندازهی حاصل ضرب مقادیر اولیهی ورودی $a$ و $b$ به حسام شکلات بده.
- پایان
هدف مسعود این است که اعدادی را به عنوان ورودی به این برنامه بدهد که حداکثر تعداد شکلات را بگیرد! برای مثال اگر مسعود اعداد ۲۳ و ۱۹ را به این برنامه بدهد در پایان ۴۳۷ شکلات میگیرد. اما اگر اعداد ۱۴ و ۱۷ را به عنوان ورودی به برنامه بدهد هیچ شکلاتی نمی گیرد. حداکثر تعداد شکلاتی که مسعود میتواند از این برنامه بگیرد چند تاست؟
- ۸۱۰
- ۹۲۸
- ۸۳۷
- ۸۶۸
- ۸۷۰
پاسخ
گزینهی «۵» درست است.
در این گونه سوالات الگوریتمی سعی میکنیم با نوشتن متغیرهای الگوریتم و اجرا کردن الگوریتم روی آنها بفهمیم که الگوریتم دقیقا چه کاری انجام میدهد. با کمی بررسی میفهمیم که بهتر است اعداد را در مبنای دو بررسی کنیم! این الگوریتم این کار را میکند:
عدد $a$ و $b$ را میگیرد و اگر رقم $i$ ام این اعداد در مبنای دو با هم متفاوت بود به $s$، $i$ واحد اضافه میکند.
پس برای اینکه $s$، 3 شود، باید تنها دو رقم سمت راست این دو عدد در مبنای دو با هم متفاوت باشد و از آنجا که میخواهیم ضربشان ماکسیمم شود پس سایر رقم هارا 1 در نظر میگیریم. پس میشود $29 \times 30 = 870$
▸ سوال قبل | سوال بعد ◂ |