Средства описания структурных алгоритмов




План темы

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-форм и диаграмм Насси-Шнейдермана является сложность построения изображений символов, что усложняет практическое применение этих нотаций для описания больших алгоритмов.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: