Конспект главы 3

Алгоритмы, в которых все действия совершаются одно за Другим, независимо ни от каких условий, называются линейными. Характерная для них форма организации действий - последовательное выполнение. Если же при решении задачи необходимо принимать решения в зависимости от создавшейся ситуации, то в алгоритме нужно использовать ветвления. Ветвление (развилка) - это такая форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий. Имеется две существенно различные формы записи ветвлений - полная и неполная. В каждой из них указывается условие, которое надо проверять, и наборы действий, которые надо исполнять при выполнении или невыполнении условия. Ясно, что проверка условия должна быть допустимым действием исполнителя.

Ветвление в полной форме записывается так:

 Если Q, то: 
 P1 
 Р2 
 ... 
 Рn 
 Иначе: 
 Т1 
 Т2 
 ...
 Тm 
 Конец ветвления.

Здесь Q - условие, P₁, P₂, ..., Р_n - действия, которые совершаются в случае выполнения условия Q (первая ветвь), а Т₁, Т₂, ..., Т_m - действия, которые совершаются, если это условие не выполнено (вторая ветвь). После исполнения всех действий ветви исполнитель переходит к исполнению действий, записанных после строки "Конец ветвления". Указатель "Конец ветвления" служит для устранения двусмысленности в алгоритме. Без него, в частности, не ясно, к какому действию переходить после исполнения первой ветви ветвления.

Ветвление в неполной форме записывается следующим образом:

 Если Q, то: 
 Р1 
 Р2 
 ...
 Рn 
 Конец ветвления.

Здесь Q - условие, P₁, P₂, ..., Р_n - действия, которые совершаются в случае выполнения условия Q. Если же условие не выполнено, то сразу совершается действие, записанное после слов "Конец ветвления".

Для более наглядного представления алгоритмов используются так называемые блок-схемы. При этом каждое действие, кроме проверки условия, записывается в прямоугольник, а каждое условие - в ромб. Блок-схема 13. а соответствует последовательному выполнению действий. Блок-схема 13, б соответствует ветвлению в полной, а 13, в - в неполной форме.

ВЫЧИСЛИТЕЛЬ умеет проверять соотношения <, >, =, ≠, ≤, ≥ между значениями арифметических выражений. Вот примеры условий, которые умеет проверять ВЫЧИСЛИТЕЛЬ: 2<3, A>3, Х + Y≥Z/T · 25,232. Вот пример разветвляющегося алгоритма для ВЫЧИСЛИТЕЛЯ:

 Запросить А, В. 
 Если cos A<cos В, то: 
 Сообщить В. 
 Иначе: 
 Сообщить А. 
 Конец ветвления.

При записи программ для ВЫЧИСЛИТЕЛЯ, имитируемого на ЭВМ, вместо знаков ≤, ≥ и ≠ пишется соответственно <=, >= и <>.

Исполнитель ЧЕРТЕЖНИК умеет определять, находится ли край листа на расстоянии менее одного шага впереди него. Вот пример разветвляющегося алгоритма для ЧЕРТЕЖНИКА:

 Если впереди край, то: 
 Повернуть налево. 
 Конец ветвления. 
 Повернуть налево. 
 Если впереди не край, то: 
 Сделать шаг. 
 Повернуть налево. 
 Иначе: 
 Повернуть налево. 
 Конец ветвления.

При записи программ для ЧЕРТЕЖНИКА, имитируемого на ЭВМ, соответствующие условия записываются так: ВПЕРЕДИ КРАЙ или ВПЕРЕДИ НЕ КРАЙ.

Ветвления неизбежно возникают при построении алгоритмов для решения жизненных задач. Ведь любая модель применима лишь в определенных границах, порождающих те или иные ограничения на исходные данные. Проверка того, удовлетворяют ли исходные данные этим ограничениям, должна присутствовать в алгоритме. А значит, алгоритм будет содержать ветвления.

Правда, границы применимости модели нелегко указать заранее. Тогда границы выявляются в ходе вычислительного эксперимента. Одно из основных достоинств ЭВМ состоит как раз в том, что натурный эксперимент (физический, биологический, экологический и т. п.) она позволяет заменить вычислительным экспериментом. Проведение эксперимента на ЭВМ имитирует проведение натурного эксперимента, будучи при этом, как правило, гораздо дешевле и безопаснее.