المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

در سوال قبل به ازای هر جایگشت مطلوب، کمینه‌ی تعداد مراحل لازم برای رسیدن به جایگشت مرتب‌ شده (از کوچک به بزرگ) را در نظر بگیرید. در میان این مقادیر، بیشینه چیست؟

  1. ۲
  2. ۳
  3. ۸
  4. ۱
  5. ۴

پاسخ

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

ترتیب دوری هر جایگشت مطلوب، مرتّب شده یا وارون آن است (طبق سوال قبل). اگر جایگشت مرتّب شده بود، ابتدا با یک حرکت ترتیب آن را وارون می‌کنیم. حال با یک حرکت می‌توانیم نقطه‌ی شروع جایگشت را برابر ۱ کنیم و جایگشت مرتّب می‌شود.


ابزار صفحه