Глава 4. Технология программирования ветвящихся процессов

Ветвящийся (разветвляющийся)– вычислительный процесс с выбором одного из возможных вариантов вычислений в зависимости от проверки заданных условий.

Условие – зависимость, формирующая узел ветвления.

Узел ветвления – точка преобразования исходной (входной) ветви в несколько формируемых (выходных).

Ветвь – каждый из возможных вариантов решения.

Графическая интерпретация фрагментов ветвящихся процессов имеет вид:

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

Результат проверки – выполнение или невыполнение условия – определяет дальнейшее направление расчета. Так, условие «Если х > 0, то y = 3х» формально задает вычислительную ветвь, соответствующую его выполнению, но не определяет действие при невыполнении его.

Проверка любого условия всегда подразумевает существование его антипода – взаимоисключающего условия.

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

Следовательно, невыполнение проверяемого условия есть выполнение взаимоисключающего его.

Сложность формирования взаимоисключающего условия зависит от структуры основного.

Простейший вариант – работа с числовой осью. Она позволяет сформулировать условия расположения одной точки «x» относительно другой «а» (в простейшем случае x < a, x > a, x = a).

 

Тогда, приняв за основное первое из них (x < a), можно сформулировать взаимоисключающее как совокупность двух оставшихся (x > a, x = a), то есть х ³ а.

Таким образом, условие «Если х > 0, то y = 3х» сформулировано не полностью и требует указания действия в случае его невыполнения (выполнения взаимоисключающего условия х £ 0).

Более сложный вариант – расположение точки на плоскости, исключая начало координат.

Условия расположения точки M(a,b) в каждом квадранте имеют вид:

a > 0, b > 0 – первый (I),

a < 0, b > 0 – второй (II),

a < 0, b < 0 – третий (III),

a >0, b < 0 – четвертый (IV) квадрант.

Тогда, приняв за основное первое из них (a > 0, b > 0), можно сформулировать взаимоисключающее как совокупность трех пар оставшихся (a < 0, b > 0; a < 0, b < 0; a >0, b < 0).

По аналогии условие расположения точки в пространстве требует задания трех координат (a > 0, b > 0, c > 0). При этом сложность взаимоисключающих условий возрастает.

Упрощение записи взаимоисключающих условий возможно с помощью логической операции «не» (отрицания условия).

Полнота формулировки взаимоисключающего условия определяет возможную степень его детализации (количество подусловий N). Это определяет общее количество возможных выходных ветвей (от двух до N+1).

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

Рис. 4.1. Классификация разветвляющихся процессов

Простой (простое ветвление)– разветвляющийся процесс, содержащий две выходные ветви.

Сложный (сложное ветвление) – разветвляющийся процесс, включающий три и более выходных ветви, независимо от числа узлов.