سوال ۳۹

آرایه‌ی ۶تایی $A$ به ترتیب با عددهای ۱ تا ۶ پر شده است. پس از اجرای الگوریتم زیر عدد ۶ در کدام خانه خواهد بود؟

به ازای $i$ از ۱ تا ۱۳۵۷ کارهای زیر را انجام بده:
- به ازای $j$ از ۱ تا ۳ این کار را انجام بده:
  - اگر $A[j]$ از $A[j+3]$ بزرگ‌تر است٬ جایشان را عوض کن.
- به ازای $j$ از ۱ تا ۵ این کار را انجام بده:
  - اگر $A[j]$ از $A[j+1]$ کوچک‌تر است٬ جایشان را عوض کن.

پاسخ

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

خروجی برنامه‌ بعد از مرحله ۱.۱.۱ و خروجی نهایی برای $i=1,2,3,4,5,6$ در جدول زیر آمده است:

همان‌طور که مشاهده می‌شود خروجی برنامه به ازای $i=2$ و $i=5$ با یک‌دیگر و همچنین خروجی برنامه به ازای $i=3$ و $i=6$ نیز با یک‌دیگر برابر می‌شوند.یعنی خروجی برنامه برای $(k\geq2)i=3k$ همان خروجی برنامه به ازای $i=3$ و خروجی برنامه‌ برای $(k\geq2)i=3k+1$ همان خروجی برنامه به ازای $i=4$ و بالاخره خروجی برنامه برای $(k\geq2)i=3k+2$ همان خروجی برنامه به ازای $i=2$ می‌باشد و چون $1375=3k+1$ پس خروجی برنامه به ازای $i=1375$ همان خروجی برنامه به ازای $i=4$ می‌باشد٬ فلذا عدد ۶ در خانه‌ی پنجم قرار دارد.