ЕГЭ – 2021, задание 5, часть 3. Элементы теории алгоритмов: бит четности и др. Практика

ЕГЭ – 2021, задание 5, часть 2. Элементы теории алгоритмов: бит четности и др.

При решении заданий 5 ЕГЭ-2021, часть 2 рассматриваются несколько типов задач на алгоритмизацию. При этом нужно учесть,, что алгоритм - это четкий порядок действий, подлежащих выполнению, то есть при решении задач на алгоритмизацию следует внимательно читать условие задачи и точно, аккуратно и без спешки (в этом залог быстрого и точного решения задачи!) выполнять описанные в нем действия.

При этом обратим внимание, что одни и те же действия в разных задачах могут описываться разными условиями, например:

- "складываются все цифры двоичной записи числа" или "считается количество единиц в двоичной записи числа": поскольку сумма цифр двоичной записи числа равна количеству единиц в двоичном числе, то при решении задач быстрее и проще посчитать количество единиц в записи и получить результат для данного условия;

- "остаток от деления суммы (количества единиц) на два", "бит чётности", "четное число или нет" - в результате проверки всех этих условий проверяется остаток от деления числа на 2: по умолчанию это ноль для четного числа и единица - для нечетного. Но в условии задач этот результат может меняться, поэтому следует точно выполнять действия, заданные в алгоритме!

Следует также внимательно смотреть, какое из чисел – N или R – следует искать в данной задаче.

Пример 1 (ДЕМО – 2021)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

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

1. складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

2. над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.

Решение:

Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:

1. Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 77) - число 78:

78 = 2⁶ + 2³ + 2² + 2¹ = 1001110₂

1. Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма

N = 10011₂ и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 1 – верно, так как количество единиц в числе N равно трем;

2. 0 – верно, так как теперь в полученном результате уже 4 единицы.

Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 10011₂ и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:

N = 10011₂ = 2⁰ + 2¹ + 0² + 0³ + 2⁴ = 1 + 2 + 16 = 19.

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

Ответ: 19

Пример 2 (1426)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

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

1. в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;

2. к этой записи справа дописывается остаток от деления количества единиц на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Решение:

Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:

1. Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 31) - число 32:

32 = 2⁵ = 100000₂

1. Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 1000₂ и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 0 – верно, так как количество единиц в числе N нечетно;

2. 0 – неверно, так как остаток от деления количества единиц на 2 равен 1.

Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число искомое число R = 33 и проверяем его.

1. Переведем число 33 в двоичную систему счисления: 33 = 2⁵ = 100001₂

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

отделяем от него справа две последние цифры (которые являются результатом

выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 1000₂

и цифры 01, которые получены в результате двух следующих шагов выполнения

алгоритма:

1. 0 – верно, так как количество единиц в числе N нечетно;

2. 1 – верно, так как результат от деления количества единиц на 2 равен 1.

Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 11000₂ и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:

N = 110011₂ = 2⁰ + 2¹ + 0² + 0³ + 2⁴ = 1 + 2 + 16 = 19.

Ответ: 33

Пример 3 (1431)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.

3. К полученному результату дописывается ещё один бит чётности.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 96. В ответе это число запишите в десятичной системе.

Решение 1 – короткое:

Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:

Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) - число 97:

97 = 2⁶ + 2⁵ + 2⁰ = 1100001₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и получаем, что для числа N = 11000₂ последними цифрами должны быть 00, но тогда число R = 1100000₂ = 96 не удовлетворяет условию задачи.

Числа с двумя последними цифрами 01 (97 = 1100001₂), 10 (98 = 1100010₂) и 11 (99=1100011₂) также не подходят. Это значит, что нужно увеличивать само число N, тогда получаем N = 11001₂ и в результате работы алгоритма получим R = 1100110₂ = 102.

Тогда искомое число N = 11001₂ = 25

Ответ: 25

Решение 2 – длинное (обычное):

Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:

1. Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) - число 97:

97 = 2⁶ + 2⁵ + 2⁰ = 1100001₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11000₂ и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 0 – верно, так как количество единиц в числе N четно;

2. 1 –неверно, так как количество единиц в числе N четно.

Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число R = 98 и проверяем его.

1. Переведем в двоичную систему число 98:

98 = 2⁶ + 2⁵ + 2¹ = 1100010₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11000₂ и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 1 – неверно, так как количество единиц в числе N четно;

2. 0 – неверно, так как количество единиц в числе N нечетно.

Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 99 и проверяем его.

1. Переведем в двоичную систему число 99:

1. = 2⁶ + 2⁵ + 2¹ + 2⁰ = 1100011₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11000₂ и цифры 11, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 1 – неверно, так как количество единиц в числе N четно

2. 1–верно, так как количество единиц в числе N нечетно.

Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 100 и проверяем его.

1. Переведем в двоичную систему число100:

1. = 2⁶ + 2⁵ + 2² = 1100100₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11001₂ и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 0 – неверно, так как количество единиц в числе N нечетно

2. 0 – неверно, так как количество единиц в числе N нечетно.

Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 101 и проверяем его.

1. Переведем в двоичную систему число 101:

1. = 2⁶ + 2⁵ + 2^{2 +} 2⁰ = 1100101₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11001₂ и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 0 – неверно, так как количество единиц в числе N нечетно

2. 1 – верно, так как количество единиц в числе N нечетно.

Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 102 и проверяем его.

1. Переведем в двоичную систему число 102:

1. = 2⁶ + 2⁵ + 2^{2 +} 2¹ = 1100110₂

Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 11001₂ и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:

1. 1 – верно, так как количество единиц в числе N нечетно

2. 0 – верно, так как количество единиц в числе N четно.

Так как оба условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 10011₂ и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:

N = 11001₂ = 2⁰ + 0¹ + 0² + 2³ + 2⁴ = 1 + 8 + 16 = 25.

Ответ: 25

Пример 4 (4796)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Складываются все цифры двоичной записи числа. Если сумма четная, то в конец числа (справа) дописывается 1, а если нечетная, то дописывается 0. Например, запись числа 10 преобразуется в запись 100;
3) К полученному результату применяется еще раз пункт 2 этого алгоритма.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество чисел R, которые могут быть получены в результате работы этого алгоритма, и лежат в диапазоне 16 ≤ R ≤ 32.

Решение:

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

Переведем в двоичную систему первое число, удовлетворяющее условию задачи границы диапазона возможных чисел R:

Rmin = 2⁴ = 10000₂

Rmax = 2⁵ = 100000₂

Соответственно получаем Nmin = 2² = 100₂ и Nmax = 2³ = 1000_2.

Далее берем все возможные числа N внутри данного диапазона (возможны только три варианта – 101, 110 и 111) и проверяем результат работы алгоритма над ними:

при N = 101₂ возможно только одно R = 10110₂ = 22

при N = 110₂ возможно только одно R = 11010₂ = 26

при N = 111₂ возможно только одно R = 11100₂ = 28

Тогда всего получаем 5 подходящих чисел.

Ответ: 5

Пример 5 (4846).

Автомат обрабатывает натуральное число N
1) Строится восьмибитная двоичная запись числа N–1.
2) Инвертируются разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого числа N результат работы алгоритма равен 113?

Решение:

Переводим число 113 в двоичную систему счисления и получаем

N - 1 = 2⁶ + 2⁵ + 2⁴ + 2⁰ = 1110001₂

Дополняем его до восьми бит и инвертируем:

N - 1 = 01110001₂ = 10001110₂ = 2¹ + 2² + 2³+ 2⁷ = 142, тогда N = 142 + 1= 143.

Ответ: 143