Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۵:سوال ۱۶

سؤال ۱۶

جای‌گشت n عضوی <a1,a2,...,an> از اعداد ۱ تا n را در نظر بگیرید. برنامه‌ی زیر این دنباله را مرتب می‌کند:

  • دستورهای زیر را برای هر یک از مقادیر i از ۱ تا n تکرار کن:
    • تا وقتی‌که ai برابر i نیست، مقدار خانه‌ی i را با مقدار خانه‌ی ai تعویض کن.

مثلاً اگر ورودی <۴، ۱، ۳، ۲، ۵> باشد،

حداکثر تعداد تعویض‌ها برای تمام جای‌گشت‌های ۲۰۰۵ عضوی را در نظر بگیرید. باقی‌مانده‌ی این عدد بر ۵ چند است؟

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

پاسخ

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

معلوم است که در هر تعویضی حداقل یک عدد در جای خود قرار می‌گیرد و با توجه به این که در تعویض آخر دو عدد در جای خود قرار می‌گیرند٬ بنابراین تعداد تعویض‌ها حداکثر ۲۰۰۴ خواهدشد.

برای جای‌گشت زیر تعداد تعویض‌ها برابر ۲۰۰۴ خواهد شد.

2005,1,2,3,4,...,2003,2004


ابزار صفحه