المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۳

دنباله‌ی $\left< 0,0,0,0,0,0 \right>$ بر روی کاغذ نوشته شده است. در هر مرحله می‌توان یکی از تغییرات زیر را روی دنباله اعمال کرد:

  • تمامی اعداد داخل لیست در دو ضرب می‌شوند.
  • یکی از اعداد دنباله انتخاب و به‌علاوه‌ی یک می‌شود.

کم‌ترین تعداد مرحله برای رسیدن به دنباله‌ی $\left< 7,11,5,1,3,8 \right>$ چند است؟

  1. ۱۴
  2. ۱۵
  3. ۱۶
  4. ۱۷
  5. ۱۸

پاسخ

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

کم‌ترین مرحله برابر است با مجموع تعداد بیت‌های ۱ در نمایش دودویی اعداد دنباله به علاوه‌ی بزرگ‌ترین xای که بزرگ‌ترین عدد دنباله از $2^{x}$ بزرگ‌تر مساوی است. روش ساخت هم این‌گونه است که در مرحله‌ی اول اعداد که بیت‌ x-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم، در مرحله دوم اعدادی که بیت x-1-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم. به همین ترتیب این کار را x بار انجام می‌دهیم. در آخر نیز اعدادی که بیت ۰-ام آن‌ها یک است، به‌علاوه‌ی یک می‌شوند. دقت کنید که بعد از آخرین مرحله‌ی اضافه کردن دیگر اعداد را در دو ضرب نمی‌کنیم.


ابزار صفحه