ВОПРОС 7: На вход алгоритма подаётся натуральное число №. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа №. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно; б) к этой записи справа дописывается 1, если остаток от деления количества единиц на 2 равен 0, и 0, если остаток от деления количества единиц на 2 равен 1. Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 54 и может являться результатом работы алгоритма. В ответе это число должно быть в десятичной системе Только один вариант ответа 56 53 55

Решение:

Алгоритм строит число R по числу N следующим образом:

1. Строится двоичная запись числа N.
2. К двоичной записи дописываются два разряда справа:
   • Первый разряд (а): 1, если число единиц в двоичной записи N чётно, и 0 — если нечётно.
   • Второй разряд (б): 1, если остаток от деления числа единиц на 2 равен 0, и 0 — если равен 1.

Обратим внимание, что правило (а) и (б) описывают одно и то же: чётность количества единиц. Таким образом, оба дописываемых разряда будут одинаковыми.

Нам нужно найти минимальное число R, которое больше 54 и является результатом работы алгоритма. Переведём 54 в двоичную систему:

\( 54 = 32 + 16 + 4 + 2 = 110110_2 \)

Теперь рассмотрим числа, большие 54, и применим к ним алгоритм:

Если R = 55:

Двоичная запись 55: \( 55 = 32 + 16 + 4 + 2 + 1 = 110111_2 \).

Число единиц в \( 110111_2 \) равно 5 (нечётное).

По правилу (а) дописывается 0.

По правилу (б) остаток от деления 5 на 2 равен 1, дописывается 0.

Таким образом, если R = 55 ( \( 110111_2 \) ), то N = \( 1101 \)_2 = \( 8 + 4 + 1 = 13 \).

Если R = 56:

Двоичная запись 56: \( 56 = 32 + 16 + 8 = 111000_2 \).

Число единиц в \( 111000_2 \) равно 3 (нечётное).

По правилу (а) дописывается 0.

По правилу (б) остаток от деления 3 на 2 равен 1, дописывается 0.

Таким образом, если R = 56 ( \( 111000_2 \) ), то N = \( 111 \)_2 = \( 4 + 2 + 1 = 7 \).

Если R = 53:

Двоичная запись 53: \( 53 = 32 + 16 + 4 + 1 = 110101_2 \).

Число единиц в \( 110101_2 \) равно 4 (чётное).

По правилу (а) дописывается 1.

По правилу (б) остаток от деления 4 на 2 равен 0, дописывается 1.

Таким образом, если R = 53 ( \( 110101_2 \) ), то N = \( 1101 \)_2 = \( 8 + 4 + 1 = 13 \). Этот вариант меньше 54.

Нам нужно найти минимальное R, которое превышает 54. Из предложенных вариантов, 55 и 56 больше 54. Для R=55, число единиц — 5 (нечётное), дописываем 00. Исходное число N — \( 11011 \)_2 = 27. Для R=56, число единиц — 3 (нечётное), дописываем 00. Исходное число N — \( 111 \)_2 = 7.

По условию, R должно превышать 54. Минимальное число из предложенных вариантов, которое превышает 54, это 55.

Проверим 55. Двоичная запись 55: \( 110111_2 \). Число единиц = 5 (нечетное). Правило (а) -> 0. Правило (б) -> остаток от деления 5 на 2 = 1, значит дописываем 0. Итого R = \( 11011100 \)_2 = 55*4 = 220. Это не соответствует условию.

Давайте разберем алгоритм правильно. Алгоритм получает N, строит его двоичную запись, к ней дописывает 2 бита. Полученное R должно быть > 54.

Нам нужно найти такое N, чтобы R > 54.

R = (двоичная запись N) + (два бита)

Рассмотрим R = 55 = \( 110111_2 \).

Если последние два бита — это результат алгоритма, то N = \( 11011 \)_2. Число единиц в N = 4 (четное). По правилу (а) дописывается 1. По правилу (б) остаток от 4 на 2 = 0, дописывается 1. Получаем \( 1101111 \)_2, что равно 55+2 = 57. Это не R=55.

Рассмотрим R = 56 = \( 111000_2 \).

Если последние два бита — это результат алгоритма, то N = \( 11100 \)_2. Число единиц в N = 3 (нечетное). По правилу (а) дописывается 0. По правилу (б) остаток от 3 на 2 = 1, дописывается 0. Получаем \( 1110000 \)_2, что равно 56*2 = 112. Это не R=56.

Рассмотрим R = 53 = \( 110101_2 \).

Если последние два бита — это результат алгоритма, то N = \( 11010 \)_2. Число единиц в N = 3 (нечетное). По правилу (а) дописывается 0. По правилу (б) остаток от 3 на 2 = 1, дописывается 0. Получаем \( 1101000 \)_2, что равно 53*4 = 212. Это не R=53.

Давайте попробуем от обратного. Нам нужно R > 54. И R получено из N путем добавления 2 бит.

R = N_bin + p1 + p2 (где p1, p2 - добавленные биты)

Так как добавляются 2 бита, то R = N * 4 + (значение добавленных бит).

Значение добавленных бит может быть 00, 01, 10, 11 (0, 1, 2, 3 в десятичной).

Правила (а) и (б) эквивалентны: оба определяются четностью числа единиц в N.

Если число единиц в N чётно, добавляются '11'.

Если число единиц в N нечётно, добавляются '00'.

Нам нужно найти минимальное R > 54, которое соответствует этому правилу.

Переберем числа N и посмотрим, какое R получится.

N=7 (\( 111_2 \)). Число единиц = 3 (нечетное). Добавляем '00'. R = \( 11100_2 \) = 28. (Меньше 54).

N=8 (\( 1000_2 \)). Число единиц = 1 (нечетное). Добавляем '00'. R = \( 100000_2 \) = 32. (Меньше 54).

N=9 (\( 1001_2 \)). Число единиц = 2 (четное). Добавляем '11'. R = \( 100111_2 \) = 39. (Меньше 54).

N=10 (\( 1010_2 \)). Число единиц = 2 (четное). Добавляем '11'. R = \( 101011_2 \) = 43. (Меньше 54).

N=11 (\( 1011_2 \)). Число единиц = 3 (нечетное). Добавляем '00'. R = \( 101100_2 \) = 44. (Меньше 54).

N=12 (\( 1100_2 \)). Число единиц = 2 (четное). Добавляем '11'. R = \( 110011_2 \) = 51. (Меньше 54).

N=13 (\( 1101_2 \)). Число единиц = 3 (нечетное). Добавляем '00'. R = \( 110100_2 \) = 52. (Меньше 54).

N=14 (\( 1110_2 \)). Число единиц = 3 (нечетное). Добавляем '00'. R = \( 111000_2 \) = 56. (Больше 54).

Таким образом, минимальное R, которое превышает 54 и может являться результатом работы алгоритма, равно 56. Оно получается из N=14.

Проверим R=55. Чтобы получить R=55 (\( 110111_2 \)), нужно, чтобы последние два бита были 11 (четное число единиц в N) или 00 (нечетное число единиц в N).

Если последние два бита '11' (\( 11_2 = 3 \)), то N = \( 1101 \)_2 = 13. Число единиц в N = 3 (нечетное). Должны были добавить '00', а добавили '11'. Значит, 55 не может быть результатом.

Если последние два бита '00' (\( 00_2 = 0 \)), то N = \( 110111 \)_2 = 55. Число единиц в N = 5 (нечетное). Добавляем '00'. Получаем \( 11011100 \)_2 = 220. Не 55.

Проверим 56 = \( 111000_2 \). Если последние два бита '00', то N = \( 1110 \)_2 = 14. Число единиц в N = 3 (нечетное). Добавляем '00'. Получаем \( 111000 \)_2 = 56. Это подходит.

Проверим 53 = \( 110101_2 \). Если последние два бита '01', это невозможно по правилам алгоритма. Биты должны быть одинаковыми.

Минимальное R, которое больше 54, это 56.

Ответ: 56