План темы
1. Основные и дополнительные алгоритмические структуры.
2. Средства описания структурных алгоритмов.
Основные и дополнительные алгоритмические структуры
Одним из способов обеспечения высокого уровня технологичности разрабатываемого программного обеспечения является структурное программирование.
Различают три вида вычислительного процесса, реализуемого программами: линейный, разветвленный и циклический.
Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности.
Разветвленная структура процесса вычислений предполагает, что конкретная последовательность операций зависит от значений одной или нескольких переменных.
Циклическая структура процесса вычислений предполагает, что для получения результата некоторые действия необходимо выполнить несколько раз.
После того, как в 60-х годах XX в. было доказано, что любой алгоритм можно представить с использованием трех основных управляющих конструкций, в языках программирования высокого уровня появились управляющие операторы для реализации соответствующих конструкций. Эти три конструкции принято считать базовыми. К ним относят:
- следование – обозначает последовательное выполнение действий;
- ветвление – соответствует выбору одного из двух вариантов действий;
- цикл-пока – определяет повторение действий, пока не будет нарушено некоторое условие, выполнение которого проверяется в начале цикла.
Помимо базовых конструкций, языки программирования высокого уровня обычно используют еще три конструкции, которые можно составить из базовых конструкций:
- выбор – обозначает выбор одного варианта из нескольких в зависимости от значения некоторой величины;
- цикл-до – обозначает повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле;
- цикл с заданным числом повторений (счетный цикл) – обозначает повторение некоторых действий указанное количество раз.
Эти шесть конструкций были положены в основу структурного программирования.
Рис. 1. Базовые конструкции: а – следование; б – ветвление; в – цикл-пока
Рис. 2. Дополнительные конструкции: а – выбор; б – цикл-до; в – счетный цикл
Программы, написанные с использованием только структурных операторов передачи управления, называют структурными.
Представление алгоритма программы в виде блок-схемы с точки зрения структурного программирования имеет два недостатка:
- предполагает слишком низкий уровень детализации, что часто скрывает суть сложных алгоритмов;
- позволяет использовать неструктурные способы передачи управления, причем часто в блок-схеме они выглядят проще, чем эквивалентные структурные.
Кроме блок-схем, для описания алгоритмов можно использовать псевдокоды, Flow-формы и диаграммы Насси-Шнейдермана.
Средства описания структурных алгоритмов
Псевдокоды. Псевдокод – формализованное текстовое описание алгоритма (текстовая нотация).
Использование псевдокодов ориентирует только на структурные способы передачи управления и потому требует более тщательного анализа разрабатываемого алгоритма. Псевдокоды хорошо согласуются с основным методом структурного программирования – методом пошаговой детализации.
Таблица 1. Псевдокоды
Задача. В векторе A(n) найти заданное число y.
Ввести n
Для i=1,n,1
Ввести A[i]
Ввести у
i: =1
Цикл-пока i?n и A[i]?у
i:=i+l
Все-цикл
Если i?n
то Вывести «Элемент найден»
иначе Вывести «Элемент не найден»
Все-если
Flow-формыпредставляют собой графическую нотацию описания структурных алгоритмов, которая иллюстрирует вложенность структур. Каждый символ Flow-формы соответствует управляющей структуре и изображается в виде прямоугольника. Для демонстрации вложенности структур символ Flow-формы может быть вписан в соответствующую область прямоугольника любого другого символа. В прямоугольниках символов содержится текст на естественном языке или в математической нотации. Размер прямоугольника определяется длиной вписанного в него текста и размерами вложенных прямоугольников.
На рис. 3 представлен фрагмент поискового цикла с использованием Flow-формы.
Рис. 3. Алгоритм поискового цикла
Диаграммы Насси-Шнейдермана являются развитием Flow-форм. Основное их отличие от Flow-форм заключается в том, что область обозначения условий и вариантов ветвления изображают в виде треугольников (рис. 4). Такое обозначение обеспечивает большую наглядность представления алгоритма.
Рис. 4. Условные обозначения диаграмм Насси-Шнейдермана для основных конструкций: а – следование; б – ветвление; в – выбор; г – цикл-пока; д – цикл-до
Графические нотации лучше отображают вложенность конструкций, чем псевдокоды.
Недостатком Flow-форм и диаграмм Насси-Шнейдермана является сложность построения изображений символов, что усложняет практическое применение этих нотаций для описания больших алгоритмов.
