Question

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

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

P.S. Бьюсь уже часа два. По идеи, если не брать первое действие, то подходят в ответ 58-111010 / 60-111100 / 66-1000010 и т.д. Ответ 66, но почему именно он, а не 58 или 60 например, я не знаю...(

Answer 1

Такие задания со сложными условиями легче всего решать программой на питоне:

for n in range(1, 10000000):  # Грубый перебор

   n -= n % 4  # 1. Из числа N вычитается остаток от деления N на 4.

   n = bin(n)[2:]  # 2. Строится двоичная запись полученного результата. + срез "0b"

   n = n + str(n.count('1') % 2)  # 3. a)

   n = n + str(n.count('1') % 2)  # 3. б)

   r = int(n, 2)  # Перевод в 10 с.с.

   if r > 56:

       print(r)  

       break

Ответ: 66

Если всё же рассуждать, то опять перебором:

Возьмём, например, число 5 и выполним алгоритм:

1. 5 - 5 % 4 = 4

2. 4 -> 100

3. a) 1001

   б) 10010

R = 18, очень мало

Возьмём, например, 14:

1. 12  

2. 1100

3. a) 11000

   б) 110000

R = 48, маловато, но близко

Возьмём, например, 15:

1. 12

Видим, будет тоже, что и 14

Возьмём, например, 16:

1. 16

2. 10000

3. a) 100001

   б) 1000010

R = 66, то, что нам нужно.

Ответ: 66