8.1. Понятие алгоритма

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

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

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

Система команд исполнителя — набор команд, которые исполнитель умеет понимать и выполнять. Например, у простого исполнителя-перемещателя в неё могут входить команды «вверх», «вниз», «влево» и «вправо». Зная систему команд, можно записать алгоритм так, чтобы исполнитель действительно смог пройти его от начала до конца.

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

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

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

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

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

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

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

Основные свойства алгоритма

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

Разбор задач

Задача: составить алгоритм для нахождения суммы двух введённых чисел. Исходные данные — два числа, а результат — их сумма. Сначала нужно получить оба значения, затем выполнить сложение и сообщить ответ, иначе исполнитель не узнает ни данные, ни требуемое действие.

1. Ввести первое число и сохранить его.
2. Ввести второе число и сохранить его.
3. Сложить сохранённые числа.
4. Сообщить полученную сумму.

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

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

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

Например, если нужно пройти две клетки вправо и одну вверх, записываем «вправо», «вправо», «вверх». Ответ: используется только система команд исполнителя, а последовательность заканчивается в нужной клетке.

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

1. Ввести числа a, b и c.
2. Если a больше b, считать текущим наибольшим числом a; иначе считать им b.
3. Сравнить текущее наибольшее число с c и, если c больше, заменить его на c.
4. Сообщить текущее наибольшее число.

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

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

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

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

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

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

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

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

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

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

• Алгоритм предназначен для решения задачи.
• Алгоритм состоит из отдельных команд.
• Команды выполняются в заданном порядке.
• Команды должны быть понятны исполнителю.
• Алгоритм должен завершаться за конечное число шагов.
• Массовый алгоритм подходит для группы однотипных задач.