المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

علی می‌خواهد تعدادی عدد از چپ به راست بنویسد که با ۱ شروع و با ۲۰ تمام شود و شامل اعداد ۵ یا ۱۰ نباشد. هم‌چنین به جز ٬۱ هر عدد یا یکی بیشتر از عدد قبلی خود (عددی که درست سمت چپ آن نوشته شده) باشد٬ یا دو برابر آن. او به چند روش مختلف می‌تواند این کار را انجام دهد؟

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

پاسخ

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

برای به‌دست آوردن تعداد حالات رسید ن به هر عدد کافیست مقدار حالات قبل از آن را بدانیم. درواقع برای رسیدن به عدد $k$ یااز $k-1$ و یااز $\frac{k}{2}$ (درصورت زوج بودن$k$) استفاده کرده‌ایم و تعداد حالات رسیدن به ۵ و۱۰ نیز صفر است. پس جدول تعداد حالات رسیدن به اعداد به‌صورت زیر است:


ابزار صفحه