======سوال ۷======

الگوریتم زیر را در نظر بگیرید:

  * عدد $x$ را از ورودی بگیر.
  * عدد $a$ را برابر صفر قرار بده.
  * تا زمانی که عدد $x$ بزرگ‌تر از صفر است٬‌ کارهای زیر را انجام بده:
    * باقی‌مانده‌ی تقسیم $x$ بر ۲ را در $k$ بریز.
    * اگر $k$ برابر صفر است٬ به مقدار $a$ یک واحد اضافه کن. 
    * $x$ را برابر خارج‌قسمت تقسیم خودش بر ۲ قرار بده.
  * مقدار $a$ را به عنوان خروجی الگوریتم برگردان.

برای مثال٬ اگر به این الگوریتم عدد ۹ را بدهیم خروجی مقدار ۲ را برمی‌گرداند. اکنون فرض کنید اعداد ۱ تا ۱۳۸۸ را یکی‌ یکی به این الگوریتم می‌دهیم و هربار خروجی الگوریتم را یادداشت می‌کنیم. بزرگ‌ترین عددی که یادداشت می‌کنیم٬ چند است؟

  - ۹
  - ۱۰
  - ۱۱
  - ۲۰
  - ۶۹۴

<پاسخ>
گزینه (۲) درست است.


اگر عدد $x$ را در مبنای دو در نظر بگیریم گام‌های اول و دوم داخل حلقه باعث می‌شوند که اگر کم‌ارزش‌ترین رقم عدد $x$ صفر بود یکی به $a$ اضافه شود و گام سوم باعث می‌شود که رقم کم‌ارزش عدد در مبنای دو حذف شود. این سیکل در انتها تعداد رقم‌های صفر عدد را به عنوان خروجی می‌دهد. از بین اعداد ۱ تا $1388$ عدد $2^{10}$ بیش‌ترین تعداد یعنی ۱۰ صفر در مبنای دو دارد.

</پاسخ>
  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]