47577 (Методология преобразования произвольной программы в структурированную)
Описание файла
Документ из архива "Методология преобразования произвольной программы в структурированную", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47577"
Текст из документа "47577"
Контрольная работа 2
МЕТОДЫ СТРУКТУРИРОВАНИЯ ПРОГРАММ
Цель работы: освоить методологию преобразования произвольной программы в структурированную.
Методические указания
Наиболее известными методами, позволяющими выполнить структурирование программ, являются: метод дублирования кодов программы, метод введения переменной состояния и метод булевых признаков.
М
етод дублирования кодов. Рассмотрим программу, блок-схема которой приведена на рисунке 1. В настоящем виде программа не является структурированной; каждый блок не удовлетворяет требованию «один вход – один выход».
Ч тобы получить структурированную программу, мы воспользуемся дублированием тех модулей, в которые можно войти из нескольких мест. Рассмотрим исходную программу как простую конструкцию типа IF-THEN-ELSE, показанную на рисунке 2.
Рисунок 2 -Упрощенное представление схемы по рисунку 1.
Она может быть расширена до структуры, изображенной на рисунке 3. Окончательно вся программа может быть представлена в виде, показанном на рисунке 4.
М
етод применим к любой программе, имеющей структуру решетки
Рисунок 3 - Более подробное представление схемы.
или сети, но не может быть применен к циклическим программам.
М
етод дублирования кодов имеет недостаток: он требует больше памяти, чем исходный неструктурированный подход. Однако часто оказывается, что дублируемые модули содержат по 2-3 оператора. В таком случае дублирование кодов – приемлемая плата за возможность получить распадающуюся на уровни структуру. Если же модули состоят из значительного объема кодов, то вводятся подпрограммы. При этом важно, чтобы они были организованы как подпрограммы с формальными параметрами, что дает возможность установить их правильность вне зависимости от контекста, в котором они используются.
Метод введения переменной состояния. Метод применим к любым программам и допускает автоматическое применение. Процесс преобразования состоит из пяти шагов.
Рисунок 5 - Неструктурированная программа
-
Каждому блоку неструктурированной схемы приписывается номер.
-
В программу вводится новая переменная i целого типа.
-
Функциональные блоки неструктурированной схемы заменяются функциональными блоками, которые выполняют те же самые вычисления и присваивают переменной i целое значение, идентифицирующее номер блока-приемника исходной схеме.
-
Логические блоки исходной схемы преобразуются таким же образом.
Т
еперь перестраиваем блок-схему, придав ей форму, показанную на
Рисунок 6 - Структурированная форма программы
Начальное значение i=1.
Затем последовательно выполняется опрос значений переменной i и т.д.
Рисунок 7 - Схема выполнения программы.
Программная функция циклической программы описывается системой рекурсивных функций. При этом для каждого i-го узла слияния, начинающего цикл, вводится вспомогательная функция f, определяющая функцию всех узлов схемы выполнения, следующих за i-м узлом.
На рисунке 8 приведен пример построения программной функции циклической программы. В данном случае [P] рекурсивно зависит от f1 и f2.
а) циклическая программа
б
) дерево выполнения
в) вывод системы рекурсивных функций
Р
исунок 8 - Пример построения программной функции
Недостатки метода:
-
разрушается форма и топология исходной блок-схемы;
-
снижается эффективность программы, т.к. каждый функциональный блок дополняется операцией присвпаивания значения переменной состояния и значение переменной состояния должно опрашиваться после исполнения каждого блока.
Достоинства метода:
-
преобразованная введением переменной состояния форма может быть неограниченно продолжена, не усложняя при этомобщего подхода;
-
облегчается документирование программы, т.к. каждому блоку исходной схемы соответствует определенное состояние программы;
-
облегчается процесс отладки, если програма не выполняется должным образом, то довольно просто трассировать переменную состояния, что дает ясное прдставление о ходе управления программой.
Метод булевого признака. Существует еще один метод структурирования программ, содержащих циклы. Данный метод требует введения в программу некоторого признака задается в некоторой точке выше цикла; конструкциями типа DO-WHILE или REPEAT-UNTIL осуществляется управление циклом до тех пор, пока названный признак сохраняет заданное значение; некоторыми условиями внутри цикла определяется момент смены значения признака. Таким тбразом, программа продставляется в форме:
...flag:=0…
WHILE flag = 0
DO… If x=y THEN flag:=1 ...
или в какой-нибудь другой эквивалентной форме.
Программной функцией [P] программы P называется множество всех упорядоченных пар {(X,Y)}, где X – исходное состояние данных перед выполнением программы по некоторому пути дерева ее выполнения; Y – состояние данных после окончания выполнения программы по этому пути.
Для ациклической программы P, показанной на рисунке 3.7, программная функция определяется условным правилом:
[P]={(X,Y)|(p(X)Y=f(X)|p(X)&q(X)Y==g(X)|p(X)&q(X)Y=X)
Задание к контрольной работе
Преобразовать управляющую структуру программы, заданную с помощью сокращенной матрицы смежности, в структурированную программу. Показать их функциональную эквивалентность.
ТАБЛИЦА 1
Номер варианта | | |||||||||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||||||||||
SX0 | SA0 | SA0 | SX0 | SA0 | SX0 | SX0 | SA0 | SA0 | SB0 | |||||||||||
XZA | AX0 | AX0 | XCA | AB0 | XAZ | XYZ | AX0 | AX0 | BX0 | |||||||||||
AB0 | XDB | XYC | CD0 | BX0 | AY0 | YBA | XZY | XDB | XBY | |||||||||||
BY0 | DY0 | YBU | DV0 | XBY | YAB | ZBC | YWV | DT0 | XQZ | |||||||||||
YBP | BC0 | BU0 | VDY | YPZ | BT0 | AP0 | ZBW | TF0 | QVT | |||||||||||
PTU | CY0 | CZ0 | AB0 | ZCW | ZCD | PLF | BU0 | BY0 | TJ0 | |||||||||||
TF0 | YZT | ZCU | BY0 | CD0 | DT0 | FV0 | UBW | YCF | JHN | |||||||||||
UGV | ZKY | UTD | YQZ | DW0 | CT0 | VFL | WTR | CF0 | HJ0 | |||||||||||
FV0 | KFH | TF0 | QFL | PTG | TP0 | LMP | TF0 | FZ0 | VKN | |||||||||||
ZDQ | FG0 | DV0 | LW0 | TQ0 | PUQ | BD0 | RGN | ZHW | KW0 | |||||||||||
QCU | GK0 | VGK | WKN | QFV | UWV | DQ0 | FG0 | HW0 | WKN | |||||||||||
CU0 | TP0 | GW0 | KL0 | FV0 | WKH | QDU | VQN | WVI | ZCU | |||||||||||
DW0 | PQT | WHU | FG0 | GU0 | VGH | UDM | QDC | VUE | CD0 | |||||||||||
WGD | QHT | HV0 | GR0 | UGV | HK0 | CW0 | CN0 | UAK | DG0 | |||||||||||
GE0 | HL0 | FE0 | RNM | VHK | GK0 | WTN | DN0 | KQ0 | GR0 | |||||||||||
VRH | LR0 | KL0 | NPO | KL0 | QMN | TN0 | NHM | QKA | RLA | |||||||||||
REL | RMN | LP0 | MP0 | LE0 | NGF | MLN | HK0 | ILM | LI0 | |||||||||||
LE0 | MU0 | PLE | ZFT | HL0 | MFK | NMP | KM0 | LF0 | IPM | |||||||||||
HK0 | NU0 | TU0 | WHR | FK0 | PHK | GP0 | MJ0 | MI0 | ||||||||||||
KE0 | UER | UHM | RML | KL0 | KE0 | PLM | JPN | PE0 | ||||||||||||
HM0 | ML0 | LE0 | HR0 | LM0 | PG0 | NP0 | ||||||||||||||
PE0 | RGE | ME0 | NT0 | ANP | ||||||||||||||||
GH0 | GRO | UFR | ||||||||||||||||||
RP0 | FR0 | |||||||||||||||||||
OW0 | ||||||||||||||||||||
Номер варианта | ||||||||||||||||||||
11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |||||||||||
SA0 | SX0 | SX0 | SA0 | SA0 | SA0 | SA0 | SA0 | SA0 | SA0 | |||||||||||
AB0 | XDA | XAE | AX0 | AX0 | AX0 | AX0 | AX0 | AX0 | AB0 | |||||||||||
BX0 | AB0 | AY0 | XCB | XDB | XBD | XYB | XCB | XDB | BC0 | |||||||||||
XBY | BY0 | YDB | CY0 | DT0 | BC0 | YTC | BZ0 | DT0 | CDG | |||||||||||
YUZ | YCF | BZ0 | YDZ | TZO | CY0 | CD0 | CY0 | BC0 | GI0 | |||||||||||
UYV | CF0 | ZCV | DY0 | BC0 | YBF | DT0 | YDZ | CY0 | IQ0 | |||||||||||
ZVW | DZ0 | CV0 | BZ0 | CY0 | DZ0 | BZ0 | DY0 | YBZ | DF0 | |||||||||||
WZK | ZDT | DU0 | ZGU | YDZ | ZTF | ZBT | ZGU | TZ0 | FJ0 | |||||||||||
VCF | TU0 | UDV | UVT | ZRU | TF0 | TU0 | UVT | ZRU | JQF | |||||||||||
CP0 | UDF | VXT | GM0 | UFV | FG0 | URV | VKH | UFW | QBP | |||||||||||
PTF | FV0 | TF0 | MW0 | FV0 | GU0 | VLW | KP0 | FV0 | PRM | |||||||||||
TD0 | VGW | FH0 | WME | VGW | ULH | LF0 | PLE | VGW | ML0 | |||||||||||
DC0 | WFQ | HW0 | VKH | GW0 | HV0 | FMK | LK0 | GW0 | RL0 | |||||||||||
KFL | GP0 | WGQ | HE0 | WAQ | VKL | MF0 | HE0 | WEQ | LOY | |||||||||||
FY0 | PHR | GH0 | KP0 | QRP | KH0 | KR0 | GM0 | QRP | OW0 | |||||||||||
LMH | HL0 | QHP | PLE | PMR | LW0 | WGR | MW0 | PMR | WT0 | |||||||||||
HE0 | LG0 | PVI | LK0 | RNH | WUP | GP0 | WME | RNH | YLT | |||||||||||
MGN | RGQ | IRK | TF0 | NL0 | PEQ | PHR | TF0 | NL0 | TCU | |||||||||||
GN0 | QMK | RNJ | FN0 | LM0 | QMR | HG0 | FN0 | LM0 | UE0 | |||||||||||
NME | MN0 | NR0 | NR0 | HJ0 | MN0 | RTN | NR0 | ME0 | ||||||||||||
NI0 | KM0 | RNQ | JKM | NQ0 | NJ0 | RNQ | HJ0 | |||||||||||||
KI0 | MJ0 | QNZ | KH0 | RFE | JUE | QNZ | JKM | |||||||||||||
IFJ | JPL | ME0 | KH0 | |||||||||||||||||
JQE | LX0 | |||||||||||||||||||
EX0 |
Порядок выполнения работы
-
Нарисовать блок-схему программы, используя сокращенную матрицу смежности. Целесообразно сразу использовать базисные элементы структурного программирования: последовательность, if-then-else,while-do, do-until и др.
-
Выполнить полный анализ исходной программы. Показать элементы анализа и результирующие блок-схемы для каждого шага анализа.
-
Выделенные неструктурированные фрагменты преобразовать одним из методов в структурированную форму. При использовании теоремы о структурировании получите помеченную и рекурсивную программы.
-
Проверить функциональную эквивалентность выделенного неструктурированного фрагмента исходной программы и полученного структурированного аналога.
Содержание отчета
-
Блок-схема исходной программы.
-
Элементы анализа и упрощенная блок-схема каждого шага анализа. Выделенный неструктурированный фрагмент программы.
-
Помеченная и рекурсивная структурированные программы.
-
E-схемы и программные функции для выделенных фрагментов исходной и структурированной программы.
Контрольные вопросы
-
Какие методы применяются для структурирования программ?
-
В каких случаях применение метода дублирования кодов эффективно?
-
Перечислите достоинства метода введения переменной состояния.
-
Как формулируется теорема о структурировании программ?
Лабораторная работа №2
ПЛАНИРОВАНИЕ ОРГАНИЗАЦИИ РАБОТ НАД ПРОЕКТОМ ПРОГРАММ