Понятная информатика,

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

(базовый уровень, примерное время решения – 4 минуты). 

Есть вопросы и замечания - пишите!

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

 

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

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

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

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

 

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

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

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

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

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

 

Решение:

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

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

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

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

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

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

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

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

Ответ: 19

 

Пример 2  (1426)

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

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

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

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

 

Решение:

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

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

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

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

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

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

• 0 – верно, так как количество единиц в числе N нечетно;
• 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 = 11000012), 10 (98 = 11000102)  и  11 (99=11000112)  также не подходят. Это значит, что нужно увеличивать само число N, тогда получаем N = 11001₂  и в результате работы алгоритма получим  R = 1100110₂   = 102.

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

Ответ: 25

 

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

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

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

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

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

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

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

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

                  98 = 2^₆ + 2^₅ + 2¹ =  1100010₂

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

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

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

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

                   99= 2⁶ + 2⁵ + 2¹ + 2⁰ =  1100011₂

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

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

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

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

                100= 2⁶ + 2⁵ + 2² =  1100100₂

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

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

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

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

                101= 2⁶ + 2⁵ + 2² +  2⁰ = 1100101₂

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

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

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

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

                102= 2⁶ + 2⁵ + 2² +  2¹ =  1100110²

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

• 1 – верно, так как количество единиц в числе N нечетно
• 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:

                         R_min  = 24 =  10000₂

                         R_max = 25 =  100000₂

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

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

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

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

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

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

Ответ: 5

 

Пример 5 (4846).

Автомат обрабатывает натуральное число N < 256 по следующему алгоритму:
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