5 номер. Преобразование записей чисел
Преобразование двоичной записи
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) В конец двоичной записи добавляется двоичный код остатка от деления числа N на 4
3) Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример 1 Дано число N = 13 Алгоритм работает следующим образом.
1) Строим двоичную запись: 13₁₀ = 1101₂
2) Остаток от деления 13 на 4 равен 1, добавляем к двоичной записи цифру 1, получаем 11011₂ = 27₁₀
3) Результат работы алгоритма R = 27
Пример 2 Дано число N = 14 Алгоритм работает следующим образом.
1) Строим двоичную запись: 14₁₀ = 1110₂
2) Остаток от деления 14 на 4 равен 2, добавляем к двоичной записи цифры 10 (10₂ = 2₁₀), получаем 111010₂ = 58₁₀
3) Результат работы алгоритма R = 58
Назовем доступными числа, которые могут получиться в результате работы этого алгоритма. Например, числа 27 и 58 – доступные.
Какое наибольшее количество доступных чисел может быть на отрезке, содержащем 65 натуральных чисел?
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Какое наибольшее количество доступных чисел может быть на отрезке, содержащем 65 натуральных чисел?
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 2.
После завершения всех преобразований получите числовой результат: R = int(s, 2). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 25.