Основные структуры алгоритмов: сравнительный анализ и примеры их использования

Любой алгоритм содержит описание команд и определяет последовательность их выполнения. На первый взгляд кажется, что все команды алгоритма всегда выполняются одна за другой, однако это не так. Для обеспечения такого свойства алгоритма, как массовость, его строят с учетом любого набора допустимых входных данных. Поэтому во многих случаях нельзя заранее предусмотреть, каким должен быть следующий шаг алгоритма. Отсюда возникает потребность в таких инструкциях исполнителю, которые позволят управлять его действиями по сложившейся ситуации в процессе выполнения алгоритма.
По характеру управления различают три основных вида структуры алгоритмов: линейные, с разветвлением и с повторением (циклический).
В простейшем случае алгоритм приписывает единовременное выполнение всех по очереди заданных действий независимо от значений входных данных задачи. Например, для нахождения объема призмы нужно найти площадь ее основания, определить высоту призмы, найти их произведение. Эти действия нужно выполнить для расчета объема любой призмы.
Сложнее с управлением справляются алгоритмы, которые предусматривают два возможных варианта действий.
Выбор варианта связывается с некоторым условием. Например, алгоритм решения квадратного уравнения подразумевает сначала нахождение значения дискриминанта, а затем, в зависимости от знака, или вывод сообщения об отсутствии действительных корней (если значение дискриминанта отрицательное), или нахождение их по соответствующим формулам (в противном случае).
Алгоритм, который подразумевает выполнение тех или иных действий в зависимости от результата проверки условия, называется алгоритмом с разветвлением, или разветвленным.
Хотя такой алгоритм содержит описание действий для обоих возможных вариантов, при каждом его выполнении реализуется только один из них, который именно — зависит от заданного набора входных данных. Итак, в отличие от линейного алгоритма, алгоритм с разветвлением приписывает выполнение не всех без исключения действий, а только тех, которые выбраны по условию.
Третий вид алгоритмов составляют предусматривающие возможность повторного выполнения определенной последовательности действий.
Например, для подсчета суммы двух целых чисел (в столбик) необходимо сначала вычислить сумму последних цифр чисел-слагаемых, записать последнюю цифру результата и перенести, если нужно, единицу в следующий разряд. Далее по аналогичному правилу нужно вычислить сумму предпоследних цифр чисел-слагаемых и т. д. Процедура повторяется, пока все цифры чисел не будут исчерпаны. Количество повторений зависит от количества цифр в заданных числах.
Алгоритм, который приписывает повторное выполнение действий, называется алгоритмом с повторением, или алгоритмом с циклом (циклический). Повторяющееся действие или группа действий называется телом цикла. Количество повторений тела цикла определяется поставленным условием, которое называется условием цикла. По результатам проверки условия осуществляется выбор: еще раз повторить тело цикла или перейти к другим действиям.
Циклический алгоритм состоит из следующих этапов:
1. Подготовка цикла – осуществление действий, которые связаны с исходными данными;
2. Описание тела цикла – осуществление многократных действий для вычисления искомых величин, а также создание значений, необходимых для повторного выполнения действий в теле цикла;
3. Условия продолжения цикла — действия, которые определяют необходимость дальнейшего выполнения тела цикла.
Наличие возврата к ранее выполненным действиям является характерным отличием алгоритмов с циклами от линейных и разветвленных.
Все рассмотренные нами базовые алгоритмические структуры — линейная, разветвление, повторение — являются замкнутыми, каждая из них имеет один вход и один выход. Это позволяет рассматривать базовые структуры как целостные единицы и использовать любую из них как элемент другой. Другими словам, базовые структуры можно соединять последовательно и вкладывать друг в друга.
Например, в базовой структуре следования (рис. 4) функциональный блок Действие 1 может быть замещен разветвлением, а блок Действие 2 — повторением. Такое замещение можно продолжать дальше и дальше.
Рекурсивным называется алгоритм, который в ходе работы на любом шаге прямо или косвенно вызывает сам себя.
При решении многих задач применяется особый набор стандартных приемов алгоритмизации. Среди них выделим и проанализируем те, которые наиболее широко применяются при решении задач на практике.
Комбинированные алгоритмы. При решении задач достаточно часто происходит так, что алгоритм их решения подразделяется на части, фрагменты и каждая часть является алгоритмом одного из трех описанных выше типов. Алгоритм, который содержит несколько структур одновременно, называется комбинированным.
Все перечисленные алгоритмические структуры или же их комбинации могут быть использованы при составлении алгоритма сложной задачи.
Вложенные циклы. Отдельным случаем комбинированных алгоритмов являются алгоритмы, в которых необходимо задействовать несколько видов циклов, которые одновременно сменяются друг за другом. Например, внутри одного цикла могут находиться один или несколько других циклов. Такие комбинации носят название вложенный цикл. Охватываемый цикл называется внешним, а вложенные в него циклы — внутренними (вложенными), при этом область действия внутреннего цикла должна полностью находиться в области внешнего цикла, то есть циклы не могут мешать работе друг друга.
Алгоритм, сконструированный исключительно из базовых структур, называется структурным.
Теоретически доказано, что для задачи любой логической сложности можно сконструировать структурный метод.