5 номер. Преобразование записей чисел
Преобразование двоичной записи
Автомат обрабатывает натуральное число N по следующему алгоритму.
1 Строится двоичная запись числа N.
2 Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3 Полученное число переводится в десятичную запись.
4 Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11 Алгоритм работает следующим образом.
1 Двоичная запись числа N: 1011
2 Удаляется первая единица и следующий за ней ноль: 11
3 Десятичное значение полученного числа 3
4 На экран выводится число 11 – 3 = 8
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 2.
Дописывание справа реализуется как s + suffix, слева — как prefix + s. Добавляйте ровно указанную последовательность символов, включая нули. Числовое сложение вместо соединения строк здесь меняет алгоритм.
Удаление разрядов выполняйте срезом строки со стороны, указанной в условии. После удаления числовое значение остатка записи вычисляется заново; ведущие нули не увеличивают это значение.
В шаге с разностью важен порядок операндов. Сохраните исходное число и промежуточные результаты отдельно, чтобы вычитать именно указанные величины, не перезаписав одну из них строковым представлением.
После завершения всех преобразований получите числовой результат: R = int(s, 2). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 7.