Question

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

Answer 1

Так как новое число образуется из предыдущего путём "дописывания" в нижние разряды двоичного представления некоторых цифр, то при увеличении числа от 0 до +∞ результирующее число также будет возрастать. При чем для каждого входного числа N существует только одно результирующее число N'.

Это значит, что по достижении какого-то значения N*, результирующие значения всегда будут больше 80, и в рассмотрении принимать участие не будут.

Вопрос заключается в определении этой верхней границы (нижняя граница задаётся ограничениями на входные данные до натуральных чисел и равняется 1, а если рассмотреть пример, то можно поднять это значение до 13). Вполне очевидно, что результирующие числа всегда больше или равны соответствующих входных чисел. Поэтому в качестве изначального значения для верхнего предела имеет смысл выбрать 80.

Есть несколько подходов к нахождению этой верхней границы. Можно, например, проанализировать то, как преобразуются значения и из свойств двоичных чисел сузить верхнюю границу. Мы же воспользуемся ещё одним способом – бинарным поиском. "Глупый поиск" был бы не очень хорошим вариантом, ведь вычислять значения перебирая входные до 13 до 80 – дело долгое и утомительное.

Однако бинарный поиск – решение более элегантное, и позволит найти необходимый предел в худшем случае за 7 расчетов. Можем мы использовать его из-за того, что мы знаем, что значения уникальны, возрастают и искомое значение делит весь набор результирующих значений на две части: (< 80) и (>= 80).

Приступим. Рассмотрим промежуток входных значений [13; 80]. Мы знаем , что 13 точно подходит, а 80 – точно не подходит. Возьмем значение посередине и вычислим для него результат.

$\frac{13 + 80}{2} \approx 46$

46 -> 101110 (4)

4 % 2 = 0

1011100 (4)

4 % 2 = 0

10111000 -> 184 – Не подходит. Это значит, что проверять значения ≥  46 не имеет смысла, и мы можем их просто отбросить. А значение 46 становится новым приближением сверху.

Выбираем следующее число:

$\frac{13+46}{2} \approx 29$

29 -> 11101 (4), что по аналогии с предыдущим станет 1110100 (4)

1110100 -> 116 – снова не подходит. Повторяем ещё раз.

Выбираем следующее число:

$\frac{13+29}{2} \approx 21$

21 -> 10101 (3) -> 101011 (4) -> 1010110(4) -> 86

На этот раз мы уже подобрались близко.

Проверим значения для 19 и 20.

20 -> 10100 (2) -> 101000 (2) -> 1010000 (2) -> 80 – НЕ подходит.

19 -> 10011 (3) -> 100111 (4) -> 1001110 (4) -> 78 – подходит!  

Итак, мы нашли верхний предел. Таким образом для входных значений от 1 до 19 результирующие значения будут всегда меньше 80. А так как каждое результирующее значение уникально, то получаем 19 уникальных значений в ответе.

Ответ: 19.