Вопрос 8. Метод булевого признака

⇐ ПредыдущаяСтр 4 из 12Следующая ⇒

Сущность метода булевого признака заключается в следующем. В программу, содержащую циклы, вводится некоторый признак. Начальное значение признака задаётся до цикла. Цикл выполняется, пока признак сохраняет своё исходное значение. Значение признака изменяется при наличии некоторых условий внутри цикла. Рассмотрим применение метода булевого признака на примере преобразования неструктурированной схемы, которую представляет рисунок 3.16.

Схема алгоритма (см. рисунок 3.16) не является структурированной, поскольку входящий в нее цикл (блоки 1, 2, 3) содержит один вход и два выхода. На данной схеме в блоках 1 и 2 записаны некоторые условия, определяющие выполнение того или иного участка вычислений. Данные условия обозначены как номера блоков 1 и 2. Значения 1 и 0 возле выходов символов «Решение» соответствуют логическим значениям «да» и «нет».

В соответствии с рассматриваемым методом в исходную схему вводится признак (например, J). Схема приобретает структурированный вид и легко реализуется конструкциями обобщенного цикла и принятия двоичного решения (рисунок 3.17).

Рисунок 3.17 схематично иллюстрирует шаги последовательности преобразований Бома-Джакопини:

1) блок 4, функциональный блок J: = 1 → блок I;

2) блоки 2, 3, I → блок II;

3) блок 5, функциональный блок J: = 1 → блок III;

4) блоки 1, II, III → блок IV;

5) условный блок (решение) J = 1, блок IV → блок V;

6) блоки J: = 0, V → блок VI.

Иногда можно обойтись без специального признака, используя те условия, которые уже есть в исходной схеме. Например, рассмотренную исходную неструктурированную схему можно представить так, как иллюстрирует рисунок 3.18. На данном рисунке условие «(1 и 2) = 0» означает одновременное равенство нулю условий, записанных в блоках 1 и 2 исходной неструктурированной схемы (см. рисунок 3.16). Таким образом, тело цикла 3 будет выполнено в том случае, если оба условия 1 и 2 не выполняются.

Результирующая схема (см. рисунок 3.18) содержит обобщенный цикл с одним входом и одним выходом и конструкцию If-Then-Else, то есть является структурированной. Следует иметь в виду, что преобразование схемы к структурированному виду без дополнительного признака возможно и эффективно только при небольшом количестве условий.

Достоинства метода булевого признака:

1) компактность, экономичность;

2) топология исходной схемы изменяется незначительно.

Недостаток метода булевого признака:

1) метод предназначен для использования только в циклах.

Вопрос 9. Метод дамке

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

Элементы в самой левой части схемы представляют укрупнённую структуру алгоритма. Затем элементы расширяются вправо по мере разделения каждого элемента на подэлементы.

Чтобы исследовать любую подзадачу, достаточно анализировать только те элементы и управляющие структуры, которые находятся справа от нее.

Основан на идее нисходящего проектирования. Основные конструкции структурного программирования:

1. Функциональный блок, как обычно, обозначается прямоугольником

2. Конструкция If-Then-Else. Элементы с выполняемыми действиями находятся справа от символа «Решение». Вход и выход из конструкции находятся соответственно сверху и снизу символа.

3. Конструкция цикла с предусловием («Пока»). В шестиугольнике записывается условие входа в цикл. Для повышения понятности алгоритма перед условием может быть записано слово «Пока» или соответствующее служебное слово оператора цикла с предусловием целевого языка программирования (например While в языке Паскаль).

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

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

Конструкция цикла с постусловием («До»). В шестиугольнике записывается условие выхода из цикла. Перед условием может быть помещена фраза «До тех пор, пока не» или соответствующее служебное слово оператора цикла с постусловием целевого языка программирования (например Until в языке Паскаль).

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

Конструкция цикла с параметром (частный случай цикла с предусловием). В шестиугольнике записываются начальное и конечное значения параметра цикла, перед которыми помещается слово «Для» или соответствующее служебное слово оператора цикла с параметром целевого языка программирования (например, For в ряде языков).

Конструкция Case.

Достоинства метода Дамке:

· схема алгоритма нагляднее, чем классическая, особенно для больших программ;

· удобно использовать при разработке алгоритма по методу нисходящего проектирования;

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

· Не позволяет разработать схему неструктурированного алгоритма

Недостатки:

· Схемы могут быть более громоздкие

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒