Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۱۷

سوال ۱۷

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

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

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

  1. 1,2,3,4,5,6,7,8
  2. 1,2,4,3,5,6,7,8
  3. 1,2,3,4,5,7,6,8
  4. 2,1,3,4,5,6,7,8
  5. 8,6,3,4,6,1,2,7

پاسخ

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

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


ابزار صفحه