Конспект лекций по программированию для начинающих. Гладков В.П. - 57 стр.

                                     59

   В соответствии с доказанным ранее, каждая часть приведенного
ветвящегося алгоритма имеет по две ветви, так как содержит по одному
условию. Воспользуемся основным принципом комбинаторики, согласно
которому, если объект А можно выбрать m способами, а после каждого такого
выбора объект В можно выбрать n способами, то выбор пары (A,B) в указанном
порядке можно осуществить m·n способами. В нашем случае первая часть
ветвящегося алгоритма содержит две ветви, после выбора любой из этих ветвей
мы вынуждены проходить любую из двух ветвей второй части. Следовательно,
всего ветвей в этом алгоритме: 2·2=4. К этому же факту можно прийти путем
преобразования исходного алгоритма. Для этого внесем вторую часть
алгоритма в каждую ветвь первой части. Преобразованный алгоритм будет
иметь вид:
   if условие1
   then     begin оператор1;
                   if условие2
                   then оператор3
                   else оператор4
            end
   else     begin оператор2;
                   if условие2
                   then оператор3
                   else оператор4
            end.
   В преобразованном алгоритме три условия, следовательно, по ранее
доказанному, - четыре ветви.
   В общем случае в ветвящемся алгоритме могут произвольным образом
сочетаться ветви, полученные вложением одного ветвящегося алгоритма в
другой, и ветви, полученные последовательным соединением двух и более
других ветвящихся алгоритмов. В этом случае для определения общего
количества ветвей исходный алгоритм разбивается на части, относящиеся к
одному из рассмотренных видов ветвящихся алгоритмов. Для каждой части
применяют установленные ранее правила подсчета, а затем используют
основные правила комбинаторики. Одно из них было рассмотрено ранее. Его
применение относится к случаю последовательного соединения ветвящихся
алгоритмов.
   Второе правило: если некоторый объект А можно выбрать m способами, а
другой объект В - n способами, то выбор «либо А, либо В» можно осуществить
m+n способами. Это правило применяют тогда, когда надо узнать количество
ветвей в двух сложно построенных ветвях ветвящегося алгоритма. Рассмотрим
пример.