СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до 12.07.2025

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Задание 22 ЕГЭ по информатике

Категория: Информатика

Нажмите, чтобы узнать подробности

Примеры решения типовых задач задания 22 ЕГЭ по информатике. Задание 22 является заданием повышенного уровня сложности. Обобщение опыта преподавания данного материала.

Просмотр содержимого документа
«Задание 22 ЕГЭ по информатике»

Задание 22 ЕГЭ по информатике

Условие задачи сводятся к тому, что существует некий исполнитель, который умеет выполнять несколько команд (система команд исполнителя – СКИ). Необходимо найти количество программ, преобразующих число А в число В.

Задание 22 претерпело изменения на протяжении нескольких лет присутствия в КИМ ЕГЭ по информатике.

На данный момент задачи можно разделить на несколько групп:

  1. Задачи без ограничения условий (приведенный выше вариант).

  2. Задачи с ограничением первого типа: траектория прохождения содержит число N.

  3. Задачи с ограничением второго типа: траектория вычислений не содержит число M.

  4. Задачи с ограничением первого и второго типов: траектория прохождения содержит число N и не содержит число M.

На своих уроках все эти типы задач я стараюсь разобрать на одном примере. Просто так получается быстрее, так как часть задачи уже решена, и нагляднее. Я не претендую на свою методику решения данных задач, а просто хочу обобщить свой опыт, который, надеюсь, может кому-то пригодится. При подготовке учащихся к сдаче ЕГЭ пользуюсь материалами сайта К.Ю. Полякова.

Задачу, которая приводится ниже , взяла из книги Крылов С.С., Чуркина Т.Е., ЕГЭ 2017. Информатика и ИКТ. Типовые экзаменационные варианты. 10 вариантов




Задача

Исполнитель Счетчик преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

  1. Прибавить 2

  2. Умножить на 2

Первая команда увеличивает число на экране на 2, вторая умножает его на 2. Программа для исполнителя Счетчик это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 44 и при этом траектория вычислений содержит число 18 и не содержит числа 34?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 6, 12, 14.

KN – количество разных программ для получения числа N из начального числа.

Построим рекуррентную формулу, связывающую KN с предыдущими элементами последовательности K1, K2, K3,…, KN-1, то есть с решениями таких же задач для меньших N.

Число N могло быть получено одной из двух операций:

  • увеличением на 2 числа N-2;

  • увеличением в 2 раза числа N/2.


Рекуррентная формула: KN = KN-2 + KN/2


Я задаю одну рекуррентную формулу и для четных и для нечетных чисел, т.к. можно считать, что для чисел нечетных KN/2 = 0. То же самое можно сказать и про KN при N меньших начального числа (KN = 0).

В нашем примере нечетные числа мы вообще получить не можем.


Будем решать данную задачу в несколько этапов, рассматривая следующие варианты:

  1. 2 – 44

  2. 2 – 44, содержит 18

  3. 2 – 44, не содержит 34

  4. 2 – 44, содержит 18 и не содержит 34.


На самом деле, это 4 разных задачи. Просто их удобно рассматривать вместе.


  1. Задача 1: 2 – 44

По рекуррентной формуле имеем:

K2 = 1

K4 = K2 + K2 = 1 + 1 + 2

K6 = K4 + K3 = 2 + 0 = 2

K8 = K6 + K4 = 2 + 2 = 4

K10 = K8 + K3 = 4 + 0 = 4

K12 = K10 + K6 = 4 + 2 = 6 = K14

K16 = K14 + K8 = 6 + 4 = 10 = K18

K20 = K18 + K10 = 10 + 4 = 14 = K22

K24 = K22 + K12 = 14 + 6 = 20 = K26

K28 = K26 + K14 = 20 + 6 = 26 = K30

K32 = K30 + K16 = 26 + 10 = 36 = K34

K36 = K34 + K18 = 36 + 10 = 46 = K38

K40 = K38 + K20 = 46 + 14 = 60 = K42

K44 = K42 + K22 = 60 + 14 = 76


  1. Задача 2: 2 – 44, содержит 18

Эта задача разбивается на две задачи: 2 – 18 и 18 – 44.

Первая у нас уже решена выше. Мы можем получить число 18 десятью способами.

Дальше мы решаем вторую задачу: 18 – 44, считая, что всех предыдущих вычислений не было. Т.е. все KN для N


K18 =10

K20 = K18 + K10 = 10 + 0 = 10 = K22

K24 = K22 + K12 = 10 + 0 = 10 = K26

K28 = K26 + K14 = 10 + 0 = 10 = K30

K32 = K30 + K16 = 10 + 0 = 10 = K34

K36 = K34 + K18 = 10 + 10 = 20 = K38

K40 = K38 + K20 = 20 + 10 = 30 = K42

K44 = K42 + K22 = 30 + 10 = 40


  1. Задача 3: 2 – 44, не содержит 34

В э той задаче траектория не может проходить через число 34, поэтому считаем, что K34 = 0 Дальше вычисления ведем обычным способом.


Использую первую задачу, получим:


K32 = K30 + K16 = 26 + 10 = 36

K34 = 0

K36 = K34 + K18 = 0 + 10 = 10 = K38

K40 = K38 + K20 = 10 + 14 = 24 = K42

K44 = K42 + K22 = 24 + 14 = 38


  1. Задача 4: 2 – 44, содержит 18 и не содержит 34

Объединяем задачи 2 и 3. Доходим до получения 18 из 2, обнуляем все предыдущие значения, потом из 18 получаем 32, обнуляем K34 , и далее считаем обычным образом.


K18 =10

K20 = K18 + K10 = 10 + 0 = 10 = K22

K24 = K22 + K12 = 10 + 0 = 10 = K26

K28 = K26 + K14 = 10 + 0 = 10 = K30

K32 = K30 + K16 = 10 + 0 = 10

K34 = 0

K36 = K34 + K18 = 0 + 10 = 10 = K38

K40 = K38 + K20 = 10 + 10 = 20 = K42

K44 = K42 + K22 = 20 + 10 = 30


Мы рассмотрели все 4 варианта данной задачи.

В 2017 году в задании 22 появился еще один тип задач. В условие задачи говорится о том, что предпоследней командой является какая-то определенная команда из СКИ.

Следующую задачу я взяла с сайта К.Ю. Полякова. Задача № 51, задание 22.

Задача

Исполнитель Калькулятор преобразует целое число, записанное на экране. У исполнителя две команды, каждой команде присвоен номер:

1. Прибавь 1

2. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза. Сколько существует программ, которые число 5 преобразуют в число 32 и в которых предпоследняя команда 1?


Решение

В условии задачи сказано, что предпоследняя команда 1. Последняя команда может быть любая – 1 или 2. Это означает, что нужно рассмотреть и получить количество всех команд вида «*11» и «*12» . Звездочка означает любую последовательность команд.

Если две последние команды «11», то до выполнения этих команд у нас было число 32 – 1 – 1 = 30. Это значит, что нам нужно получить количество команд преобразующих 5 в 30.

Если две последние команды «12», то до выполнения этих команд у нас было число 32/2 – 1 = 15. Это значит, что нам нужно получить количество команд преобразующих 5 в 15.


Число N могло быть получено одной из двух операций:

  • увеличением на 1 числа N-1;

  • умножением на 2 числа N/2 (только для четных N)


Запишем общую рекуррентную формулу: KN = KN-1 + KN/2

Если N нечетное, то считаем, что KN/2 = 0.

Далее решаем задачу обычным способом: 5 – 30


K5 = 1

K6 = K5 + K3 = 1 + 0 = 1 = K7

K8 = K7 + K4 = 1 + 0 = 1 = K9

K10 = K9 + K5 = 1 + 1 = 2 = K11

K12 = K11 + K6 = 2 + 1 = 3 = K13

K14 = K13 + K7 = 3 + 1 = 4 = K15

K16 = K15 + K8 = 4 + 1 = 5 = K17

K18 = K17 + K9 = 5 + 1 = 6 = K19

K20 = K19 + K10 = 6 + 2 = 8 = K21

K22 = K21 + K11 = 8 + 2 = 10 = K23

K24 = K23 + K12 = 10 + 3 = 13 = K25

K26 = K25 + K13 = 13 + 3 = 16 = K27

K28 = K27 + K14 = 16 + 4 = 20 = K29

K30 = K29 + K15 = 20 + 4 = 24


Решая эту задачу, мы решили и вторую задачу: узнали, что число 15 мы можем получить 4 способами.

Складываем полученные результаты: 24 + 4 = 28.


Ответ: существует 28 программ, которые число 5 преобразуют в число 32 и в которых предпоследняя команда 1.




Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!

Поделитесь с друзьями
ВКонтактеОдноклассникиTwitterМой МирLiveJournalGoogle PlusЯндекс