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

Просмотры: 879
Изменено: 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\)