====== سوال ۲۳ ======

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

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

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

  - ۱۴ 
  - ۱۵ 
  - ۱۶
  - ۱۷ 
  - ۱۸


<راهنمایی>
چگونه می‌توان یک عدد دلخواه را با اعمال تعریف شده ساخت؟
</راهنمایی>


<راهنمایی>
ساختار دودویی اعداد را در نظر بگیرید. در هر مرحله، چه تغییری در ساختار دودویی هر عدد ایجاد می‌شود؟
</راهنمایی>

<راهنمایی>
ساختار دودویی اعداد را طوری تغییر دهید که تعداد ارقام همه‌ی اعداد در ساختار دودویی یکسانی باشد. سپس در هر مرحله سعی کنید رقم یکسانی از اعداد را مشخص کنید.
</راهنمایی>
<راهنمایی>
برای اثبات بهینگی روش خود، حداقل تعداد عمل‌های ضرب در دو و حداقل تعداد عمل‌های افزودن یک را محاسبه کنید.
</راهنمایی>
<راهنمایی>
انجام دادن کدام عمل‌ها کاملا از هم مستقل هستند؟
</راهنمایی>

<پاسخ>

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

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