Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задание 5. Информатика. ЕГЭ. Статград. 04.03.2025
- Просмотры: 2434
- Изменено: 4 марта 2025
Алгоритм получает на вход натуральное число \(N\) и строит по нему новое число \(R\) следующим образом.
- Строится двоичная запись числа \(N.\)
- Если в двоичной записи числа \(N\) нулей больше, чем единиц, то самый левый ноль заменяется на единицу. В противном случае самая правая единица заменяется на ноль.
- Результат переводится в десятичную систему счисления.
- Результатом работы алгоритма становится модуль разности исходного числа \(N\) и числа, полученного на предыдущем шаге.
Пример 1. Дано число \(N = 17.\) Алгоритм работает следующим образом.
- Строим двоичную запись числа \(N:\) \(17_{10} = 10001_2.\)
- В полученном двоичном числе нулей больше, заменяем самый левый ноль: \(10001 \to 11001.\)
- Переводим в десятичную систему: \(11001_2 = 25_{10}.\)
- Вычисляем модуль разности: \(| 17 – 25 | = 8.\)
Пример 2. Дано число \(N = 28.\) Алгоритм работает следующим образом.
- Строим двоичную запись числа \(N:\) \(28_{10} = 11100_2.\)
- В полученном двоичном числе нулей не больше, заменяем самую правую единицу: \(11100 \to 11000.\)
- Переводим в десятичную систему: \(11000_2 = 24_{10}.\)
- Вычисляем модуль разности: \(| 28 – 24 | = 4.\)
Результат работы алгоритма \(R = 4.\)
При каком наименьшем \(N,\) не превышающем \(10^9,\) в результате работы алгоритма получится наибольшее значение \(R?\)
Решение:
Исходное число \(N\) и число, полученное на втором шаге отличается только одним битом, там где единица была заменена на ноль или наоборот. Поэтому модуль разности исходного числа и числа, получившегося на втором шаге, будет равен \(2^n,\) где \(n\) — номер бита (счёт идет с нуля справа налево), где произошла замена. Так как \(2^{30} > 10^9,\) а \(2^{29} < 10^9,\) то число \(N\) должно быть максимум \(30\)- разрядное в двоичной системе счисления. Чтобы получить наибольшее \(R = 2^n,\) мы должны взять наибольшее из возможных \(n.\) Значит, \(n = 28.\) Так как замена нуля на единицу должна произойти в наибольшем разряде, то в двоичной записи количество нулей числа \(N\) должно превышать количество единиц. Учитывая требование, чтобы \(N\) при этом было минимальным, получаем, что \(N = 2^{29} = 536870912.\)
Ответ: \(536870912\)
Обсуждение задания
Здесь пока нет ни одного комментария. Будьте первым!
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене.
Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Совершая донат, вы соглашаетесь с Условиями использования