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

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

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

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

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

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

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

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

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

Решение.

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

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

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

 

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

98_10 = 1100010_2  — на конце 10, но сумма остальных разрядов чётна, не подходит ни под один из случаев.

100_10 = 1100100_2  — на конце 00, но сумма остальных разрядов нечётна, не подходит.

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

 

Ответ: 25.

 

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

print(n)

break