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

Answer 2

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

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

Понятно, что это действие приведет к тому, что R будет кратно 4. То есть R = 4k, где k - некоторое целое число.

2. Строится двоичная запись полученного результата.

Это не влияет на значение R, так как двоичная запись не меняет само число, а только его представление.

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

а) Складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа.

Это действие добавляет один разряд в двоичной записи числа. То есть если у нас было, например, 101 в двоичной записи, то после этого действия оно станет 1010. Если сумма всех цифр была четной, то добавится 0, а если нечетной, то добавится 1.

б) Те же действия.

Это повторное действие еще раз добавляет один разряд в двоичной записи числа на основе суммы цифр.

Таким образом, суммарно мы добавляем 2 разряда на основе суммы цифр двоичной записи числа, что эквивалентно добавлению 1 разряда в десятичной записи числа.

Теперь мы можем попробовать найти минимальное значение R, удовлетворяющее этим условиям. Поскольку R = 4k, начнем с минимального значения k = 14 (56/4), а затем будем увеличивать его, пока не найдем подходящее R.

1. k = 14: R = 4 * 14 = 56 После применения действий (а) и (б), мы добавим 1 разряд к числу. Получится 5. Далее, при следующей итерации, опять добавим 1 разряд, и получится 50.

2. k = 15: R = 4 * 15 = 60 После применения действий (а) и (б), мы добавим 1 разряд к числу. Получится 6. Далее, при следующей итерации, опять добавим 1 разряд, и получится 60.

3. k = 16: R = 4 * 16 = 64 После применения действий (а) и (б), мы добавим 1 разряд к числу. Получится 7.

Как видим, для k = 16 уже не удовлетворяет условиям алгоритма, так как добавился разряд 7, и это не соответствует добавлению 1 разряда в десятичной записи.

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