Моделирование алгоритмической задачи

Моделирование алгоритмической задачи — это перевод условия на точный язык исполнителя. Нужно понять, какие данные поступают на вход, какие команды разрешены, как меняется состояние объекта и что именно требуется получить на выходе.

Зачем моделировать условие

В условии задачи часто описывается ситуация словами: исполнитель перемещается по клеткам, автомат читает символы, программа изменяет переменную или выполняет команды в цикле. До вычислений необходимо отделить существенную информацию от пояснений. Для этого удобно построить модель — упрощённое описание задачи, в котором сохранены все свойства, влияющие на ответ.

1. Прочитайте условие целиком и определите, кто или что выполняет алгоритм.
2. Выпишите начальное состояние: положение, значения переменных, содержимое памяти или состояние автомата.
3. Определите входные данные и ограничения на них.
4. Перечислите команды и условия их выполнения.
5. Сформулируйте, что нужно найти или проверить.
6. Проверьте модель на простом примере.

Полезно вспомнить алгоритм: это конечная последовательность понятных исполнителю команд, приводящая к результату. Если неизвестно, какие команды допустимы, нельзя надёжно рассуждать о решении. Если не определено начальное состояние, нельзя однозначно проследить выполнение.

Четыре элемента модели

В большинстве задач достаточно выделить четыре группы сведений. Они могут быть явно названы в условии или скрыты в описании.

Входные и выходные данные алгоритма помогают не перепутать исходные сведения с ответом. Например, в задаче может быть дана строка, а требуется вывести число содержащихся в ней символов. Строка — вход, количество символов — выход.

Состояние должно быть достаточно подробным, но не перегруженным. Для движения по клетчатому полю обычно нужны координаты \((x,y)\) и направление. Для цикла могут быть нужны текущие значения переменных, но не все уже выполненные команды.

Команды и переходы между состояниями

Каждая команда задаёт переход из одного состояния в другое. Если состояние обозначить \(S\), а команду — \(C\), то новое состояние можно записать как \(S' = C(S)\). В задачах с условиями команда может выполняться только при истинности некоторого условия. В задачах с циклом переход повторяется несколько раз.

При разборе команды задайте три вопроса: что она изменяет, что остаётся неизменным и при каком условии она допустима. Например, команда «перейти вправо» меняет \(x\) на единицу, не меняет \(y\) и может быть запрещена границей поля.

Пошаговый разбор условия

Рассмотрим типичную задачу экзаменационного уровня. Исполнитель начинает с числа \(x=3\). Команда «Прибавь 2» увеличивает \(x\) на 2, а команда «Умножь на 3» заменяет \(x\) на \(3x\). Команды выполняются по одной. Требуется определить, какое число получится после последовательности: «Прибавь 2», «Умножь на 3», «Прибавь 2».

Ответ равен \(17\). Важен порядок: операции выполняются последовательно, поэтому нельзя сначала сложить все прибавления, а затем умножить, если такое преобразование меняет порядок команд.

1x := 3
2x := x + 2
3x := 3 * x
4x := x + 2
5вывести x

Циклы, автоматы и перебор

В циклическом алгоритме состояние включает переменную цикла, накопленный результат и, если необходимо, другие переменные. Для проверки числа повторений полезно отдельно считать итерации: в сложных случаях помогает подсчёт итераций вложенных циклов. Если перебираются все варианты, нужно точно указать множество вариантов и условие отбора; это связано с методом полного перебора.

При описании автомата состоянием служит текущая вершина или режим работы, а входной символ определяет переход. Нужно различать текущее состояние и заключительное состояние: последнее проверяют только после чтения всей входной последовательности. Для таких задач важны детерминированный конечный автомат и заключительное состояние автомата.

Если алгоритм задан рекурсивно, модель должна содержать параметры текущего вызова и условие остановки. Значение, возвращаемое вызовом, не всегда совпадает с количеством вызовов; полезно сравнивать возвращаемое значение рекурсии с пошаговым выполнением. Связь рекурсии с циклом разобрана на странице сравнение рекурсии и итерации.

Стратегия решения на экзамене

• Подчеркнуть начальные значения и ограничения.
• Выписать команды дословно и заменить их математическими действиями.
• Выбрать минимальное, но полное описание состояния.
• Составить таблицу выполнения или цепочку переходов.
• Проверить, соответствует ли найденный результат формулировке вопроса.

В задачах на количество шагов не следует выполнять все действия вручную, если процесс повторяется. Сначала найдите закономерность изменения состояния, затем оцените число повторений. При анализе программы также учитывают классы сложности алгоритмов, но сначала всё равно нужно точно выделить состояние и переходы.