Задачи на исполнителей
Задачи на исполнителей решают не угадыванием, а последовательным моделированием: фиксируют начальное состояние, выполняют команды по порядку и проверяют условие задачи. Такой подход подходит для числовых, координатных и графических исполнителей, а также для программ с циклами и ветвлениями.
Что дано в задаче
В условии обычно указаны исполнитель, его система команд, начальное состояние и алгоритм. Начальное состояние может включать число на экране, координаты, направление движения, содержимое ёмкостей или положение на клетчатом поле. Нужно определить результат работы алгоритма, найти неизвестное начальное значение или выяснить, при каких параметрах достигается нужное состояние.
Исполнитель — объект, который умеет выполнять только команды из своей системы команд. Команды имеют точный смысл, поэтому нельзя заменять их «похожими» действиями или добавлять операции, которых нет в условии.
Результат работы алгоритма определяется тремя составляющими: начальным состоянием, последовательностью команд и точным толкованием каждой команды. Если хотя бы одна составляющая понята неверно, итог может оказаться неправильным.
- Выписать все данные и обозначить неизвестные величины.
- Уточнить, что меняет каждая команда и что она не меняет.
- Развернуть сокращённую запись алгоритма: циклы, повторы, ветвления.
- Выполнить команды по шагам, записывая состояние после каждого существенного действия.
- Проверить итог по условию и ограничениям задачи.
Как описывать состояние исполнителя
Состояние удобно представлять набором переменных. Например, для числового исполнителя достаточно \(x\); для исполнителя на плоскости нужны координаты \((x,y)\) и, если это важно, направление; для переливаний — объёмы воды в сосудах. Если команда изменяет только одну величину, остальные сохраняются.
Здесь \(S_i\) — состояние перед \(i\)-й командой, \(c_i\) — команда, а \(F_{c_i}\) — действие этой команды. Формула означает: новое состояние получают применением текущей команды к предыдущему состоянию.
Составляйте таблицу с номерами шагов. В строке записывайте только изменившиеся величины, но периодически фиксируйте полное состояние. Для движения полезно рисовать траекторию; для координатных задач поможет страница координатная система исполнителя.
| Шаг | Команда | Состояние до | Состояние после |
|---|---|---|---|
| 0 | — | \(x=x_0\) | \(x_0\) |
| 1 | прибавь \(a\) | \(x_0\) | \(x_0+a\) |
| 2 | умножь на \(b\) | \(x_0+a\) | \(b(x_0+a)\) |
Если исполнитель перемещается, сначала выясните, как команда задаёт направление и расстояние. При наличии препятствий отдельно учитывайте правило остановки или запрета движения; такие случаи разобраны на странице препятствие исполнителя. При построении пути важно различать конечное положение и всю траекторию исполнителя.
Циклы, параметры и обратный ход
Команда «повтори \(n\) раз» означает ровно \(n\) последовательных выполнений вложенной последовательности. При \(n=0\) команды внутри цикла не выполняются. Если число повторений зависит от условия, нужно определить, сколько раз условие истинно, не путая это число с количеством проверок.
Для одинаковой команды \(F\), повторённой \(n\) раз, итоговое состояние обозначают \(F^n(S_0)\). В числовых исполнителях повторение прибавления \(a\) даёт \(x_n=x_0+na\), а повторение умножения на \(q\) — \(x_n=x_0q^n\).
Параметр — число или другой элемент записи команды, определяющий её действие: величина сдвига, число повторений, номер направления. Не следует путать параметр команды с начальным значением исполнителя: параметр задаёт действие, а начальное значение — исходное состояние.
Если требуется найти начальное число, действуйте в обратном порядке: отменяйте команды справа налево. Для команды «прибавь \(a\)» обратной будет операция «вычти \(a\)», для «умножь на \(q\)» — деление на \(q\) при \(q\ne0\). Однако обратный ход допустим только после точного выяснения всех выполненных команд.
Исполнитель начинает с \(x=3\) и дважды выполняет команду «умножь на 2», затем «прибавь 1». Каково итоговое значение?
Разобранный пример
Исполнитель работает с числом \(x\). Команда 1 увеличивает число на 3, команда 2 умножает его на 2. Алгоритм: повторить 2 раза: команда 1, команда 2. После этого выполнить команду 1. Известно, что результат равен 38. Найдём начальное значение \(x\).
Внутри цикла выполняется одна и та же пара действий: сначала прибавление 3, затем умножение на 2. Эту пару нужно применить два раза, а затем ещё раз прибавить 3.
Проверка решения Ответ
Проверим прямым выполнением: \(4{,}25\to7{,}25\to14{,}5\to17{,}5\to35\to38\). Все команды выполнены в правильном порядке, поэтому начальное значение равно \(4{,}25\).
В заданиях экзамена начальное значение часто должно быть целым или удовлетворять дополнительному ограничению. Тогда после решения уравнения обязательно проверьте допустимость ответа. Если алгоритм содержит параметр команды, его также следует учитывать как неизвестную величину или перебрать возможные значения.
Перебор и проверка вариантов
Когда формула получается сложной, а диапазон параметров невелик, безопаснее выполнить перебор. Для каждого варианта задайте начальное состояние, запустите алгоритм и проверьте условие. Перебор особенно удобен в задачах с остатками, ограничениями на координаты, препятствиями и несколькими ветвлениями.
- Проверить крайние значения диапазона.
- Отдельно рассмотреть нулевое число повторений.
- Убедиться, что деление на ноль или выход за границы невозможны.
- Сравнить результат ручного решения с одним-двумя прямыми прогонами.
1) Выполняют команды не слева направо. 2) Считают «повтори 3 раза» как три дополнительных повтора после первого выполнения. 3) Забывают последнюю команду вне цикла. 4) Меняют координату или направление, хотя команда этого не делает. 5) Подставляют параметр вместо начального состояния. 6) Останавливают алгоритм при промежуточном неудобном результате, хотя условие не требует остановки.
Для поиска ошибки полезны локализация ошибки в алгоритме и случайное тестирование. Если программа должна работать для разных входных данных, проверяйте не один удачный пример, а несколько классов случаев: ноль, отрицательные значения, границы диапазона и обычное значение. Такой подход связан с тестированием классов эквивалентности.
Особые виды задач
В задачах на перемещение часто требуется найти не только конечную точку, но и длину пути, число посещённых клеток или факт попадания на линию. Для этого применяйте правила перемещения исполнителя и не сокращайте путь до одного вектора, если важен порядок движения.
В задачах с сосудами состояние записывают как \((a,b,...)\), где значения не превышают вместимости сосудов. Каждая операция должна сохранять общий объём воды, если вода не добавляется и не выливается. Для таких задач удобно использовать метод переливаний: перечислять состояния и переходы между ними.
Быстрая проверка
Проверьте себя
Главное
- Исполнитель действует только по заданной системе команд, начиная с указанного состояния.
- Каждый шаг нужно выполнять в точном порядке; циклы разворачивают по числу повторений.
- Состояние удобно записывать таблицей, формулой или набором координат и объёмов.
- При поиске начального значения можно отменять команды в обратном порядке, но итог обязательно проверяют прямым прогоном.
- Перебор и тестирование помогают обнаружить ошибки в циклах, параметрах, границах и трактовке команд.