§ 5. Основные сведения об алгоритмах

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

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

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

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

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

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

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

Дискретность нужна, чтобы решение можно было выполнять последовательно и проверять по шагам. Определённость нужна для воспроизводимости: при одинаковых исходных данных и условиях исполнитель не должен произвольно выбирать, как трактовать команду. Если написать «прибавь немного», величина прибавления не задана. Точное указание, например «прибавь 2», устраняет неоднозначность.

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

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

Форма записи зависит от того, кому предназначен алгоритм и насколько точно нужно передать действия. Словесное описание удобно для объяснения человеку, но длинный текст иногда трудно проверять на однозначность. Блок-схема наглядно показывает порядок действий и ветвления, а алгоритмический язык помогает записать их строго. Язык программирования используют, когда команды должен выполнить компьютер.

Формы представления алгоритма

Сравнивайте формы по двум вопросам: как именно в них задаются действия и кто будет читать или выполнять описание. Для краткого объяснения человеку часто достаточно слов, а для сложного алгоритма полезна схема или строгая запись. Компьютеру нужны команды на языке программирования, который он может обработать.

Разбор задач

Задача 1. Составить алгоритм вычисления периметра прямоугольника по заданным длине a и ширине b. Сначала выделим входные данные, затем применим формулу периметра P = 2 · (a + b). Запись будет понятна исполнителю, если он умеет принять два числа, вычислять сумму и умножать на 2.

1. Получить значения a и b.
2. Вычислить сумму a + b.
3. Умножить полученную сумму на 2 и присвоить значение переменной P.
4. Вывести P.

Ответ: алгоритм состоит из ввода длины и ширины, вычисления P = 2 · (a + b) и вывода результата. Для a = 3 и b = 5 он даст P = 16. При вводе нужно учитывать условие задачи: длина и ширина должны быть допустимыми значениями.

Задача 2. Описать алгоритм определения большего из двух введённых чисел x и y. Здесь недостаточно выполнить одни и те же вычисления при любых входных данных: нужно проверить, какое число больше. Результат сравнения определяет, какую из команд вывода выполнить, то есть возникает ветвление.

1. Ввести числа x и y.
2. Сравнить x и y.
3. Если x > y, вывести x; иначе, если y > x, вывести y.
4. Если числа равны, сообщить, что они равны.

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

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

1. Ввести n и присвоить S значение 0.
2. Для каждого из n чисел проверить условие: число > 0.
3. Если условие выполнено, прибавить число к S; если нет — оставить S без изменений.
4. После обработки всех чисел вывести S.

Ответ: итоговая сумма содержит только положительные элементы последовательности. Цикл должен выполнить ровно n проверок и завершиться, поэтому важно корректно учесть количество элементов. Если n = 0 и такой случай разрешён, ни одно число не обрабатывается, а ответом будет начальное значение S = 0.

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

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

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

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

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

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

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

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

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