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

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

Цель: Освоить методологию преобразования произвольной программы в структурированную.

Задание:

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

Вариант: 3

Ход работы:

1. Используя матрицу смежности, построим блок-схему исходной программы:

2. Выполним полный анализ исходной программы. Покажем элементы анализа и результирующие блок-схемы для каждого шага анализа.

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

Шаг 1:

Шаг 2:

Шаг 3:

Результат:

3. Выделенные неструктурированные фрагменты преобразуем с помощью теоремы о структурировании в структурированную форму. При использовании теоремы о структурировании получим помеченную и рекурсивную программы. Для структурирования программы воспользуемся методом введения переменной состояния:

Шаг 1: Идентифицируем все функциональные и предикатные узлы и помечаем все дуги, причем выходной дуге присваиваем «0», а все остальные дуги помечаются номерами узлов, в которые эти дуги входят:

Шаг 2: Заменяем функциональные и предикатные узлы новыми элементами с использованием счетчика i:

Шаг 3: Строим структурированную программу, используя новые обозначения, причем вводим дополнительный цикл по счетчику i:

Шаг 4: Упростим полученную схему путем подстановки узлов и линий в узлы присваивания счетчику нового значения. При этом нельзя допускать образования рекурсии:

4. Проверим функциональную эквивалентность выделенного неструктурированного фрагмента исходной программы и полученного структурированного аналога:

Е-схема исходной программы:

Е-дерево исходной программы:

Введем обозначения составных функциональных узлов:

Программная функция для исходной программы будет выглядеть следующим образом:

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

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

Для упрощения программной функции подставим r₄ в r₃:

Выводы: Как видно, r₁ исходной программы идентично r₂ структурированной, а r₂ исходной программы идентично r₃ структурированной, т. е. программные функции абсолютно идентичны, что подтверждает правильность структурирования программы.