Методы структурирования программ
Тема: Методы структурирования программ
Цель: Освоить методологию преобразования произвольной программы в структурированную.
Задание:
Преобразовать управляющую структуру программы, заданную с помощью сокращенной матрицы смежности, в структурированную программу. Показать их функциональную эквивалентность
Вариант: 3
|
SA0 | AX0 | XYC | YBU | BU0 | CZ0 | ZCU | UTD | TF0 | |
DV0 | VGK | GW0 | WHU | HV0 | FE0 | KL0 | LP0 | PLE | |
|
Ход работы:
1. Используя матрицу смежности, построим блок-схему исходной программы:
2. Выполним полный анализ исходной программы. Покажем элементы анализа и результирующие блок-схемы для каждого шага анализа.
Находим в исходной блок-схеме структурированные элементы, для каждого из которых вводится функциональный дополнительный узел, в котором хранится идентификатор и счетчик. Идентификатор содержит номер шага структурирования и номер оператора. Счетчик указывает, сколько исходных узлов данным узлом объединено. Данный этап заканчивается, когда в программе не остается ни одного структурированного элемента.
Шаг 1:
Шаг 2:
Шаг 3:
Результат:
3. Выделенные неструктурированные фрагменты преобразуем с помощью теоремы о структурировании в структурированную форму. При использовании теоремы о структурировании получим помеченную и рекурсивную программы. Для структурирования программы воспользуемся методом введения переменной состояния:
Шаг 1: Идентифицируем все функциональные и предикатные узлы и помечаем все дуги, причем выходной дуге присваиваем «0», а все остальные дуги помечаются номерами узлов, в которые эти дуги входят:
Шаг 2: Заменяем функциональные и предикатные узлы новыми элементами с использованием счетчика i:
Шаг 3: Строим структурированную программу, используя новые обозначения, причем вводим дополнительный цикл по счетчику i:
Шаг 4: Упростим полученную схему путем подстановки узлов и линий в узлы присваивания счетчику нового значения. При этом нельзя допускать образования рекурсии:
4. Проверим функциональную эквивалентность выделенного неструктурированного фрагмента исходной программы и полученного структурированного аналога:
Е-схема исходной программы:
Е-дерево исходной программы:
Введем обозначения составных функциональных узлов:
Программная функция для исходной программы будет выглядеть следующим образом:
Е-дерево структурированной программы:
Введем обозначения составных функциональных узлов, а также вспомогательных узлов, модифицирующих состояние счетчика:
Для упрощения программной функции подставим r4 в r3:
Выводы: Как видно, r1 исходной программы идентично r2 структурированной, а r2 исходной программы идентично r3 структурированной, т. е. программные функции абсолютно идентичны, что подтверждает правильность структурирования программы.