Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۲

افراد با شماره‌های ۱ تا ۶ به ترتیب دور میز دایره‌ای شکل و در جهت ساعت‌گرد نشسته‌اند و هریک ورقه‌ای دارند که بر روی آن یک عدد نوشته شده است (عدد فرد شماره‌ي i را A[i] می‌نامیم). الگوریتم زیر را ۱۳۸۸ مرحله تکرار می‌کنیم:

۱) هر فرد با شماره‌ی فرد ورقه‌اش را با نفر کناری‌اش (در جهت ساعت‌گرد) مقایسه می‌کند. خود عدد کوچک‌تر و نفر کناری‌اش عدد بزرگ‌تر را برمی‌دارد.

۲) هر فرد با شماره‌ی زوج ورقه‌اش را با نفر کناری‌اش (در جهت ساعت‌گرد) مقایسه می‌کند. خود عدد کوچک‌تر و نفر کناری‌اش عدد بزرگ‌تر را برمی‌دارد.

اگر A[1..6]=2,4,5,6,8,9 باشد٬ بعد از اجرای ۱ مرحله A[1..6]=9,5,4,8,6,2 خواهد بود. بعد از اجرای ۱۳۸۸ مرحله ورقه‌ای که عدد ۲ روی آن نوشته شده است در دست کدام فرد خواهد بود؟

  1. شماره‌ی ۱
  2. شماره‌ی ۲
  3. شماره‌ی ۴
  4. شماره‌ی ۵
  5. شماره‌ی ۶

پاسخ

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

می‌دانیم عدد ۲ کوچک‌ترین عدد در بین اعداد است، در نتیجه همواره عنصر کوچک‌تر است. بدین ترتیب از مرحله‌ی اول به بعد همواره در جایگاه‌های زوج باقی خواهد ماند و همواره دو خانه نسبت به قبل عقب‌تر خواهد رفت. در مرحله‌ی اول در خانه‌ی ششم قرار دارد و باتوجه به اینکه ۱۳۸۸ باقی‌مانده‌اش بر ۳ برابر با ۲ است در آخرین مرحله در خانه‌ی چهارم قرار می‌گیرد (هر سه مرحله به جایگاه قبلیش برمی‌گردد).


ابزار صفحه