سوال ۲۳
دنباله‌ی $\left< 0,0,0,0,0,0 \right>$ بر روی کاغذ نوشته شده است. در هر مرحله می‌توان یکی از تغییرات زیر را روی دنباله اعمال کرد:
- تمامی اعداد داخل لیست در دو ضرب می‌شوند.
- یکی از اعداد دنباله انتخاب و به‌علاوه‌ی یک می‌شود.
کم‌ترین تعداد مرحله برای رسیدن به دنباله‌ی $\left< 7,11,5,1,3,8 \right>$ چند است؟
- ۱۴
- ۱۵
- ۱۶
- ۱۷
- ۱۸
پاسخ
گزینه‌ی ۲ درست است.
کم‌ترین مرحله برابر است با مجموع تعداد بیت‌های ۱ در نمایش دودویی اعداد دنباله به علاوه‌ی بزرگ‌ترین xای که بزرگ‌ترین عدد دنباله از $2^{x}$ بزرگ‌تر مساوی است. روش ساخت هم این‌گونه است که در مرحله‌ی اول اعداد که بیت x-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم، در مرحله دوم اعدادی که بیت x-1-ام آن‌ها یک است را به‌علاوه‌ی یک می‌کنیم و سپس کل اعداد را در دو ضرب می‌کنیم. به همین ترتیب این کار را x بار انجام می‌دهیم. در آخر نیز اعدادی که بیت ۰-ام آن‌ها یک است، به‌علاوه‌ی یک می‌شوند. دقت کنید که بعد از آخرین مرحله‌ی اضافه کردن دیگر اعداد را در دو ضرب نمی‌کنیم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
