Автомат обрабатывает натуральное число N по следующему алгоритму: 1. Строится двоичная запись числа N. 2. В конец записи (справа) добавляется (дублируется) последняя цифра. 3. Складываются все цифры полученной двоичной записи. В конец записи (справа)

24 октября 2025
Информационные технологии

Условие:

Автомат обрабатывает натуральное число N по следующему алгоритму: 1. Строится двоичная запись числа N.
2. В конец записи (справа) добавляется (дублируется) последняя цифра. 3. Складываются все цифры полученной двоичной записи. В конец записи
(справа) дописывается остаток от деления суммы на 2.
4. Результат переводится в десятичную систему и выводится на экран. Пример. Дано число N = 13. Алгоритм работает следующим образом: 1. Двоичная запись числа N: 1101.
2. Дублируется последняя цифра, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая
запись 110110.
4. На экран выводится число 54.
Какое наименьшее число, большее 105, может появиться на экране в результате работы автомата?

Решение:

Мы рассмотрим работу алгоритма на входном числе N. Напомним, что алгоритм действует так: 1. Строится двоичная запись числа N (обозначим её B). 2. К ней дописывается справа последняя цифра B (обозначим её L). Тогда получается новая запись D = B ‖ L. 3. Суммируются все цифры полученной записи D, и к D справа дописывается остаток от деления этой суммы на 2 (обозначим его r). 4. Полученную запись F = D ‖ r интерпретируют как двоичное число и выводят в десятичной системе. Например, для N = 13: – Двоичная запись: 1101. – Дублируем последнюю цифру (1): получаем 11011. – Сумма цифр 1+1+0...