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

Вариант: 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 структурированной, т. е. программные функции абсолютно идентичны, что подтверждает правильность структурирования программы.