Инструменты пользователя

Инструменты сайта


examination:c:question12

Вопрос №12. Структурированные программы

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

  1. функциональный (1 вход, 1 выход - прямоугольничек)
  2. предикатный (1 вход, 2 выхода - ромбик)
  3. узел слияния (несколько входов, 1 выход - круглешок)

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

  • ровно 1 вход и 1 выход
  • через каждый узел проходит путь от входа к выходу структуры

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

Части программы, которые сами являются программами, называются простыми подпрограммами.

Схема выполнения программы(Е-схема) - представляется в виде конечного дерева последовательного выполнения программы.

Алгоритм построения Е-схемы (строится на основе блок-схемы):

  1. Начать схему с входной линии и связанного с ней узла. На каждом шаге построения рассматривать каждый путь выполнения программы.
  2. Если заканчивается узлом, ранее не входившем в эту схему, то все входные линии и узлы, с которыми эти линии соединены, включаются в путь выполнения
  3. Формирование этой схемы считается законченным, если все пути выполнения оканчиваются выходными линиями или узлами

Все узлы слияния, кроме тех, которые находятся на повторяющемся пути, можно удалить.

Дерево выполнения(Е-дерево) - дерево, пути которого изображают все возможные последовательности реализации блок-схемы без возвращения назад.

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

Элементарная программа - простая программа, которая не содержит простых подпрограмм, более чем из одного узла. Некоторые элементарные программы имеют специальные наименования и соответствуют управляющим структурам языка программирования: if,then; if,then,else; while,do. Если функциональный узел элементарной программы заменить другой элементарно программой, то полученная программа называется составной.

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

Структурированная программа - составная программа, сформированная на основе фиксированного базисного множества элементарных программ.

examination/c/question12.txt · Последние изменения: 2014/01/15 08:09 (внешнее изменение)