Основные типы структур алгоритмов
Одним из системных методов разработки алгоритмов является метод структурной алгоритмизации. Этот метод основан на визуальном представлении алгоритма в виде последовательности управляющих структурных фрагментов. Выделяют три базовые управляющие процессом обработки информации структуры: композицию, альтернативу и итерацию. С помощью этих структур можно описать любые процессы обработки информации.
Композиция (следование) - это линейная управляющая конструкция, не содержащая альтернативу и итерацию. Она предназначена для описания единственного процесса обработки информации.
Альтернатива - это нелинейная управляющая конструкция, не содержащая итерацию. Она предназначена для описания различных процессов обработки информации, выбор которых зависит от значений входных данных.
Итерация - это циклическая управляющая структура, которая содержит композицию и ветвление. Она предназначена для организации повторяющихся процессов обработки последовательности значений данных.
В соответствии с наличием в алгоритмах управляющих структур композиции, альтернативы и итерации алгоритмы классифицируют на: линейные (структура «следование»), разветвленные (структура «разветвление») и циклические (структура «повторение») алгоритмы.
Структура «Следование»
Данная структура предполагает последовательное расположение блоков и групп блоков. В программе она реализуется последовательным размещением операторов (рисунок 3.4).
Рисунок 3.4 Структура «Следование»
Действия могут быть отдельным оператором, вызовом с возвратом некоторой процедуры, другой управляющей структурой.
Структура «Разветвление»
Данная структура применяется, когда в зависимости от заданного условия нужно выполнить либо одно, либо другое действие (рисунок 3.5).
Рисунок 3.5 Структура «Разветвление»
Проверка «Условие?» представляется предикатом, т.е. функцией, задающей логическое выражение или условие, значением которого может быть истина («+») или ложь («-»). Эта структура может быть неполной, когда отсутствует действие, выполняемое при ложном (или истинном) значении логического выражения (рисунок 3.6).
Рисунок 3.6 Неполная структура «Разветвление»
Структура «Повторение»
Эту структуру часто называют циклом. Она имеет два варианта построения.
Структура цикла «До». Данная структура применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого заданного условия (рисунок 3.7).
Рисунок 3.7 Структура цикла «До»
«Действие» будет повторяться до тех пор, пока значение предиката «Условие» будет оставаться истинным. Поэтому в «Действии» должно изменяться значение переменных, от которых зависит значение, по которому проверяется «Условие». В противном случае произойдет зацикливание. Вычисление предиката производится до начала выполнения «Действия» и может случиться так, что оно не будет выполняться ни разу.
Данный тип цикла называют также циклом с постусловием или итерационным.
Структура цикла «Пока». Данная структура отличается от структуры цикла «До» тем, что проверка условия производится до выполнения тела цикла (рисунок 3.8).
Рисунок 3.8 Структура цикла «Пока»
Повторение типа «Пока» всегда выполняется хотя бы один раз. «Действие» перестает выполняться, как только предикат становится ложным.
Данный тип цикла называют также циклом с предусловием.
Если цикл имеет определенное количество повторений, его называют арифметическим. Он может быть реализован как при помощи структуры цикла «До», так и структуры цикла «Пока», но графически он описывается с использованием блока «цикл».
Арифметический цикл. В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (K) значений параметра и шагом его изменения (h). Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра равно К (рисунок 3.9).
Рисунок 3.9 Структура арифметического цикла
В реальных задачах может встретиться любое число циклов. Обозначив цикл квадратной скобкой, схематично представим варианты взаимного расположения циклов (рисунок 3.10).
а) б) в)
Рисунок 3.10 Расположение циклов а) последовательные, б) вложенные, в) запрещенные
Структура «Множественный выбор». Множественный выбор является обобщением разветвления, когда в зависимости от значения переменной I выполняется одно из нескольких действий S1, S2, …, Sn (рисунок 3.11).
Рисунок 3.11 Структура «Множественный выбор»
Структура выбор полезна в том случае, когда требуется выбрать одну из нескольких альтернатив.
Комбинированные алгоритмы. Структурный подход предполагает использование только нескольких основных структур (линейных, ветвящихся, циклических), комбинации которых дает все многообразие алгоритмов.
Особенностью всех приведенных структур является то, что они имеют один вход и один выход, и их можно соединить друг с другом в любой последовательности. В частности, каждая структура может содержать любую другую структуру в качестве одного из блоков.
Обычно при составлении схемы блоки размещаются друг под другом в порядке их выполнения. Возврат осуществляется только на циклах. Это дает простую и наглядную структуру алгоритма, по которому легко составить программу.