Решение: Минимальное значение результата алгоритма
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
1. Строится двоичная запись числа $N$.
2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
а) если $N$ чётное, то к нему справа приписываются два нуля, а слева единица;
б) если $N$ нечётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи.
Полученная таким образом запись является двоичной записью искомого числа $R$.
Например, исходное число $4_{10}=100_2$ преобразуется в число $110000_2=48_{10}$, а исходное число $13_{10}=1101_2$ преобразуется в число $110111_2=55_{10}$.
Укажите наименьшее число $R$, превышающее $205$, которое может быть результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение по шагам
6 шаговДля чётного числа $N$ к двоичной записи слева приписывается единица, а справа — два нуля. Если длина записи $N$ равна $k$, то
$$R=2^{k+2}+4N$$При $k=4$ максимальное значение чётного $N$ равно $14$, поэтому максимальный результат равен $2^6+4\cdot14=120$, что недостаточно.
При $k=5$ имеем $16\leq N\leq30$. Требование $R>205$ даёт $128+4N>205$, то есть $N>19{,}25$. Наименьшее подходящее чётное число — $N=20$.
Двоичная запись числа $20$ имеет вид $10100_2$. После преобразования получаем $11010000_2$.
Переводим результат в десятичную систему:
$$11010000_2=128+64+16=208$$Для нечётных $N$ ближайшие возможные результаты, превышающие $205$, не дают значения меньше $208$, поэтому найденный результат является минимальным.
Где здесь ошибаются
Приписывают единицу справа вместо слева для чётного числа.
Забывают, что два нуля справа означают умножение на $4$.
Сравнивают двоичную запись с $205$, не переводя результат в десятичную систему.