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