Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291353
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится двоичная запись числа $N$.
- К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
- если $N$ чётное, то к нему справа приписываются два нуля, а слева единица;
- если $N$ нечётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи.
- Результат переводится в десятичную систему и выводится на экран.
Например, исходное число $4_{10}=100_2$ преобразуется в число $110000_2=48_{10}$, а исходное число $13_{10}=1101_2$ преобразуется в число $110111_2=55_{10}$.
Укажите такое число $N$, для которого число $R$ является наименьшим среди чисел, превышающих $190$. В ответе это число запишите в десятичной системе счисления.
Рассмотрим чётное число $N=16$: $16_{10}=10000_2$.
Справа приписываем два нуля, а слева единицу:
$10000\rightarrow11000000_2$.
$11000000_2=192_{10}$.
Это число превышает $190$. Меньшим возможным результатом могло бы быть только число $191$.
Проверим число $191$: $191_{10}=10111111_2$.
При чётном $N$ результат заканчивается двумя нулями, поэтому число $191$ получить нельзя.
При нечётном $N$ справа приписывается двоичная запись количества единиц в записи $N$:
- если приписана цифра $1$, то запись $N$ равна $1011111_2$ и содержит $6$ единиц, а не $1$;
- если приписано $11_2=3$, то запись $N$ равна $101111_2$ и содержит $5$ единиц, а не $3$;
- если приписано $111_2=7$, то запись $N$ равна $10111_2$ и содержит $4$ единицы, а не $7$.
Следовательно, число $191$ получить нельзя, а наименьшее значение $R>190$ равно $192$ и получается при $N=16$.
20
