Top.Mail.Ru
Персональный сайт учителя информатики Звездиной Веры Алексеевны

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

или Давайте учиться дружно!

Смотреть презентацию
Смотреть презентацию
Смотреть презентацию
Скачать презентацию
Скачать презентацию
Читать
Смотреть и скачать

Практикум для подготовки к ЕГЭ – 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 = 26 + 23 + 22 + 21 =  10011102

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

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

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

 N = 100112  = 20 + 21 + 02 + 03 + 24 =  1 + 2 + 16 = 19.

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

Ответ: 19

 

Пример 2  (1426)

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

  1. Строится двоичная запись числа N.
  2. К этой записи дописываются справа ещё два разряда по следующему правилу:
  • в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;
  • к этой записи справа дописывается остаток от деления количества единиц на 2.

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

 

Решение:

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

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

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

     1.  Переведем число 33 в двоичную систему счисления:   33 = 25 + 1 =  1000012

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

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

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

         N = 1100112  = 20 + 21 + 02 + 03 + 24 =  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 = 26 + 25 + 20 =  11000012

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

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

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

Ответ: 25

 

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

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

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

                         97 = 26 + 25 + 20 =  11000012

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

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

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

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

                  98 = 26 + 25 + 21 =  11000102

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

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

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

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

                   99= 26 + 25 + 21 + 20 =  11000112

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

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

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

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

                100= 26 + 25 + 22 =  11001002

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

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

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

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

                101= 26 + 25 + 22 +  20 = 11001012

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

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

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

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

                102= 26 + 25 + 22 +  21 =  11001102

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

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

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

                N = 110012  = 20 + 01 + 02 + 23 + 24  = 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  = 24 =  100002

                         Rmax = 25 =  1000002

Соответственно получаем Nmin = 22 = 1002  и  Nmax = 23 =  10002.

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

        при N = 1012  возможно только одно R = 101102 =  22

        при N = 1102  возможно только одно  R = 110102 =  26

        при N = 1112  возможно только одно  R = 111002 = 28

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

Ответ: 5

 

Пример 5 (4846).

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

 

Решение:

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

      N - 1 = 26 + 25 + 24 + 20  = 11100012

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

      N - 1 = 011100012  => 100011102 = 21 + 22 + 23+ 27  = 142, тогда N = 142 + 1= 143.

Ответ: 143

© 2018–2022   Звездина Вера Алексеевна, v_zvezdina@mail.ru

SSL