Задание 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.

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

Построим рекуррентную формулу, связывающую K_N с предыдущими элементами последовательности K₁, K₂, K₃,…, K_N-1, то есть с решениями таких же задач для меньших N.

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

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

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

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

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

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

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

1. 2 – 44

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

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

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

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

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

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

K₂ = 1

K₄ = K₂ + K₂ = 1 + 1 + 2

K₆ = K₄ + K₃ = 2 + 0 = 2

K₈ = K₆ + K₄ = 2 + 2 = 4

K₁₀ = K₈ + K₃ = 4 + 0 = 4

K₁₂ = K₁₀ + K₆ = 4 + 2 = 6 = K₁₄

K₁₆ = K₁₄ + K₈ = 6 + 4 = 10 = K₁₈

K₂₀ = K₁₈ + K₁₀ = 10 + 4 = 14 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 14 + 6 = 20 = K₂₆

K₂₈ = K₂₆ + K₁₄ = 20 + 6 = 26 = K₃₀

K₃₂ = K₃₀ + K₁₆ = 26 + 10 = 36 = K₃₄

K₃₆ = K₃₄ + K₁₈ = 36 + 10 = 46 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 46 + 14 = 60 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 60 + 14 = 76

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

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

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

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

K₁₈ =10

K₂₀ = K₁₈ + K₁₀ = 10 + 0 = 10 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 10 + 0 = 10 = K₂₆

K₂₈ = K₂₆ + K₁₄ = 10 + 0 = 10 = K₃₀

K₃₂ = K₃₀ + K₁₆ = 10 + 0 = 10 = K₃₄

K₃₆ = K₃₄ + K₁₈ = 10 + 10 = 20 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 20 + 10 = 30 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 30 + 10 = 40

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

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

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

K₃₂ = K₃₀ + K₁₆ = 26 + 10 = 36

K₃₄ = 0

K₃₆ = K₃₄ + K₁₈ = 0 + 10 = 10 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 10 + 14 = 24 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 24 + 14 = 38

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

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

K₁₈ =10

K₂₀ = K₁₈ + K₁₀ = 10 + 0 = 10 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 10 + 0 = 10 = K₂₆

K₂₈ = K₂₆ + K₁₄ = 10 + 0 = 10 = K₃₀

K₃₂ = K₃₀ + K₁₆ = 10 + 0 = 10

K₃₄ = 0

K₃₆ = K₃₄ + K₁₈ = 0 + 10 = 10 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 10 + 10 = 20 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 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)

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

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

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

K₅ = 1

K₆ = K₅ + K₃ = 1 + 0 = 1 = K₇

K₈ = K₇ + K₄ = 1 + 0 = 1 = K₉

K₁₀ = K₉ + K₅ = 1 + 1 = 2 = K₁₁

K₁₂ = K₁₁ + K₆ = 2 + 1 = 3 = K₁₃

K₁₄ = K₁₃ + K₇ = 3 + 1 = 4 = K₁₅

K₁₆ = K₁₅ + K₈ = 4 + 1 = 5 = K₁₇

K₁₈ = K₁₇ + K₉ = 5 + 1 = 6 = K₁₉

K₂₀ = K₁₉ + K₁₀ = 6 + 2 = 8 = K₂₁

K₂₂ = K₂₁ + K₁₁ = 8 + 2 = 10 = K₂₃

K₂₄ = K₂₃ + K₁₂ = 10 + 3 = 13 = K₂₅

K₂₆ = K₂₅ + K₁₃ = 13 + 3 = 16 = K₂₇

K₂₈ = K₂₇ + K₁₄ = 16 + 4 = 20 = K₂₉

K₃₀ = K₂₉ + K₁₅ = 20 + 4 = 24

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

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

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