المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۸:سوال ۴۹

سوال ۴۹

یک ترتیب از عددهای ‎۱‎ تا ‎۱۰‎ به ما داده شده است. دو عمل زیر را می‌توانیم بر روی هر ترتیب انجام دهیم:

  • عنصر اول و دوم ترتیب را جابه‌جا کنیم.
  • عنصر اول ترتیب را برداشته، آن را در آخر ترتیب قرار دهیم.

آیا با استفاده از دو عمل فوق، می‌توانیم ترتیب داده شده را مرتب کنیم؟

پاسخ

با الگوریتم زیر می‌توان جای هر دو عضو دلخواه مانند $i$ و $j$ با فرض این که $i$ قبل از $j$ باشد راعوض کرد:

  • ابتدا با توجه به عمل دوم تمام اعضای قبل از $i$ را به انتهای دنباله به ترتیب انتقال می‌دهیم.
  • با توجه به عمل اول جای $i$ و عضو بعد از آن را عوض کرده و سپس باتوجه به عمل دوم آن‌ ‌را به انتهای دنباله انتقال می‌دهیم و این کار را تا جایی ادامه می‌دهیم که $i$ و $j$ مجاور باشند٬ در این مرحله خود $i$ را به انتها منتقل می‌کنیم.
  • باتوجه به عمل اول جای $j$ و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن‌ را به انتهای دنباله انتقال می‌دهیم و کار را تا جایی ادامه می‌دهیم که جای خالی $i$ و $j$ پر شود.
  • باتوجه به عمل دوم تا جای ممکن اعضا را به انتها انتقال می‌دهیم تا ترتیب اولی ظاهر شود با این تفاوت که جای $i$ و $j$ عوض شده باشد.

با الگوریتم بالا ابتدا ۱ را به ابتدا٬ سپس ۲ را به جایگاه دوم و … انتقال می‌دهیم.


ابزار صفحه