Автомат обрабатывает натуральное число 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, может появиться на экране в результате работы автомата?
даю 100 баллов, с решением пожалуйста
Ответы
Ответ:
86
Объяснение:
Нужно проверить несколько чисел больше 80.
Предположим это число 81
81₂ = 1010001 - такое число не может получится в результате работы автомата, поскольку его последняя цифра - 1, а это значит что сумма остальных цифр не делится на 2 без остатка. В нашем случае сумма остальных цифр =2, поэтому 81 не подходит.
Проверим число 82.
82₂ = 1010010 - такое число тоже не может получится в итоге, поскольку последняя цифра 0 может получится только в том случае когда сумма остальных цифр делится без остатка на 2. Сумма остальных цифр =3, на 2 не делится, 82 не подходит.
Проверим число 83.
83₂ = 1010011
83 тоже не походит, поскольку, хотя последняя единица подходит под условие, но предпоследняя цифра 1 не может получится в результате работы автомата.
Проверяем 84
84₂ = 1010100 - не подходит по тем же причинам, потому что изначальное число будет 10101 и на конце не могут добавится 00
Проверяем 85
85₂ = 1010101 - не подходит по тому же принципу. предпоследняя цифра не может быть 0
Проверяем 86
86₂= 1010110
Убирая 2 последние цифры получаем исходное число 10101
Сумма его цифр 3, остаток от деления на 2 равен 1, дописываем этот остаток справа, получаем число
101011. Его сумма цифр = 4, остаток от деления на 2 равно 0, дописываем этот 0 справа, получаем число
1010110
То есть двоичное представление числа 86 это 1010110, что полностью соответствует алгоритму работы автомата.
Ответ. Минимальное число, большее 80, которое может получится в результате работы автомата - это число 86