Вопрос 5.Реализация теоретических основ

Реализация теоретических основ структурного программирования

базируется на следующих правилах.

Все операции в программе должны представлять собой либо

непосредственно исполняемые в линейном порядке выражения, либо одну из

следующих управляющих конструкций:

1) вызовы подпрограмм – любое допустимое на конкретном языке

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

одним выходом;

2) вложенные на произвольную глубину операторы If-Then-Else;

3) циклические операторы (цикл с предусловием, называемый циклом

«Пока»).

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

Однако иногда допускаются их некоторые расширения:

1) дополнительные конструкции организации цикла:

• цикл с параметром как вариант цикла с предусловием;

• цикл с постусловием, называемый в структурном

программировании циклом «До», – для него характерно то, что тело

цикла выполняется до проверки условия выхода из цикла;

изображается так, как представляет рисунок 3.5.

 

 

Рисунок 3.5 – Графическое представление цикла с постусловием

 

2) подпрограммы с несколькими входами и несколькими выходами

(например, один выход нормальный, второй – по ошибке);

3) применение оператора GoTo с жёсткими ограничениями (например,

передача управления не далее, чем на десять операторов, или только вперёд по

программе);

4) использование оператора Case как расширения конструкции If-Then-

Else; в структурном проектировании программ конструкция Case

представляется так, как показывает рисунок 3.6.

Рисунок 3.6 – Графическое представление оператора Case

 

Достоинства структурного программирования по сравнению с

интуитивным неструктурным программированием:

1) Уменьшение трудностей тестирования программ.

2) Более высокая производительность программистов.

3) Ясность и читаемость программ, что упрощает их сопровождение.

4) Эффективность программ.

Примеры структурного программирования:

отказ от использования оператора безусловного перехода (GoTo), замена его рядом других структурированных операторов, использование идей нисходящего проектирования программ.

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

1) Функциональный блок;

2) Конструкция принятия двоичного (дихотомического) решения.

3) Конструкции обобщенного цикла.

 

Вопрос 6. Преобразование. Дублирование.

Программа, реализующая данный алгоритм, не является структурированной, так как не удовлетворяет условию «один вход – один выход».

Сущность метода дублирования кодов: дублируются те модули исходного алгоритма или программы, котрые имеют несколько входов/выходов (кроме последнего модуля).

В соответствии с этим в исходной схеме необходимо дублировать модули 5 (в него можно войти из модулей 2 и 3), 7 (в него можно войти из модулей 4 и 5) и 8 (в него можно войти из модулей 5 и 6). Это приводит исходную схему к виду, который иллюстрирует рисунок 3.8.

Полученная схема алгоритма является структурированной.

Чтобы доказать это, необходимо воспользоваться преобразованиями Бома-Джакопини, т.е. последовательно преобразовать схему к одному функциональному блоку с одним входом и одним выходом. Для этого необходимо выполнить несколько шагов.

Шаг 1

На вышеприведенной схеме модули 4 и 7 представляют собой конструкцию следования. В соответствии с преобразованиями БомаДжакопини они могут быть сведены к одному функциональному блоку Х1. Модули 5, 7, 8 представляют собой конструкциюIf-Then-Elseс одним входом и одним выходом. Они также могут быть преобразованы к одному функциональному блоку ( Х2 и Y1 ). Аналогичные рассуждения справедливы для конструкции следования, состоящей из модулей 6, 8 – она сводится к функциональному блоку Y2. В результате предыдущая схема принимает вид, который представляет рисунок 3.9.

Шаг 2

В полученной в результате выполнения шага 1 схеме группа модулей 2, X1, X2 и группа модулей 3, Y1, Y2 представляют собой конструкцииIf-Then-Else c одним входом и одним выходом. В соответствии с преобразованиямиБома-Джакопиниих можно представить в виде функциональных блоков (блоков Х и Y соответственно). В результате схема принимает вид, который иллюстрирует рисунок 3.10.

Шаг 3

В полученной в результате выполнения шага 2 схеме группа модулей 1, X, Yпредставляет собой конструкциюIf-Then-Elsec одним входом и одним выходом. В соответствии с преобразованиями Бома-Джакопиниее можно представить в виде функционального блокаZ. В результате схема принимает вид конструкции следования (рисунок 3.11).

Шаг 4

В соответствии с преобразованиями Бома-Джакопиниконструкцию следования можно представить в виде функционального блокаR(см. рисунок

3.11).

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

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

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

1)неприменимость к программам с циклами;

2)дополнительные затраты памяти для хранения дублируемых модулей. Поэтому метод используется, если дублируемые модули содержат

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

3)Увеличение объема кода(громоздкие схемы алгоритма)

 

Вопрос 7. Преобразование. Введение переменной

Данный метод был впервые предложен Ашкрофтом и Манной.

Рассмотрим применение данного метода на примере

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

рисунок 3.12.

 

Данная схема не является структурированной, так как из цикла,

состоящего из блоков 1 и 3, существует два выхода. Таким образом, нарушено

условие «один вход – один выход», которому должны удовлетворять

структурированные схемы.

Рисунок 3.12 – Исходная схема неструктурированного алгоритма

Процесс преобразования программы в структурированную состоит из

следующей последовательности шагов.

1) Каждому блоку неструктурированной схемы приписывается номер.

Обычно первому блоку присваивается 1, последнему – 0.

2) В программу вводится дополнительная переменная целого типа

(например, J ), называемая переменной состояния.

3) Функциональные блоки исходной схемы заменяются блоками,

выполняющими помимо основных функций преобразование переменной J: переменной J присваивается значение, равное номеру блока-приёмника в исходной схеме.

4) Аналогично преобразуются логические блоки. При этом, если в

логическом блоке условие истинно, то это соответствует одному значению J,

если ложно – другому.

5) Исходная схема перестраивается к виду, предложенному Ашкрофтом-

Манной (рисунок 3.13).

На данной схеме блоки 1а – nа являются аналогами соответствующих

блоков исходной схемы и, помимо этого, присваивают значение переменной J.

В результате преобразований Ашкрофта-Манны исходная

неструктурированная схема рассматриваемого примера (см. рисунок 3.12)

принимает структурированный вид, который представляет рисунок 3.14.

При выполнении алгоритма, реализованного по методу Ашкрофта-

Манны, переменная состояния J устанавливается в начальное значение, равное

номеру первого блока непреобразованной схемы (как правило, это единица).

Затем осуществляется последовательный опрос переменной J, начиная с нуля и

заканчивая максимальным номером блока исходной схемы (в нашем примере

он равен пяти). Выполняется тот блок исходной схемы, номер которого

соответствует текущему значению J. Помимо этого в J заносится значение,

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

текущим блоком. Когда значение J станет равно нулю, выполняется последний

блок непреобразованной схемы (блок с номером ноль) и осуществляется выход

из алгоритма.

Полученная по методу Ашкрофта-Манны схема алгоритма является

структурированной. Для доказательства этого достаточно последовательно

преобразовать данную схему к одному функциональному блоку.

Шаг 1 преобразования.

Конструкции 1а, 3а и 4а представляют собой конструкции If-Then-Else с

одним входом и одним выходом, конструкции 2а, 5а являются конструкциями

следования (см. рисунок 3.14). Следовательно, они могут быть преобразованы к

соответствующим функциональным блокам.

Данный шаг преобразований и все последующие шаги поясняет рисунок

3.15.

Следующие шаги преобразований необходимо проводить снизу вверх

схемы (см. рисунок 3.15).

Шаг 2 преобразования.

Символ “Решение” с проверкой условия J = 5 и блок 5а представляют собой конструкцию If-Then-else (с одной ветвью) с одним входом и одним выходом. Поэтому данный символ «решение» и блок 5а могут быть заменены функциональным блоком I (см. рисунок 3.15).

Рисунок 3.13 – Обобщенный вид схемы алгоритма, предложенный Ашкрофтом-Манной Вторая ветвь данного символа «Решение» может быть использована для повышения надежности программы и на данном рисунке не показана (данная ветвь обеспечивает возможность контроля непопадания значений J в диапазон

0 – n, где n – максимальный номер блока в исходной схеме).

По сути, без проверки условия J = 5 в алгоритме можно обойтись, перейдя на выполнение блока 5а по ветви «нет» проверки условия J = 4.

Шаг 3 преобразования.

Символ “Решение” с проверкой условия J = 4 и блоки I и 4а

представляют собой конструкцию If-Then-Еlse с одним входом и одним

выходом. Поэтому они заменяются функциональным блоком II (см. рисунок

3.15).

Шаг 4 преобразования.

Символ “Решение” с проверкой условия J = 3 и блоки II и 3а

представляют собой конструкцию If-Then-Else с одним входом и одним

выходом. Поэтому они заменяются функциональным блоком III (см. рисунок

3.15).

Шаг 5 преобразования・  撰 ・ ____í.

Символ “решение” с проверкой условия J = 2 и блоки III и 2а

представляют собой конструкцию If-Then-Else с одним входом и одним

выходом. Поэтому они заменяются функциональным блоком IV (см. рисунок

3.15).

Шаг 6 преобразования.

Символ “решение” с проверкой условия J = 1 и блоки IV и 1а

представляют собой конструкцию If-Then-Else с одним входом и одним

выходом. Поэтому они заменяются функциональным блоком V (см. рисунок

3.15).

Шаг 7 преобразования.

Символ “решение” с проверкой условия J = 0 и блок V представляют

собой конструкцию обобщенного цикла с одним входом и одним выходом.

Поэтому они заменяются функциональным блоком VI (см. рисунок 3.15).

Шаг 8 преобразования.

Функциональный блок начальной установки J = 1, блок VI и блок 0

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

выходом. Поэтому они заменяются функциональным блоком VII (см. рисунок

3.15).

Таким образом, за восемь шагов преобразований Бома-Джакопини

исходная схема, построенная по методу Ашкрофта-Манны, преобразована в

один функциональный блок с одним входом и одним выходом. Это

подтверждает, что она является структурированной.

Достоинства метода _______введения переменной состояния:

1) процесс преобразования программы отличается наглядностью и

чёткостью;

2) любому блоку исходной схемы соответствует определённое состояние

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

3) метод применим к программам любой структуры (разветвляющимся и

циклическим);

4) возможно автоматическое применение данного метода.

Недостатки метода:

1) структурированная форма схемы алгоритма сильно отличается от

топологии исходной схемы, что затрудняет ее понимание;

2) дополнительные затраты времени на анализ и установку значений

переменной сосотояния;

3) громоздкость результирующей схемы.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. A. особая форма восприятия и познания другого человека, основанная на формировании по отношению к нему устойчивого позитивного чувства
2. DSM-IV-TR: Основные характеристики.
3. I ГЛАВА. НАУЧНО-ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОЕКТИРОВАНИЯ МУЗЫКАЛЬНЫХ ШКОЛ
4. I. Запоры — основная причина стресса
5. I. Какое из данных утверждений выражает основную идею текста?
6. I. Основания и фундаменты зданий и сооружений
7. I. ОСНОВНЫЕ ЭТАПЫ НАПИСАНИЯ КУРСОВОЙ РАБОТЫ
8. I. Теоретические основы использования палочек Кюизенера как средство математического развития дошкольников.
9. I. Теоретические основы экономического воспитания детей старшего дошкольного возраста посредством сюжетно-ролевой игры
10. I.1. Основные предпосылки и механизмы развития речевой деятельности
11. IDEF1X - методология моделирования данных, основанная на семантике, т.е. на трактовке данных в контексте их взаимосвязи с другими данными.
12. II. ОРГАНИЗАЦИОННЫЕ ОСНОВЫ ПСИХИАТРИИ