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

                                      58

   Назовем ветвью последовательность условий и операторов, которые будут
пройдены при выполнении алгоритма для конкретных значений исходных
данных. Заметьте, что во всех рассмотренных выше условных операторах,
которые можно рассматривать как запись простейших ветвящихся алгоритмов,
количество ветвей равно количеству условий плюс единица. Рассмотрим еще
пример:
  if условие1
  then if условие2
         then оператор1
         else оператор2
  else if условие3
         then оператор3
         else оператор4
   В этом примере 3 (три) условия, поэтому, в соответствии с предложенной
формулой, количество ветвей будет равно 4. Запишем все ветви этого
алгоритма в таблице.
                               Ветви алгоритма
           Ветвь Условие1 Условие2 Условие3 Оператор
           1       true         true                   1
           2       true         false                  2
           3       false                     true      3
           4       false                     false     4
   Докажем, что для произвольного ветвящегося алгоритма, построенного с
помощью вложения других ветвящихся алгоритмов, количество ветвей равно
количеству условий плюс единица.
   Воспользуемся методом математической индукции. Для количества
условий, равного единице, количество ветвей равно двум. Этот факт следует из
рассмотренных выше ветвящихся алгоритмов (условных операторов).
Предположим, что в ветвящемся алгоритме количество условий равно n, а
количество ветвей - n+1. Докажем, что при добавлении еще одного условия
количество ветвей станет n+2. В самом деле, добавление условия вызывает
замену в ветвящемся алгоритме одной ветви двумя новыми, поэтому
количество ветвей станет: n+1-1+2=n+2 или (n+1)+1, где n+1 - количество
условий. Таким образом, утверждение доказано.
   Ветвящийся алгоритм может быть построен последовательным соединением
других ветвящихся алгоритмов. Покажем, что и в этом случае формула для
подсчета количества ветвей остается той же. Рассмотрим
пример:
   if условие1       Первая часть
   then оператор1 ветвящегося
   else оператор2; алгоритма
   if условие2       Вторая часть
   then оператор3 ветвящегося
   else оператор4 алгоритма