Задание №5 — Анализ простейших алгоритмов

#69756Задание №5ФИПИ

Анализ алгоритмов и исполнители

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Из числа N вычитается остаток от деления N на 4.
2) Строится двоичная запись полученного результата.
3) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия - справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число R, большее 100, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Правильный ответ

114

Пояснение

Решение:

Обозначим $M=N-(N\bmod 4)$ — результат первого шага. Это ближайшее снизу число, кратное 4, и при переборе всех $N$ величина $M$ пробегает в точности все кратные четырём числа.

Пусть в двоичной записи $M$ ровно $k$ единиц и $p=k\bmod 2$ . На шаге 3а справа приписывается $p$ . После этого сумма цифр равна $k+p$ — она чётна при любом $k$ , поэтому на шаге 3б приписывается 0.

Итак, к записи $M$ всегда приписываются два разряда $p$ и 0, то есть $R=4M+2p$ , где $p$ — чётность количества единиц в $M$ .

Нужно наименьшее $R\gt 100$ . Так как $p\le 1$ , из $4M+2p\gt 100$ следует $4M\ge 99$ , то есть $M\ge 25$ ; а $M$ кратно 4, поэтому $M\ge 28$ . Величина $R=4M+2p$ растёт вместе с $M$ , значит достаточно взять наименьшее допустимое $M=28$ .

$M=28=11100_2$ , единиц три, $p=1$ : запись $11100$ превращается в $111001$ , затем в $1110010$ , то есть $R=1110010_2=114$ .

Для сравнения, предыдущее кратное четырём $M=24=11000_2$ даёт $p=0$ и $R=96$ — это не больше 100.

def alg(n):
    b = bin(n - n % 4)[2:]
    b += str(sum(map(int, b)) % 2)
    b += str(sum(map(int, b)) % 2)
    return int(b, 2)

print(min(r for r in {alg(n) for n in range(1, 1000)} if r > 100))

Ответ: 114