Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۹:سوال ۲۶

سوال ۲۶

یک جدول 1×10 شامل اعداد ۱ تا ۱۰ است و از هر عدد دقیقا یک بار در جدول آمده است. در هر مرحله عدد i بین ۱ تا ۱۰ را انتخاب می‌کنیم و اگر محتوای خانه‌ی iام جدول برابر (ji)j بود٬ محتوای دو خانه‌ی iام و jام را عوض می‌کنیم. کدام یک از گزینه‌های زیر صحیح است؟

  1. تعداد تعویض‌ها می‌تواند بی‌نهایت باشد.
  2. تعداد تعویض‌ها حداکثر ۱۰ است.
  3. تعداد تعویض‌ها حداکثر ۴۵ است.
  4. تعداد تعویض‌ها حداکثر ۹ است.
  5. تعداد تعویض‌ها حداکثر ۲۰ است.

پاسخ

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

در هر مرحله تعویض٬ عدد i در خانه‌ی i قرار می‌گیرد یعنی در هر مرحله تعویض حداقل یک عنصر در جای خود قرار می‌گیرد بنابراین حداکثر ۹ تعویض لازم است( لازم به ذکر است که اگر دقیقا ۹ عدد در جایگاه خود باشند عدد دهم نیز به ناچار در جایگاه خود خواهد بود).


ابزار صفحه