خروجی الگوریتم

عمل $\oplus$ به صورت زیر تعریف می‌شود:

فرض کنید که نمایش عددهای $x$ و $Y$ در مبنای دو به صورت $x=x_nx_{n-1}…x_1x_0$ و $y=y_ny_{n-1}…y_1y_0$ باشد. (در صورت لزوم در سمت چپ نمایش دودویی عدد کوچک‌تر به تعداد مورد نظر صفر اضافه می‌کنیم.) برای هر $(0\leq i \leq n)i$، در صورتی که دقیقا یکی از دو عدد $x_i$ و $y_i$ برابر با یک و دیگری صفر باشد، $a_i$ را مساوی با یک و در غیر این صورت مساوی با صفر تعریف می‌کنیم. عددی که نمایش آن در مبنای دو به صورت $a_na_{n-1}…a_1a_0$ است برابر با $x\oplus y$ خواهد بود. حال الگوریتم زیر را در نظر بگیرید:

1) $a_0$ را مساوی با ۱ و $k$ را مساوی با ۱ قرار بده.

2) $a_k$ را مساوی با $a_{k-1}$ قرار بده.

3) به مقدار $a_k$ یکی اضافه کن.

4) $F$ را برابر با ۱ قرار بده.

5) برای هر $i$ از صفر تا $(0\leq i <k)k-1$ این کار را انجام بده:

1-5) برای هر $j$ از صفر تا $(0\leq j <k)k-1$ این کار را انجام بده:

1-1-5) در صورتی که $a_k=a_i\oplus a_j$ است، $F$ را مساوی با ۰ قرار بده.

6) اگر $F=1$ است، به مقدار $k$ یکی اضافه کن و در غیر این صورت به مرحله‌ی ۳ برو.

7) اگر $k\leq 1376$ است، به مرحله‌ی (۲) برو و در غیر این صورت متوقف شو.

مقدار $a_{1376}$ در انتهای این الگوریتم چند است؟ برای ادعای خود دلیل بیاورید.

• سوال بعد
• سوال قبل