Информатика. ЕГЭ

Перейти к заданиям

Задание 5. Информатика. ЕГЭ. Статград. 04.03.2025

Просмотры: 2388
Изменено: 4 марта 2025

Алгоритм получает на вход натуральное число \(N\) и строит по нему новое число \(R\) следующим образом.

  1. Строится двоичная запись числа \(N.\)
  2. Если в двоичной записи числа \(N\) нулей больше, чем единиц, то самый левый ноль заменяется на единицу. В противном случае самая правая единица заменяется на ноль.
  3. Результат переводится в десятичную систему счисления.
  4. Результатом работы алгоритма становится модуль разности исходного числа \(N\) и числа, полученного на предыдущем шаге.

Пример 1. Дано число \(N = 17.\) Алгоритм работает следующим образом.

  1. Строим двоичную запись числа \(N:\) \(17_{10} = 10001_2.\)
  2. В полученном двоичном числе нулей больше, заменяем самый левый ноль: \(10001 \to 11001.\)
  3. Переводим в десятичную систему: \(11001_2 = 25_{10}.\)
  4. Вычисляем модуль разности: \(| 17 – 25 | = 8.\)

Пример 2. Дано число \(N = 28.\) Алгоритм работает следующим образом.

  1. Строим двоичную запись числа \(N:\) \(28_{10} = 11100_2.\)
  2. В полученном двоичном числе нулей не больше, заменяем самую правую единицу: \(11100 \to 11000.\)
  3. Переводим в десятичную систему: \(11000_2 = 24_{10}.\)
  4. Вычисляем модуль разности: \(| 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\)

kege1

kege2

kege3

Новый тренажёр-эмулятор
Станции КЕГЭ

Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене

Новое видео
Методы решения задания 16 ЕГЭ по Информатике «Вычисление рекуррентных выражений»
Поддержать автора сайта!
​ Поддержите автора сайта, если материалы, размещённые здесь, оказались вам полезны.
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
  1. 13 октября 2026 года
  2. 3 декабря 2026 года
  3. 21 января 2027 года
  4. 19 февраля 2027 года
  5. 23 марта 2027 года
  6. 27 апреля 2027 года
Математика ОГЭ 9 класс
  1. 23 сентября 2026 года
  2. 1 декабря 2026 года
  3. 22 января 2027 года
  4. 3 марта 2027 года
  5. 14 апреля 2027 года
Физика ОГЭ 9 класс
  1. 19 октября 2026 года
  2. 10 декабря 2026 года
  3. 29 января 2027 года
  4. 17 марта 2027 года
  5. 22 апреля 2027 года
Математика ЕГЭ 10 класс
  1. 3 февраля 2027 года
  2. 11 мая 2027 года
Информатика ЕГЭ 11 класс
  1. 22 октября 2026 года
  2. 15 декабря 2026 года
  3. 26 января 2027 года
  4. 2 марта 2027 года
  5. 13 апреля 2027 года
Математика ЕГЭ 11 класс
  1. 30 сентября 2026 года
  2. 17 декабря 2026 года
  3. 9 февраля 2027 года
  4. 16 марта 2027 года
  5. 21 апреля 2027 года
Физика ЕГЭ 11 класс
  1. 14 октября 2026 года
  2. 16 декабря 2026 года
  3. 4 февраля 2027 года
  4. 12 марта 2027 года
  5. 9 апреля 2027 года