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

Решение:

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

1. Строим двоичную запись числа N.
2. К двоичной записи N добавляем два разряда справа по правилу:
   • Первый разряд: сумма цифр двоичной записи N, взятая по модулю 2 (остаток от деления на 2).
   • Второй разряд: сумма цифр получившейся записи (после добавления первого разряда), взятая по модулю 2.
3. Полученную двоичную запись R переводим в десятичную систему.

Нам нужно найти минимальное число R > 75. Начнём с числа 76 и будем проверять, может ли оно быть результатом работы алгоритма. Это означает, что нам нужно найти такое число N, чтобы после применения алгоритма получилась двоичная запись числа R.

Переведём число 76 в двоичную систему:

\( 76 = 64 + 8 + 4 = 2^6 + 2^3 + 2^2 \)

Двоичная запись 76: \( 1001100 \).

Теперь будем обратным ходом искать N. Отбросим два последних разряда двоичной записи R, чтобы получить двоичную запись N.

Проверяем числа, близкие к 76:

R = 77 (двоичная запись \( 1001101 \))

Если отбросить последние два разряда (01), получим \( 10011 \).

Переведём \( 10011_2 \) в десятичную систему:

\( 1 · 2^4 + 0 · 2^3 + 0 · 2^2 + 1 · 2^1 + 1 · 2^0 = 16 + 0 + 0 + 2 + 1 = 19 \)

Итак, N = 19. Проверим, как алгоритм построит R для N = 19.

Двоичная запись N = 19: \( 10011_2 \).

Шаг 2а: Сумма цифр N = \( 1+0+0+1+1 = 3 \). Остаток от деления на 2 = \( 3 · 2 = 1 \). Дописываем 1: \( 100111 \).

Шаг 2б: Сумма цифр \( 100111 \) = \( 1+0+0+1+1+1 = 4 \). Остаток от деления на 2 = \( 4 · 2 = 0 \). Дописываем 0: \( 1001110 \).

Получили двоичную запись R = \( 1001110_2 \).

Переведём \( 1001110_2 \) в десятичную систему:

\( 1 · 2^6 + 0 · 2^5 + 0 · 2^4 + 1 · 2^3 + 1 · 2^2 + 1 · 2^1 + 0 · 2^0 = 64 + 0 + 0 + 8 + 4 + 2 + 0 = 78 \)

Мы нашли число R = 78, которое больше 75. Может ли быть меньшее число? Проверим R = 76.

R = 76 (двоичная запись \( 1001100 \))

Отбросив последние два разряда (00), получим \( 10011 \). Это N = 19.

Проверим алгоритм для N = 19:

Двоичная запись N = 19: \( 10011_2 \).

Шаг 2а: Сумма цифр N = 3. Остаток = 1. Дописываем 1: \( 100111 \).

Шаг 2б: Сумма цифр \( 100111 \) = 4. Остаток = 0. Дописываем 0: \( 1001110 \).

Получили R = \( 1001110_2 \) = 78. Значит, 76 не может быть результатом работы алгоритма, так как он должен быть получен из N=19, а из N=19 получается 78.

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

Рассмотрим двоичные записи, которые заканчиваются на 00, 01, 10, 11.

Если R заканчивается на 00, то N заканчивается на 00. Сумма цифр N должна быть чётной. После добавления остатка от деления суммы цифр на 2 (т.е. 0) к N, сумма цифр новой записи должна быть чётной (чтобы добавился 0).

Если N = \( 100100 \) (76), то сумма цифр = 3 (нечётная). Алгоритм даст R = 78.

R = 78 (двоичная запись \( 1001110 \)).

Отбрасываем 10, получаем N = \( 100111 \) (55).

Проверим N = 55:

Двоичная запись N = 55: \( 110111_2 \).

Шаг 2а: Сумма цифр = \( 1+1+0+1+1+1 = 5 \). Остаток = 1. Дописываем 1: \( 1101111 \).

Шаг 2б: Сумма цифр = \( 1+1+0+1+1+1+1 = 6 \). Остаток = 0. Дописываем 0: \( 11011110 \).

\( 11011110_2 \) = \( 128 + 64 + 0 + 16 + 8 + 4 + 2 + 0 = 222 \).

Этот путь не подходит. Вернёмся к R = 77. Мы получили N = 19, но R=77, а полученное R=78.

Давайте будем перебирать N и строить R.

N = 19 (\( 10011_2 \)) → R = 78 (\( 1001110_2 \))

N = 20 (\( 10100_2 \))

Сумма цифр N = 2. Остаток = 0. Дописываем 0: \( 101000 \).

Сумма цифр \( 101000 \) = 2. Остаток = 0. Дописываем 0: \( 1010000 \).

R = \( 1010000_2 \) = 64 + 16 = 80.

Это больше 75. R = 80 — возможный результат.

N = 21 (\( 10101_2 \))

Сумма цифр N = 3. Остаток = 1. Дописываем 1: \( 101011 \).

Сумма цифр \( 101011 \) = 4. Остаток = 0. Дописываем 0: \( 1010110 \).

R = \( 1010110_2 \) = 64 + 16 + 4 + 2 = 86.

N = 18 (\( 10010_2 \))

Сумма цифр N = 2. Остаток = 0. Дописываем 0: \( 100100 \).

Сумма цифр \( 100100 \) = 2. Остаток = 0. Дописываем 0: \( 1001000 \).

R = \( 1001000_2 \) = 64 + 8 = 72. (Меньше 75)

N = 19 → R = 78. Это первое число больше 75, которое мы получили.

Проверим, может ли быть R = 77. Если R = 77 (\( 1001101 \)), то N = \( 10011 \) = 19. Для N=19 мы получили R=78.

Значит, минимальное число R, превышающее 75, является 78.

Ответ: 78