Математическая логика и теория алгоритмов. Анкудинов Г.И - 30 стр.

UptoLike

Составители:

Рубрика:

Структуры с ветвлениями

Для программы с ветвлениями все возможные пути выполнения

определяются так называемым деревом выполнения (E-деревом).

Рис. 2.3.

Пример 2.14. Рассмотрим блок-схему программы на рис.2.3. Эта

программа имеет дерево выполнения, представленное на рис.2.4. Условия

ветвления выражаются предикатами s, q, r. Программная функция программы с

ветвлениями без циклов определяется как объединение композиций

программных функций, которые получаются непосредственно из E-дерева.

Необходимое и достаточное условие выполнения конкретной ветви

определяется композицией каждого предиката с предшествующей функцией

пути.

В рассматриваемом примере имеется пять путей выполнения,

пронумерованных как показано на рис. 2.4. Выпишем программную функцию

каждого пути:

1. {(X,Y): s(X) & q(f(X)) & Y=g(f(X))}.

2. {(X,Y): s(X) &

⎤ q(f(X)) & r(h(f(X))) & Y=g(h(f(X)))}.

3. {(X,Y): s(X) &

⎤ q(f(X)) & ⎤ r(h(f(X))) & Y=h(f(X))}.

4. {(X,Y):

⎤ s(X) & r(h(X)) & Y=g(h(X))}.

5. {(X,Y):

⎤ s(X) & ⎤ r(h(X)) & Y=h(X)}.

114