13.1. Алгоритм и алгоритмические конструкции

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

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

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

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

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

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

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

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

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

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

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

Основные алгоритмические конструкции

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

Разбор задач

1. Периметр прямоугольника

Условие: даны длина a и ширина b прямоугольника. Требуется найти его периметр. Здесь все действия заранее известны, поэтому используется следование.

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

Ответ: алгоритм заканчивается после вычисления периметра P. Например, при a = 5 и b = 3 получится P = 2 · (5 + 3) = 16.

2. Сравнение двух чисел

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

1. Получить значения a и b.
2. Проверить условие a > b.
3. Если оно истинно, сообщить, что больше a, и закончить алгоритм.
4. Иначе проверить условие a < b.
5. Если оно истинно, сообщить, что больше b, а в противном случае сообщить о равенстве.

Ответ: алгоритм выдаёт ровно один результат из трёх вариантов. Например, для a = 7 и b = 4 срабатывает первая ветвь, поэтому сообщается, что больше первое число.

3. Сумма чисел от 1 до n

Условие: дано натуральное число n. Нужно найти сумму 1 + 2 + 3 + … + n. Повторение позволяет не записывать отдельную команду для каждого слагаемого.

1. Присвоить сумме S значение 0, а счётчику i — значение 1.
2. Пока i ≤ n, прибавлять i к S.
3. После каждого сложения увеличивать i на 1.
4. Когда i станет больше n, вывести S.

Ответ: при n = 4 действия дадут S = 0 + 1 + 2 + 3 + 4 = 10. Изменение счётчика необходимо для окончания цикла.

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

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

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

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

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

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

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

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

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

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