Разбор задания №22 ЕГЭ-2019 по информатике и ИКТ

Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще проекта) КИМ ЕГЭ по информатике.

Часть 1

Задание 22

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

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

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

3. Прибавить 3

Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.

Программа для Вычислителя – это последовательность команд.

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.

Ответ: ___________________________.

Решение

Для начала решим задачу просто, без учета дополнительного условия «содержит число 11»:

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

Выпишем все числа от стартового и до последнего включительно. Под первым напишем 1. Двигаясь слева направо, рассмотрим число способов попадания в текущую позицию, используя данные нам команды.

Сразу можно убрать очевидные позиции, не влияющие на решение: 3 можно зачеркнуть – понятно, что в нее нельзя попасть из стартовой позиции, используя одну из доступных нам команд; 10 – через нее мы не можем никак попасть в нашу промежуточную, а главное, обязательную позицию 11.

В 4 мы можем попасть двумя путями-командами: х2 и +2, т.е. через 4 проходят 2 пути. Напишем это значение под 4. В 5 можно попасть единственным способом: +3. Напишем под 5 значение 1. В 6 можно попасть единственным путем – через 4. А под ней у нас указано значение 2. Соответственно, именно по этим двум путям, проходя 4, мы попадем из 2 в 6. Пишем под 6 значение 2. В 7 можно попасть из двух предыдущих позиций, используя имеющиеся у нас команды, и для получения числа путей, которые нам доступны для попадания в 7, мы сложим числа, которые указывали под этими предыдущими позициями. Т.е. в 7 мы попадаем 2 (из-под 4) + 1 (из-под 5) = 3 путями. Действуя по этой схеме и далее, получаем:

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

Двигаясь и далее слева направо, мы получаем искомый результат – 100.

Ответ: 100.