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

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

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

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

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

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

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

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

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

Решение.

Рассмотрим числа, большие 83, и найдем меньшее число, которое является результатом работы алгоритма.

84 = 10101002  — не является результатом работы алгоритма.

85 = 10101012  — не является результатом работы алгоритма.

86 = 10101102  — является результатом работы алгоритма для числа 101012.

Таким образом, искомое число  — 86.

 

Ответ: 86.

 

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

print(r)

break

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