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

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

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

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

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

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

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

Пояснение

Решение:

После первого шага получается число $M = N - (N \bmod 4)$ , кратное 4, поэтому его двоичная запись оканчивается двумя нулями. Любое кратное четырём число может получиться на этом шаге (достаточно взять $N = M$ ), так что дальше можно перебирать сразу значения M.

Разберёмся с двумя приписываемыми разрядами. Пусть в двоичной записи числа M ровно s единиц, тогда сумма её цифр равна s.

Первым приписывается разряд $s \bmod 2$ .
После этого сумма цифр становится равной $s + (s \bmod 2)$ — а это число всегда чётно, поэтому второй приписанный разряд всегда 0.

Итак, если единиц в записи M чётное число, справа приписывается 00, если нечётное — 10. Приписывание двух разрядов умножает число на 4, поэтому $R = 4M$ или $R = 4M + 2$ , причём M кратно 4, то есть R кратно 16 либо даёт при делении на 16 остаток 2.

Перебираем M, кратные четырём, и ищем первый результат, больший 56:

$M = 12 = 1100_2$ : единиц две, число чётное, приписываем 00, получаем $110000_2 = 48$ — не больше 56;
$M = 16 = 10000_2$ : единица одна, число нечётное, приписываем 10, получаем $1000010_2 = 66$ — больше 56.

Между 48 и 66 других результатов нет, потому что каждое следующее значение M кратно 4 и увеличивает R сразу на 16. Значит, минимальное $R \gt 56$ равно 66. Проверка программой:

res = set()
for n in range(4, 1000):
    m = n - n % 4
    s = bin(m)[2:]
    s += str(sum(map(int, s)) % 2)
    s += str(sum(map(int, s)) % 2)
    res.add(int(s, 2))

print(min(r for r in res if r > 56))

Программа печатает 66. Ответ: 66