Задание 22 ЕГЭ по информатике
Условие задачи сводятся к тому, что существует некий исполнитель, который умеет выполнять несколько команд (система команд исполнителя – СКИ). Необходимо найти количество программ, преобразующих число А в число В.
Задание 22 претерпело изменения на протяжении нескольких лет присутствия в КИМ ЕГЭ по информатике.
На данный момент задачи можно разделить на несколько групп:
Задачи без ограничения условий (приведенный выше вариант).
Задачи с ограничением первого типа: траектория прохождения содержит число N.
Задачи с ограничением второго типа: траектория вычислений не содержит число M.
Задачи с ограничением первого и второго типов: траектория прохождения содержит число N и не содержит число M.
На своих уроках все эти типы задач я стараюсь разобрать на одном примере. Просто так получается быстрее, так как часть задачи уже решена, и нагляднее. Я не претендую на свою методику решения данных задач, а просто хочу обобщить свой опыт, который, надеюсь, может кому-то пригодится. При подготовке учащихся к сдаче ЕГЭ пользуюсь материалами сайта К.Ю. Полякова.
Задачу, которая приводится ниже , взяла из книги Крылов С.С., Чуркина Т.Е., ЕГЭ 2017. Информатика и ИКТ. Типовые экзаменационные варианты. 10 вариантов
Задача
Исполнитель Счетчик преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Прибавить 2
Умножить на 2
Первая команда увеличивает число на экране на 2, вторая умножает его на 2. Программа для исполнителя Счетчик это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 44 и при этом траектория вычислений содержит число 18 и не содержит числа 34?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 6, 12, 14.
KN – количество разных программ для получения числа N из начального числа.
Построим рекуррентную формулу, связывающую KN с предыдущими элементами последовательности K1, K2, K3,…, KN-1, то есть с решениями таких же задач для меньших N.
Число N могло быть получено одной из двух операций:
Рекуррентная формула: KN = KN-2 + KN/2
Я задаю одну рекуррентную формулу и для четных и для нечетных чисел, т.к. можно считать, что для чисел нечетных KN/2 = 0. То же самое можно сказать и про KN при N меньших начального числа (KN = 0).
В нашем примере нечетные числа мы вообще получить не можем.
Будем решать данную задачу в несколько этапов, рассматривая следующие варианты:
2 – 44
2 – 44, содержит 18
2 – 44, не содержит 34
2 – 44, содержит 18 и не содержит 34.
На самом деле, это 4 разных задачи. Просто их удобно рассматривать вместе.
Задача 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
Задача 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
Задача 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
Задача 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 могло быть получено одной из двух операций:
Запишем общую рекуррентную формулу: 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.