Структурное программирование

Лекция 8

Между детальной схемой алгоритма и программой есть вполне однозначное соответствие, поэтому структура алгоритма полностью определяет структуру и характеристики программы. Если не накладывать никаких ограничений на алгоритм, то программа может иметь хаотическую структуру в ней может быть много безусловных переходов (операторы GOTO), что затрудняет чтение и понимание программы и увеличивает затраты на отладку.

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

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

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

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

- использование ряда правил и ограничений на допустимые конструкции алгоритма;

- применение метода проектирования «сверху вниз» при разработке алгоритма;

- использование специальных приемов при составлении программы для повышения ее читабельности (сдвиг функционально законченных фрагментов программы друг относительно друга, включение комментариев и т.п.).

- применение метода параллельной разработки алгоритма и программы.

Кроме требований рассмотренных выше СП накладывает следующие ограничения на алгоритм:

- алгоритм решения задачи должен представлять собой совокупность только допустимых конструкций;

- схема алгоритма должна содержать минимальное число параллельных ветвей; каждый функционально законченный фрагмент алгоритма должен иметь только один вход и один выход;

- каждая подпрограмма должна выполнять только одну функцию и причем целиком.

Теоретические основы СП были разработаны еще в 1965 г. В соответствии со структурной теоремой итальянских математиков К. Бом и Г. Джакопини, всякий алгоритм, а следовательно и программа могут быть построены с использованием только трех управляющих структур:

- следование;

- развилка;

- повторение.

В структурном программировании используется еще и конструкция ВЫБОР. Основным компонентом этих конструкций является функциональный блок с одним входом и одним выходом, внутри которого записывается действие по обработке информации.

Рис.3.8.1.

3.6.1. Конструкция следование.

Эта управляющая конструкция изображается в виде последовательности функциональных блоков, соединенных стрелками (рис.3.8.1), и означает, что управление передается от предыдущего блока к последующему. Так как каждый функциональный блок имеет один вход и один выход, то сложное действие, изображенное в виде одного функционального блока, может бать представлено в виде последовательности более простых действий. Аналогично последовательность функциональных блоков может быть заменена одним функциональным блоком. Это важное свойство конструкций СП позволяет легко делать преобразования алгоритма.

3.6.2. Конструкция развилка.

Эта управляющая конструкция предназначена для выбора одного из двух возможных альтернативных путей выполнения алгоритма в зависимости от некоторого условия Р (рис.3.8.2). При выполнении этой конструкции сначала проверяется

Рис.3.8.2

логическое условие, записанное в условном блоке, значения которого могут быть ИСТИНА или ЛОЖЬ. В случае истинного значения условия управление передается функциональному блоку, расположенному по пути ДА, иначе управление передается блоку, расположенному по пути НЕТ.

В любом случае после выполнения той или иной функции управление передается к одной точке выхода данной конструкции.

Рис.3.8.3.

Допускается, что одна из ветвей конструкции РАЗВИЛКА может быть пустой, обычно пустой делают ветвь по пути НЕТ. Пример такой конструкции приведен на рис.3.8.3.

3.6.3. Конструкция выбор.

Эта конструкция предназначена для оформления фрагментов алгоритма, в которых вычислительный процесс в некоторой точке разветвляется по нескольким параллельным путям. Форма конструкции "Выбор" приведена на рис.3.8.4. В данном случае СВ – селектор варианта; МВ1, МВ2 …MBn – метки вариантов. В зависимости от значения управляющей переменной (СВ) управление передается функции, метка варианта которой совпадает совпадает Рис. 3.8.4. со значением селектора варианта СВ. После реализации функции осуществляется выход из данной конструкции.

Рис.3.8.5.

3.6.4. Конструкция повторение.

Конструкция Повторение предназначена для обозначения многократно повторяющихся действий. Такие процессы принято называть циклическими (или просто циклами). В структурном программировании предусмотрено использование двух конструкций ПОВТОРЕНИЕ, цикла с предуслвием и цикла с постусловием.

Принцип действия.

В цикле с предусловием (рис.3.8.5) сначала проверяется условие окончания цикла, и если оно истинно, то выполняется тело цикла, после выполнения которого осуществляется возврат к проверке условия окончания цикла. Эти действия выполняются до тех пор, пока условие Р не станет ложным. В этом случае выполнение тела цикла прекращается и осуществляется выход из цикла по пути НЕТ.

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

Рис.3.8.6

В цикле с постусловием (рис.3.8.6) сначала выполняется тело цикла (блок R), а затем проверяется условие окончания цикла. В зависимости от значения Р, либо снова выполняется блок R, либо осуществляется выход из цикла.

В этой конструкции независимо от начального значения условия Р тело цикла всегда выполняется хотя бы один раз.

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

Замечание. Алгоритм приведенный на рис.3.8.7, дает неправильный результат, если N=0 и первый элемент массива А не равен нулю.

Рис.3.8.7

Что дает использование конструкций СП?

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

Если предположить, что имеется готовая схема алгоритма решения некоторой задачи, составленная из конструкций СП, то заменяя отдельные конструкции на функциональные блоки, можно свернуть весь алгоритм к одному функциональному блоку (РИС.). Это позволяет решить и обратную задачу: представив алгоритм решения задачи в виде одного функционального блока, последовательно раскрывать его и получающиеся функциональные блоки с помощью конструкций СП до тех пор пока не получим детальную схему алгоритма.

При разработке алгоритма методом СП работа выполняется в два этапа.

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

2. На втором этапе разрабатываются алгоритмы полученных элементарных функций. Здесь надо придумать, как представить тот или иной метод реализации функции в виде схемы алгоритма.

Дата добавления: 2014-01-03