المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

برای مرتب‌سازی، عمل «ابرجابه‌جایی» را چنین تعریف می‌کنیم. در هر ابرجابه‌جایی، یک زیررشته‌ی دلخواه از دنباله‌ی داده‌شده را معکوس می‌کنیم. برای مثال دنباله‌ی $\left< 1,4,3,2,5\right>$ با یک ابرجابه‌جایی مرتب می‌‌شود. کافی است زیررشته‌‌ی $\left<4,3,2\right>$ را معکوس کنیم. ولی برای مرتب‌سازی دنباله‌ی $\left<4,2,3,1\right>$ دو ابرجابه‌جایی نیاز داریم. ابتدا کل دنباله را معکوس می‌کنیم تا به $\left<1,3,2,4\right>$ برسیم. سپس زیررشته‌ی $\left<3,2\right>$ را معکوس می‌کنیم. حداقل تعداد ابرجابه‌جایی که برای مرتب‌سازی هر دنباله‌ی دلخواه به طول ۴ کافی است، چند است؟

  1. ۲
  2. ۳
  3. ۴
  4. ۵
  5. در برخی حالات مرتب‌سازی با ابرجابه‌جایی ممکن نیست.

پاسخ

گزینه‌ی ۲ درست است.

با حالت‌گیری و رسیدن به دنباله‌ی $\left<3,1,4,2\right>$ جواب به دست می‌آید.


ابزار صفحه