Question

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 137. В ответе это число запишите в десятичной системе счисления.​

Answer 1

Ответ:

35

Объяснение:

Переводим 138 в двоичку, получаем 10001010. Нам нужно, чтобы первые 6 цифр в сумме давали нечётное число, тогда пишется справа от этого числа 1, если чётное - то 0. Число 138 нам не подходит, так как алгоритм выполняется неправильно. Ближайшее справа  число к 137 имеет следующую двоичную запись: 10001110. Первые 6 цифр нечётны, пишется 1, потом заново: первые семь цифр чётны, пишется 0. Переводим 10001110 в десятичную, получаем 35.

Answer 2

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

1. Начнем с N = 1:

   • Двоичная запись числа 1: 1
   • Сумма цифр: 1
   • Остаток от деления суммы на 2: 1
   • Новая запись: 11 Этот результат не подходит.

2. Попробуем N = 2:

   • Двоичная запись числа 2: 10
   • Сумма цифр: 1
   • Остаток от деления суммы на 2: 1
   • Новая запись: 101 Этот результат также не подходит.

3. Продолжим с N = 3:

   • Двоичная запись числа 3: 11
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 110
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 1100 Этот результат не подходит.

4. Продолжим с N = 4:

   • Двоичная запись числа 4: 100
   • Сумма цифр: 1
   • Остаток от деления суммы на 2: 1
   • Новая запись: 1001
   • Сумма цифр: 3
   • Остаток от деления суммы на 2: 1
   • Новая запись: 10011 Этот результат не подходит.

5. Продолжим с N = 5:

   • Двоичная запись числа 5: 101
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 1010
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 10100 Этот результат не подходит.

6. Продолжим с N = 6:

   • Двоичная запись числа 6: 110
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 1100
   • Сумма цифр: 2
   • Остаток от деления суммы на 2: 0
   • Новая запись: 11000 Этот результат не подходит.

7. Продолжим с N = 7:

   • Двоичная запись числа 7: 111
   • Сумма цифр: 3
   • Остаток от деления суммы на 2: 1
   • Новая запись: 1111
   • Сумма цифр: 4
   • Остаток от деления суммы на 2: 0
   • Новая запись: 11110 Это число подходит.

Итак, наименьшее число N, для которого результат работы алгоритма больше 137, это 7.