سوال ۲۶

الگوریتم زیر را در نظر بگیرید. در این الگوریتم $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$ خواهیم داشت:

$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$

غلط بودن گزینه‌های ۴٬۱ و ۵ واضح است. برای به دست آوردن $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$ (در مبنای ۲ به صورت ۱۰۰۰) جمع کنیم فقط رقم آخر از سمت چپ آنان از صفر به ۱ تغییر خواهند یافت…