سوال ۱۷

آرایه‌ی $A[1..8]$ داده شده است. بر روی آن الگوریتم زیر را اجرا می‌کنیم:

  1. در ابتدا $i$ را برابر ۱ قرار بده و به خط ۲ برو
  2. اگر $A[i]=i$ به خط ۴ برو و اگر $ A[i]\neq i$ به خط ۳ برو
  3. $A[i]$ را با $A[A[i]]$ تعویض کن و به خط ۲ برو
  4. $i$ را یک واحد افزایش بده و اگر $i$ کوچکتر یا مساوی ۸ است به خط ۲ برو. اگر $i$ بزرگتر از ۸ است به خط ۵ برو.
  5. آرایه‌ی $A$ را چاپ کن

اگر $A[1..8] = \langle 8,5,3,4,6,1,2,7 \rangle$ باشد٬ خروجی این الگوریتم چیست؟

  1. $\langle 1, 2, 3, 4, 5, 6, 7, 8 \rangle$
  2. $\langle 1, 2, 4, 3, 5, 6, 7, 8 \rangle$
  3. $\langle 1, 2, 3, 4, 5, 7, 6, 8 \rangle$
  4. $\langle 2, 1, 3, 4, 5, 6, 7, 8 \rangle$
  5. $\langle 8, 6, 3, 4, 6, 1, 2, 7 \rangle$

پاسخ

گزینه (۱) درست است.

این الگوریتم تا زمانی که $A[i]$ برابر $i$ نشده است تمام اعضای آرایه را در گام‌های اول تا سوم به صورت دوری (به دلیل متفاوت بودن همه اعداد با شماره‌ی خانه‌هایشان) بر روی $A[i]$ قرار می‌دهد تا برابر $i$ شود و در گام‌های چهارم و پنجم به سراغ خانه‌ی بعدی می‌رود و همین کار را تکرار می‌کند تا به آخرین خانه برسد و سپس آرایه را چاپ می‌کند که باعث می‌شود به ازای هر $1≤i≤8$ تساوی $A[i]=i$ برقرار شود. بنابرین آرایه به صورت $〈1,2,…,8〉$ مرتب شده می‌باشد.