====== سوال ۲۶ ======

الگوریتم زیر را در نظر بگیرید. در این الگوریتم $n$ یک عدد طبیعی و $A$ یک آرایه است که عنصر $i$ام آن را با $A[i]$ نشان می‌دهیم.

  * $A[1]$ را مساوی با صفر و $A[2]$ را مساوی یک قرار بده.
  * برای هر $i$ از ۲ تا $n$ کار زیر را انجام بده:
      * برای هر $j$ از $2^{i-1}+1$ کار زیر را انجام بده:
      * $A[i]$ را مساوی با $[2^i-j+1]+2^{i-1}$ قرار بده.

کدام یک از گزاره‌های زیر در مورد مقدار آرایه‌ی $A$ پس از اجرای این الگوریتم٬ درست است؟

  - دنباله‌ی اعدد صفر تا $2^n-1$ به ترتیب صعودی در $A$ قرار دارد.
  - هر دو عدد متوالی از آرایه‌ی $A$ در مبنای ۲ دقیقا در یک رقم متفاوت هستند.
  - آرایه‌ی $A$ شامل عناصر تکراری است.
  - عناصر اول تا $2^{n-1}$ام آرایه $A$ به ترتیب صعودی و بقیه عناصر به ترتیب نزولی هستند.
  - گزینه‌های ۳ و ۴ درست‌اند.
<پاسخ>
گزینه (۲) درست است.

به ازای $j=1,2,...,16$ خواهیم داشت:

<WRAP :en>

$A(1)=0 \quad\quad\quad\quad\quad\quad\quad\quad A(2)=1 \quad\quad\quad\quad\quad\quad\quad\quad A(3)=3 \\ A(4)=2 \quad\quad\quad\quad\quad\quad\quad\quad A(5)=6 \quad\quad\quad\quad\quad\quad\quad\quad A(6)=7 \\ A(7)=5 \quad\quad\quad\quad\quad\quad\quad\quad A(8)=4 \quad\quad\quad\quad\quad\quad\quad\quad A(9)=12 \\ A(10)=13 \quad\quad\quad\quad\quad\quad\quad A(11)=15 \quad\quad\quad\quad\quad\quad\quad A(12)=14 \\ A(13)=10 \quad\quad\quad\quad\quad\quad\quad A(14)=11 \quad\quad\quad\quad\quad\quad\quad\quad A(15)=9 \\ A(16)=8$
</WRAP>

غلط بودن گزینه‌های ۴٬۱ و ۵ واضح است. برای به دست آوردن $A(2^n+1)$ تا $A(2^{n+1})$ باید مقادیر $A(2^n)$ تا $A(1)$ را (نه به ترتیب) با مقدار ثابت $2^n$ جمع کرد. پس اگر $A(2^n)$ تا $A(1)$ عضو تکراری نداشته باشد به استقرا معلوم می‌شود که  $A(2^n+1)$ تا $A(2^{n+1})$ نیز عضو تکراری نخواهد داشت٬ ضمن اینکه به عنوان مثال از $A(1)$ تا $A(8)$  عضو تکراری وجود ندارد(پایه‌ی استقرا). پس گزینه‌ی ۳ نیز غلط می‌باشد.

و اما گزینه‌ی ۲ صحیح است. استدلال٬ مشابه استدلال فوق است چون هر دو عدد متوالی از $A(1)$ تا $A(8)$ در مبنای ۲ دقیقا در یک رقم متفاوت هستند پس اگر آنان را با  $2^3$ (در مبنای ۲ به صورت ۱۰۰۰) جمع کنیم فقط رقم آخر از سمت چپ آنان از صفر به ۱ تغییر خواهند یافت...
</پاسخ>
  * [[سوال ۲۷|سوال بعد]]
  * [[سوال ۲۵|سوال قبل]]