ВОПРОС 8: На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи, если а) сумма нечетная к числу дописывается 11, б) сумма четная, дописывается 00. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число должно быть в десятичной системе счисления. Только один вариант ответа 120 117 115

Решение:

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

1. Строится двоичная запись числа N.
2. К записи числа N справа дописываются два разряда:
• Если сумма цифр двоичной записи N нечетная, дописывается '11'.
• Если сумма цифр двоичной записи N четная, дописывается '00'.
3. Полученная запись является двоичной записью числа R.

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

Рассмотрим варианты ответов:

1. R = 115. В двоичной системе это 1110011.
• Последние два разряда: '11'. Это значит, что сумма цифр исходного числа N была нечетной.
• Уберем последние два разряда: 111001.
• Сумма цифр числа 111001: 1 + 1 + 1 + 0 + 0 + 1 = 4. Сумма четная.
• Согласно правилу, если сумма цифр четная, должны дописываться '00'. Но у нас '11'. Значит, 115 не может быть результатом работы алгоритма.
2. R = 117. В двоичной системе это 1110101.
• Последние два разряда: '01'. По условию алгоритма, дописываются только '11' или '00'. Значит, 117 не может быть результатом работы алгоритма.
3. R = 120. В двоичной системе это 1111000.
• Последние два разряда: '00'. Это значит, что сумма цифр исходного числа N была четной.
• Уберем последние два разряда: 111100.
• Сумма цифр числа 111100: 1 + 1 + 1 + 1 + 0 + 0 = 4. Сумма четная.
• Согласно правилу, если сумма цифр четная, дописываются '00'. Это совпадает.
• Переведем двоичное число 111100 в десятичную систему: \( 1 x 2^5 + 1 x 2^4 + 1 x 2^3 + 1 x 2^2 + 0 x 2^1 + 0 x 2^0 = 32 + 16 + 8 + 4 = 60 \).
• Таким образом, исходное число N = 60. Его двоичная запись — 111100. Сумма цифр равна 4 (четная), поэтому дописываем '00'. Получаем 11110000, что в десятичной системе равно 120.

Проверим меньшие числа, которые могут быть результатом работы алгоритма и больше 114.

Наименьшее число, которое больше 114, является результатом работы алгоритма:

Если N — двоичное число, а R — результат, то R = N + 2 бита.

Ищем двоичное число, которое оканчивается на '00' или '11', и при отбрасывании этих двух последних цифр, сумма цифр исходного числа будет соответствовать последним двум цифрам.

Проверим числа, которые больше 114:

• 115 = 1110011 (двоичное). Не заканчивается на 00 или 11.
• 116 = 1110100 (двоичное). Заканчивается на '00'. Убираем '00' -> 11101. Сумма цифр 1+1+1+0+1 = 4 (четная). По правилу, если сумма четная, дописываем '00'. Это совпадает. Значит, 116 является возможным результатом.
• 117 = 1110101 (двоичное). Не заканчивается на 00 или 11.
• 118 = 1110110 (двоичное). Не заканчивается на 00 или 11.
• 119 = 1110111 (двоичное). Заканчивается на '11'. Убираем '11' -> 11101. Сумма цифр 1+1+1+0+1 = 4 (четная). По правилу, если сумма четная, дописываем '00'. А у нас '11'. Не подходит.
• 120 = 1111000 (двоичное). Заканчивается на '00'. Убираем '00' -> 11110. Сумма цифр 1+1+1+1+0 = 4 (четная). По правилу, если сумма четная, дописываем '00'. Это совпадает. Значит, 120 является возможным результатом.

Наименьшее число, которое больше 114 и может являться результатом работы алгоритма, это 116.

Однако, 116 не представлен в вариантах ответа. Вернемся к анализу предложенных вариантов.

R = 120 (1111000₂). Сумма цифр 1+1+1+1 = 4 (четная). Дописываем '00'. Получаем 11110000₂, что равно 120.

R = 117 (1110101₂). Последние цифры '01' невозможны по правилу.

R = 115 (1110011₂). Сумма цифр 1+1+1+0+0+1 = 4 (четная). Должны были дописаться '00', а дописалось '11'. Не подходит.

Единственный вариант, который может быть результатом работы алгоритма, — это 120.

Ответ: 120