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

Решение:

Обозначим $M=N-(N\bmod 8)+(N\bmod 2)$ — результат первого шага. Число $N-(N\bmod 8)$ кратно 8, а прибавляется 0 для чётного $N$ и 1 для нечётного. Значит, $M$ — это число вида $8k$ или $8k+1$, и любое такое число достижимо.

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

Нужно наименьшее $R\gt 90$. Так как $p\le 1$, из $4M+2p\gt 90$ следует $4M\ge 89$, то есть $M\ge 23$. Ближайшие подходящие значения $M$ — это 24 и 25.

• $M=24=11000_2$: единиц две, $p=0$, запись $11000\to 110000\to 1100000$, $R=96\gt 90$;
• $M=25=11001_2$: единиц три, $p=1$, $R=4\cdot 25+2=102$.

Все более крупные $M$ дают $R\ge 4\cdot 32=128$. Наименьшее значение $R$, большее 90, равно 96.

def alg(n):
    b = bin(n - n % 8 + n % 2)[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 > 90))

Ответ: 96