سوال ۱۸
عملگر $\&$ دو عدد در مبنای دو را به عنوان ورودی دریافت میکند و یک عدد به عنوان خروجی تولید میکند. هر رقمِ خروجی، فقط زمانی برابر با ۱ میشود که آن رقم در هر دو عدد ورودی برابر ۱ باشد. برای مثال: $$ 6=(110)_2,\ 3=(011)_2 \;\Longrightarrow\; 6 \mathbin{\&} 3 = (010)_2 = 2 $$ دستگاهی داریم که برای هر عدد طبیعی ورودی $i$، الگوریتم زیر را اجرا میکند:
- متغیر $j$ برابر ۰ قرار داده میشود.
- متغیر
ansبرابر ۰ قرار داده میشود. - اگر مقدار $i \mathbin{\&} j$ برابر $j$ باشد، مقدار
ansیک واحد افزایش مییابد. - اگر مقدار $i$ و $j$ برابر باشد، مقدار
ansیادداشت میشود و الگوریتم خاتمه مییابد. - مقدار $j$ یک واحد افزایش مییابد و الگوریتم به مرحلهی ۳ بازمیگردد.
برای مثال، اگر عدد ۲ را به دستگاه ورودی بدهیم، الگوریتم با یادداشت عدد ۲ خاتمه مییابد. اگر اعداد $1,2,\ldots,63$ را به ترتیب به دستگاه ورودی بدهیم، مجموع اعداد یادداشت شده چقدر خواهد بود؟
- ۱۵۳۸
- ۵۵۲
- ۱۰۲۴
- ۷۲۸
- ۶۸۰
پاسخ
گزینهی ۴ درست است.
پاسخ مسئله برابر است با تعداد زوج مرتبهای $i$ و $j$ به طوری که مجموعهی رقمهای ۱ عدد $j$ زیرمجموعهی مجموعهی رقمهای ۱ عدد $i$ باشد. فرض کنید میخواهیم $i$ و $j$ را مشخص کنیم. به ازای هر $k$، سه حالت مجاز برای رقم $k$ام اعداد $i$ و $j$ وجود دارد:
- هر دو ۱ باشند.
- هر دو ۰ باشند.
- رقم $k$ام $i$ برابر ۱ و رقم $k$ام $j$ برابر ۰ باشد.
همچنین هر کدام از $i$ و $j$ در مبنای ۲ حداکثر ۶ رقم دارند (اعداد کوچکتر از $2^6 = 64$ حداکثر ۶ رقمیاند.) اما میدانیم $i$ عددی طبیعی است و لذا زوج مرتب ($j = 0$ ،$i = 0$) معتبر نیست. در نتیجه، در مجموع تعداد زوج مرتبهای معتبر برای $i$ و $j$ برابر است با: ${3 ^ 6 - 1 = 728}$
| < سوال قبل | سوال بعد > |