5. Автомат обрабатывает натуральное число N N по следующему алгоритму. 1. Строится двоичная запись числа N N . 2. Складываются все цифры полученной двоичной записи. В конец записи…
5. Автомат обрабатывает натуральное число N N по следующему алгоритму. 1. Строится двоичная запись числа N N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2. 3. Предыдущий пункт повторяется для записи с добавленной цифрой. 4. Результат переводится в десятичную систему и выводится на экран. Пример. Дано число N N = = 14. Алгоритм работает следующим образом. 1. Двоичная запись числа N N: 1110. 2. Сумма цифр двоичной записи — 3; остаток от деления на 2 равен 1; новая запись 11101. 3. Сумма цифр полученной записи — 4; остаток от деления на 2 равен 0; новая запись 111010. 4. На экран выводится число 57. Укажи наименьшее число, большее 41, которое может появиться на экране в результате работы автомата.
Ответ: 46.
Пусть в двоичной записи числа \(N\) содержится \(k\) единиц.
- Первая дописанная цифра: \(p=k\bmod 2\).
- После её добавления число единиц станет \(k+p\), а оно всегда чётное. Поэтому вторая дописанная цифра равна \(0\).
Значит, результат в двоичной системе имеет вид:
\[ \text{двоичная запись }N+p0, \]
а в десятичной системе:
\[ R=4N+2p. \]
Проверим ближайшие значения:
- \(N=10\): \(1010_2\), единиц \(2\), поэтому \(p=0\), результат \(4\cdot10=40\), не подходит;
- \(N=11\): \(1011_2\), единиц \(3\), поэтому \(p=1\):
\[ 1011\to10111\to101110_2. \]
\[ 101110_2=32+8+4+2=46. \]
Следующее возможное значение больше, поэтому наименьший подходящий результат — \(\boxed{46}\).
