Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291350
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится двоичная запись числа $N$.
- К этой записи дописываются справа ещё несколько разрядов по следующему правилу:
- если $N$ чётное, то к нему справа приписываются два нуля, а слева единица;
- если $N$ нечётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи.
- Результат переводится в десятичную систему и выводится на экран.
Например, исходное число $4_{10}=100_2$ преобразуется в число $110000_2=48_{10}$, а исходное число $13_{10}=1101_2$ преобразуется в число $110111_2=55_{10}$.
Укажите наименьшее число $R$, превышающее $205$, которое может быть результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.
Возьмём чётное число $N=20$: $20_{10}=10100_2$.
Справа дописываем два нуля, а слева — единицу:
$10100\rightarrow11010000_2$.
$11010000_2=208_{10}$.
Проверим, могут ли быть получены числа $206$ или $207$.
Если $N$ чётное, запись результата заканчивается двумя нулями. Числа $206_{10}=11001110_2$; $207_{10}=11001111_2$ двумя нулями не заканчиваются.
Если $N$ нечётное, в конец его записи дописывается двоичная запись количества единиц.
Для числа $206$ возможные окончания дают противоречия:
- окончание $10_2=2$, но в оставшейся части $110011$ содержится $4$ единицы;
- окончание $110_2=6$, но в оставшейся части $11001$ содержится $3$ единицы.
Для числа $207$:
- окончание $1_2=1$, но в оставшейся части $1100111$ содержится $5$ единиц;
- окончание $11_2=3$, но в оставшейся части $110011$ содержится $4$ единицы;
- окончание $111_2=7$, но в оставшейся части $11001$ содержится $3$ единицы.
Следовательно, числа $206$ и $207$ получить нельзя, а число $208$ получить можно.
20
