Исполнители в информатике: задачи с решениями
Исполнитель в информатике это воображаемый робот, который понимает несколько команд. Задачи на исполнителей встречаются в ОГЭ и ЕГЭ каждый год: выполнить программу, найти кратчайшую, посчитать, сколько программ ведут к нужному числу. Разбираем все типы на примерах и показываем, как проверить ответ на Python.
Для 7–11 классов. Номера заданий сверяйте с демоверсией своего года.
Выполнить программу
Исполнитель Калькулятор умеет две команды: 1) прибавь 3; 2) умножь на 2. Программа записывается номерами команд.
Задача
Какое число получится из 1 после программы 12121?
1: 1 + 3 = 4.
2: 4 · 2 = 8.
1: 8 + 3 = 11.
2: 11 · 2 = 22.
1: 22 + 3 = 25.
Ответ: 25.
Здесь главное не торопиться и выполнять команды строго по порядку. Удобно записывать промежуточные числа в строчку над номерами команд.
Кратчайшая программа
Теперь команды другие: 1) прибавь 1; 2) умножь на 2. Нужно получить из 3 число 22 за наименьшее число команд.
Задача
Найдите кратчайшую программу из 3 в 22.
Удобно идти с конца: заменять команды обратными. Из чётного числа делим пополам, из нечётного вычитаем 1.
22 чётное: 22 : 2 = 11. 11 нечётное: 11 − 1 = 10. 10 : 2 = 5. 5 − 1 = 4. 4 − 1 = 3.
Пять шагов. Читаем в обратном порядке: прибавь 1, прибавь 1, умножь на 2, прибавь 1, умножь на 2.
Проверка: 3 → 4 → 5 → 10 → 11 → 22.
Можно ли за 4 команды? Число 22 получается либо из 11, либо из 21. Число 11 нечётное, его можно получить только из 10, а 21 только из 20. Значит, за 2 команды нужно было бы получить 10 или 20. Но из 3 за 2 команды получаются только 5, 8, 7 и 12. Значит, 5 команд минимум.
Ответ: 11212.
Обратный ход работает не всегда: иногда выгоднее отнять 1, даже если число чётное. Поэтому для уверенности короткие варианты стоит проверить перебором, как в последнем шаге.
Сколько существует программ
Самый частый тип в ЕГЭ: сколько существует программ, которые переводят одно число в другое. Решается таблицей, где для каждого числа записывают количество способов до него добраться.
Задача
Сколько существует программ из команд «прибавь 1» и «умножь на 2», которые переводят число 2 в число 12?
В число x можно попасть из x − 1 командой «прибавь 1» и, если x чётное, из x/2 командой «умножь на 2». Значит, f(x) = f(x − 1) + f(x/2), а для нечётных только f(x − 1).
f(2) = 1. f(3) = 1. f(4) = f(3) + f(2) = 2. f(5) = 2.
f(6) = f(5) + f(3) = 3. f(7) = 3. f(8) = f(7) + f(4) = 5. f(9) = 5.
f(10) = f(9) + f(5) = 7. f(11) = 7. f(12) = f(11) + f(6) = 10.
Ответ: 10 программ.
Важно: f(x/2) учитываем, только если x/2 не меньше начального числа. Например, для 4 мы прибавили f(2), а для 2 не прибавляем f(1): из 1 мы не стартуем.
Если в условии есть «траектория должна проходить через 8» или «не должна содержать 10», таблицу считают в две части или обнуляют запрещённое число. На компьютерном ЕГЭ удобно проверить себя кодом.
n = 12 f = [0] * (n + 1) f[2] = 1 for x in range(3, n + 1): f[x] = f[x - 1] if x % 2 == 0 and x // 2 >= 2: f[x] += f[x // 2] print(f[n])
Программа выводит 10. Как решать на Python и другие задания ЕГЭ, разобрали в статье о переборе на Python.
Черепаха
Исполнитель Черепаха оставляет след на экране. Команды: «Вперёд n» сдвигает на n шагов, «Направо m» поворачивает на m градусов. «Повтори k [команды]» повторяет команды k раз.
Задача
Какую фигуру нарисует программа «Повтори 6 [Вперёд 10 Направо 60]»?
Шесть одинаковых отрезков и шесть поворотов по 60°.
Всего поворот 6 · 60° = 360°, черепаха вернулась в начало.
Это правильный шестиугольник со стороной 10.
Ответ: правильный шестиугольник.
Общее правило: чтобы нарисовать правильный n-угольник, поворот должен быть 360° : n. Треугольник 120°, квадрат 90°, пятиугольник 72°. Если поворот такой, что 360 на него не делится, черепаха нарисует звезду или фигуру, которая не замкнётся за указанное число повторов.
Задача
Сколько повторов нужно в программе «Повтори k [Вперёд 5 Направо 45]», чтобы фигура замкнулась?
360 : 45 = 8.
Ответ: 8, получится правильный восьмиугольник.
В ЕГЭ встречаются задачи, где нужно посчитать точки с целыми координатами внутри фигуры, нарисованной Черепахой. Их удобно решать, нарисовав фигуру по клеткам или повторив команды в модуле turtle на Python.
Советы
- Выполнять программы на бумаге, записывая каждое промежуточное значение.
- Для кратчайшей программы идти с конца и проверять короткие варианты перебором.
- Для количества программ строить таблицу от начального числа к конечному.
- На компьютерном экзамене проверять ответ коротким кодом.
Разберём на занятии
Занимаемся по всем школьным предметам с 4 по 11 класс: живые занятия, общая доска и домашка, которую проверяет тот же преподаватель.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Почему в таблице f(2) = 1?
Из 2 в 2 ведёт одна программа: пустая, без команд. С неё и начинается подсчёт. Это частый вопрос, и без этого шага таблица не заработает.
Есть ли исполнители в ОГЭ?
Да, в ОГЭ есть задания на исполнение простого алгоритма и на исполнителя с несколькими командами. Они проще, чем в ЕГЭ, но идея та же: выполнять команды строго по порядку.