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

Просмотры: 2317
Изменено: 2 февраля 2025

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

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

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

  1. Строим двоичную запись: \(17_{10} = 10001_2.\)
  2. В полученном двоичном числе две единицы и три нуля. Переводим в двоичную систему: \(2_{10} = 10_2, \, 3_{10} = 11_2.\) Записываем подряд: \(1011.\)
  3. Переводим в десятичную систему: \(1011_2 = 11_{10}.\)

Результат работы алгоритма \(R = 11.\)

Определите минимальное число \(N,\) для которого результатом работы данного алгоритма будет \(R = 214.\)

Решение:

Простым перебором эта задача решается долго. Пойдём другим путём. В двоичном виде \(214_{10} = 11010110_2.\) Так как мы хотим получить минимальное число, то количество разрядов в числе \(R\) должно быть минимальным, причём единиц должно быть меньше, чем нулей. Значит, количество единиц должно быть \(110_2 = 6_{10},\) а нулей — \(10110_2 = 22_{10}.\) Составим из них минимальное число. Для этого все единицы за исключением одной отправим в младшие разряды.


>>> s = '1' + '0' * 22 + '1' * 5
>>> int(s, 2)
134217759

Это ответ. На всякий случай проверим его программой:


def R(N):
    bn = f'{N:b}'
    d = f'{bn.count("1"):b}' + f'{bn.count("0"):b}'
    return int(d, 2)

for N in range(134217759, 134217759 + 5):
    if R(N) == 214:
        print(N)
        break

Ответ: \(134217759\)