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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Условия расположения точки 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. Технология программирования ветвящихся процессов - student2.ru

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

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

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

Наши рекомендации