§ 32. Оптимальные программы

Определения и обозначения

Оптимальная программа — программа, которая выполняет заданную задачу и использует наименьшее число команд по выбранному критерию. Это не обязательно самый короткий текст: сначала нужно уточнить, что именно считаем — команды в записи или действия исполнителя. Определение помогает сравнивать варианты не на глаз, а по понятному правилу.

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

Корректная программа — программа, которая при заданных условиях приводит исполнителя к требуемому результату. Для проверки нужно проследить выполнение её команд от начального состояния до конца. Это позволяет не считать удачной программу, которая короче, но ведёт не туда.

Система команд исполнителя — набор команд, которыми можно управлять исполнителем при составлении программы. Исполнитель понимает только команды из этого набора и выполняет их по заданным правилам. Поэтому способ сокращения программы зависит от того, какие команды ему доступны.

Как это устроено

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

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

Когда несколько программ решают задачу, их сравнивают по одному и тому же критерию. Можно посчитать команды в записи, а можно отдельно проследить, сколько действий совершит исполнитель. Эти числа не всегда совпадают: одна команда цикла в тексте может означать несколько повторений. Поэтому выражение «самая короткая программа» требует уточнения — короткая по записи или по работе исполнителя.

Если исполнитель много раз делает одно и то же, повторяющийся фрагмент можно заменить циклом, когда цикл предусмотрен системой команд. Например, вместо трёх одинаковых команд можно указать одну команду и число повторений. Запись станет компактнее, однако исполнитель всё равно выполнит действие три раза. Цикл полезен для сокращения текста, но не обязательно уменьшает число действий.

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

Сравнение программ для одной задачи

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

Разбор задач

Повторить одну команду три раза

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

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

Ответ. Запись с циклом экономнее по числу команд в тексте, если система команд позволяет такой цикл. По числу действий исполнителя варианты равны: в каждом случае он выполняет команду трижды.

Перемещение вправо, затем вверх

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

1. Вариант 1: команда «вправо» выполняется четыре раза подряд, затем выполняется команда «вверх». Получается четыре шага вправо и один шаг вверх.
2. Вариант 2: цикл повторяет команду «вправо» четыре раза, после цикла выполняется «вверх». Порядок перемещений и их количество остаются прежними.
3. Проверяем оба маршрута от одной начальной клетки: конечная клетка в обоих случаях находится на четыре клетки правее и на одну выше.
4. Считаем команды записи с учётом возможностей языка. Вариант с циклом может быть короче, но число перемещений исполнителя в нём не уменьшается.

Ответ. Оба варианта корректны и приводят к одной клетке. Если критерий — число команд в записи и цикл считается одной командой, выигрывает вариант с циклом; по числу перемещений варианты равны.

Выбрать программу для заданного маршрута

Условие. Для одного маршрута предложено несколько программ: одна использует повторяющийся фрагмент, другая содержит лишние действия. Нужно найти корректную программу с наименьшим числом действий. Точные команды зависят от самого маршрута, поэтому решение строится проверкой каждого кандидата.

1. Записываем начальное положение и требуемый маршрут, чтобы знать, какие перемещения должны произойти.
2. Выполняем каждую программу по командам и отмечаем положение исполнителя после каждого шага. Если полученная конечная точка или путь не соответствует условию, исключаем вариант.
3. Среди оставшихся программ считаем действия исполнителя, включая все повторения внутри циклов. Лишние действия учитываем, даже если они не меняют конечное положение.
4. Сравниваем только корректные программы и выбираем ту, у которой действий меньше. Если требуется сравнить также число команд в записи, это будет отдельный критерий.

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

Типичные ошибки

Не указывать критерий. Нельзя назвать программу оптимальной просто потому, что она выглядит короче: это может быть краткая запись с большим числом действий. Так ошибаются, когда смешивают разные способы сравнения. Проверьте себя: сформулируйте показатель — например, «минимум действий исполнителя» — и сравните все варианты именно по нему.

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

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

Забывать начальные условия и возможности исполнителя. Команда может быть недопустима в конкретном положении, а программа — работать только при определённом старте. Ошибка возникает, если проверяют текст сам по себе, не учитывая исполнителя. Уточните исходное состояние и систему команд, затем выполните все команды по правилам.

Связь с другими темами

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

Что запомнить

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