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

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

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

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

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

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

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

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

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

Решение.

Если в числе было нечётное количество единиц, то в конец допишется 10. Если количество единиц чётное, то допишется 00. Рассмотрим числа, большие 43. Имеем:

4410 = 1011002  — не может являться результатом работы алгоритма,

4510 = 1011012  — не может являться результатом работы алгоритма,

4610 = 1011102  — может являться результатом работы алгоритма, количество единиц (кроме последних двух разрядов) нечетное, и в последних двух разрядах 10.

 

Ответ: 46.

 

Приведём другое решение на языке 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)

summa = f(s)

s = s + str(summa % 2)

summa = f(s)

s = s + str(summa % 2)

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

if r > 43:

print(r)

break

Источник: ЕГЭ 05.05.2015. Досрочная волна.