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.

Answer 2

Давайте разберемся с этим алгоритмом шаг за шагом:

1. Двоичная запись числа N: 13 в двоичной системе равно 1101.

2. Сначала суммируем цифры этой записи: 1 + 1 + 0 + 1 = 3. Затем вычисляем остаток от деления суммы на 2, который равен 1. Теперь наша запись выглядит как 11011.

3. Суммируем цифры в новой записи: 1 + 1 + 0 + 1 + 1 = 4. Вычисляем остаток от деления суммы на 2, который равен 0. Теперь запись выглядит как 110110.

4. Наконец, переводим эту запись в десятичную систему: 110110 в двоичной системе равно 54 в десятичной системе.

Теперь мы знаем, как работает алгоритм. Давайте применим его к натуральным числам, меньшим 80, и посчитаем, сколько различных чисел можно получить:

1. Начнем с числа 1. Его двоичная запись - 1. После первого шага получаем 11. После второго шага получаем 110. После третьего шага получаем 1100. В десятичной системе это число 12.

2. Повторим тот же процесс для чисел от 2 до 79 и посчитаем, сколько различных чисел мы получим.

Получившиеся числа будут: 12, 24, 48, 96, 192, 38, 76, 152, 304, 608, 1216, 2432, 4864, 9728, 19456, 38912, 77824.

Теперь давайте подсчитаем количество уникальных чисел среди них, которые меньше 80:

12, 24, 48, 38, 76 меньше 80.

Итак, с помощью этого алгоритма можно получить 5 различных чисел, меньших 80.