Задания
Версия для печати и копирования в MS Word
Тип 5 № 10468

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

1.  Строится двоичная запись числа N.

2.  К этой записи дописываются справа ещё два разряда по следующему правилу:

а)  складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б)  над этой записью производятся те же действия  — справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R.

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

Спрятать решение

Решение.

Если изначально сумма разрядов была чётная, то в конец запишется 00, что эквивалентно N arrow N умножить на 4.

Если же сумма была нечётная, то запишется 10, что эквивалентно N arrow N умножить на 4 плюс 2.

В обоих случаях число получается чётным.

Посмотрим на чётные числа, превосходящие 77.

78_10 = 1001110_2  — на конце 10, а сумма остальных разрядов нечётна. Число подходит под второй случай, значит, число, из которого оно было получено, равно  дробь: числитель: 78 минус 2, знаменатель: 4 конец дроби = 19 .

 

Ответ: 19.

 

Приведём другое решение на языке Python.

def f(s):

summa = 0

for i in range(len(s)):

summa += int(s[i])

return summa

for n in range(1, 100):

s = bin(n)[2:] # перевод в двоичную систему

s = str(s)

s = s + str(f(s) % 2)

s = s + str(f(s) % 2)

r = int(s, 2) # перевод в десятичную систему

if r > 77:

print(n)

break

Источник: Демонстрационная версия ЕГЭ−2022 по информатике