Алгоритмы с ветвлением

В реальной жизни не все так просто. Вы захотели съесть бутер­брод, открыли хлебницу — а хлеба в ней нет! Что делать? Если очень хочется есть, то придется пойти в магазин, купить хлеб и принести его домой. Таким образом, ваши действия будут зави­сеть от условия: есть ли хлеб в хлебнице?

В этой ситуации последовательность ваших действий после по­явления желания съесть бутерброд будет следующей:

/. Открыть хлебницу.

2.                Если хлеб есть, то взять хлеб.

3.                Закрыть хлебницу.

4.                Если хлеба нет, то пойти в магазин.

5.                Купить хлеб.

6.                Принести хлеб домой.

7.                 Положить хлеб на стол и т. д.

Полужирным шрифтом выделены строки, на которые вам сле­дует обратить особое внимание, — в данном случае в них заданы условия, определяющие ваши дальнейшие действия.

Итак, теперь вы с бутербродом, однако в описании последова­тельности действий возникла неопределенность. Если строго сле­довать этому описанию, то несмотря на наличие хлеба в хлебнице и успешное выполнение действия 2....взять хлеб вам все равно придется идти в магазин, выполняя последовательно действия 3, 4, 5 и 6. Иначе не понятно, что делать после действия 3. Закрыть

16

хлебницу. Конечно, вы как человек разумный сообразите, что вам делать. А как быть, если в подобной ситуации окажется машина, которой поручено выполнение алгоритма?

Очевидно, в такой ситуации в описание алгоритма надо вне­сти некоторые уточнения. Во-первых, надо указать, что в какой-то момент последовательность выполнения действий может быть нарушена, и тогда нужно будет сделать выбор очередного дей­ствия. Этот выбор будет зависеть от выполнения (или невыполне­ния) некоторого условия (есть ли хлеб в хлебнице). Во-вторых, надо указать, какими именно должны быть очередные действия как при том, так и при другом результате выбора.

Признаком ситуации выбора служит слово «если», которое вво­дит условие (хлеб есть}. Но поскольку хлеба может и не быть, в алгоритме неизбежно еще одно «если», которое вводит противо­положное условие (хлеба нет). Чтобы не запутаться в этих услови­ях, второе условие обычно заменяют словом «иначе»:

/. Открыть хлебницу.

2.                 Если хлеб есть, то взять хлеб.

3.                Закрыть хлебницу.

4.                 Иначе пойти в магазин.

5.                Купить хлеб.

6.                  Принести хлеб домой.

7.                 Положить хлеб на стол и т. д.

Таким образом, главным является первое условие, вводимое словом «если». В зависимости от того, выполнено это условие или нет, вы переходите либо к действию J, либо к действиям 4, 5, 6. Эти варианты действий называются ветвями алгоритма.

Алгоритмы, в которых производится выбор одного из несколь­ких вариантов действий в зависимости от выполнения некоторого условия, называются алгоритмами с ветвлением, или условными алгоритмами.

Где начинается и где заканчивается каждая ветвь? При выпол­нении условия Если последовательность действий в алгоритме продолжается так, как она записана, — ведь никаких оснований для ее нарушения нет. Вы выполняете действия, образующие пер­вую ветвь. Где она заканчивается? Там, где заканчиваются дей­ствия, предусмотренные условием Если, т.е. перед вторым усло­вием — Иначе.

А если условие Если не выполнено? Тогда появляются основа­ния для нарушения последовательности действий. После провер­ки выполнения (точнее, невыполнения) условия Если начинает­ся выполнение действий, стоящих в алгоритме после Иначе, т.е. действий второй ветви.

Итак, в зависимости от выполнения условия Если вы соверша­ете действия либо первой, либо второй ветви. А дальше — опять не понятно: с какого места продолжать выполнение алгоритма,

17

например, после выполнения действия 3 первой ветви? Вы-то мо­жете догадаться, что следующим в алгоритме должно быть дей­ствие 7. Положить хлеб на стол, но как в подобной ситуации быть машине? Она-то догадываться не умеет!

Для снятия неопределенности в алгоритм вводят специальный указатель, отделяющий ветви от продолжения алгоритма. Обычно таким указателем является фраза Конец ветвления. После заверше­ния действий любой ветви надо отыскать фразу Конец ветвления и продолжить выполнение алгоритма с действия, которое следует после этой фразы.

Алгоритм будет выглядеть следующим образом:

/. Открыть мебницу.

2.                 Если хлеб есть, то взять хлеб.

3.                Закрыть хлебницу.

4.                 Иначе пойти в магазин.

5.                  Купить хлеб.

6.                Принести Xjw6 домой.

7.                  Конец ветвления.

8.                  Положить хлеб на стол и т. д.

Теперь, независимо оттого, какая именно ветвь алгоритма была выполнена, очередным будет действие, стоящее после фразы Ко­нец ветвления (8. Положить хлеб на стол).

Рассмотрим еще один алгоритм с ветвлением. Предположим, что надо произвести сортировку цилиндрических изделий по ди­аметру и распределить их по двум магазинам (ящикам, коробкам). Изделия поступают с конвейера в устройство, которое измеряет их диаметр, и в зависимости от результатов измерения другое ус­тройство помешает изделие в тот или иной магазин.

Алгоритм сортировки может быть следующим:

/. Установить изделие в измерительное устройство.

2.                 Измерить диаметр изделия.

3.                       Если диаметр больше заданного, то поместить изделие в магазин № 1.

4.                Иначе поместить изделие в магазин № 2.

5.                 Конец ветвления.

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

В автоматических системах, работающих без участия человека, при возникновении различных ситуаций машине приходится са-

18

|мой принимать решение о выборе варианта действий, поэтому в таких системах часто используются алгоритмы с ветвлением. Лю­бую ситуацию, в которой нужно выбирать один из двух или не­скольких вариантов действий, всегда можно свести к одному или нескольким ветвлениям алгоритма. 2.2.3. Циклические алгоритмы Часто мы наблюдаем или участвуем в процессах, в которых много раз подряд выполняются одни и те же действия. Например, рассмотрим, как работает продавец в магазине. Каждого покупа­теля он обслуживает по одной схеме: выдать товар —получить день­ги— выбить чек—дать сдачу. Меняются только вид и количество товаров. Контролер в кинотеатре работает по схеме: взять билет — проверить сеанс — оторвать контроль—вернуть билет. И так сотни раз в течение дня. Многократно повторяют одни и те же действия грузчик, разгружающий машину с продуктами; рабочий на кон­вейере; маляр, оклеивающий комнату обоями; и вы сами, когда пьете чай или отправляетесь утром на занятия.

Вернемся к рассмотрению алгоритма сортировки изделий. В этом алгоритме описаны однократные действия, производимые с од­ним изделием. Оно отправлялось в магазин № 1 или № 2, и на этом алгоритм заканчивался. Но реальные изделия поступают на сортировку, скорее всего, в большом количестве. Значит, описан­ные в алгоритме действия должны повторяться вновь и вновь. Как долго? Очевидно, пока изделия имеются на конвейере.

Как изменить алгоритм, чтобы процесс сортировки повторял­ся многократно? Какие именно действия повторять и до каких пор? Существует два варианта:

•           задать условие, при выполнении которого действия нужно повторять, а как только условие будет нарушено — прекратить повторение и перейти к продолжению алгоритма (например, кра­сить доски забора, пока он не закончится, а затем приступить к

•          задать необходимое количество повторений одних и тех же действий (например, налить в бочку 10 ведер воды).

Первый вариант более универсальный — он подходит для за­бора с любым количеством досок, в том числе и заранее неизвест­ным. Но исполнитель этого варианта алгоритма должен уметь про­верять выполнение заданного условия (закончился ли забор?), что не трудно для человека, но может оказаться трудным для маши­ны.

А вот второй вариант для машины не проблема — механиче­ские, электрические, электронные и другие счетчики существуют давно и в самых разных видах. Но этот вариант лишен гибкости, и

19

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

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

Алгоритмы, в которых повторяются одни и те же действия, называются циклическими алгоритмами.

Когда цикл выполнен нужное количество раз, исполнитель алгоритма переходит к дальнейшим действиям, находящимся уже за пределами цикла.

Поскольку в алгоритме сортировки изделий количество изде­лий заранее неизвестно, воспользуемся первым вариантом — попробуем найти условие, выполнение которого необходимо для повторения процесса сортировки. Таким условием является нали­чие очередного изделия на конвейере. Если сортировку произво­дит человек, то он легко обнаружит это изделие. Если же испол­нитель алгоритма сортировки — машина, то она должна уметь проверять наличие изделия на конвейере. Как машина сможет это сделать, рассмотрим далее. А сейчас дополним алгоритм сорти­ровки условием повторения цикла:

/. Пока на конвейере есть изделие, выполнять действия:

2.               Установить изделие в измерительное устройство.

3.                Измерить диаметр изделия.

4.              Если диаметр больше заданного, то поместить изделие в мага­зин № 1.

5.                Иначе поместить изделие в магазин № 2.

6.                Конец ветвления.

7.                Конец цикла.

Здесь полужирным шрифтом выделены строки, имеющие от­ношение к повторению действий, т.е. к циклу. В алгоритме есть и ветвление, но оно записано светлым шрифтом.

Для того, чтобы исполнителю было понятно, какие именно действия нужно повторять, эти действия (цикл) должны быть как-то выделены, т.е. должны быть указаны границы цикла. Так как повторение цикла зависит от выполнения заданного условия /. Пока на конвейере..., строка с этим условием может быть одной из гра­ниц цикла. Другую границу устанавливают строкой Конец цикла. Если условие / соблюдено, то выполняются действия 2... 6, распо­ложенные между указанными границами. При нарушении условия 1 исполнителю нужно будет перейти к действию, следующему за строкой 7. Конец цикла (если имеется продолжение алгоритма).

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

20

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

Составим циклический алгоритм погрузки контейнеров в вагон:

/. Начало цикла.

2.                 Поднять краном очередной контейнер.

3.                  Переместить контейнер к вагону.

4.                Погрузить контейнер в вагон.

5.                 Вернуть кран в исходное положение.

6.                     Пока в вагоне есть свободное место, повторять действия цикла.

7.                Закрыть и опечатать дверь вагона.

При выполнении условия 6 будут повторяться действия 2...5, после чего снова будет проверяться выполнение условия 6. Если оно окажется нарушенным, то повторения цикла не будет и ис­полнитель перейдет к команде 7. Закрыть и опечатать дверь ваго­на, следующей за условием 6.

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

В этом случае весь записанный ранее алгоритм будет представ­лять собой цикл, повторяемый при условии наличия контейне­ров, причем проверка выполнения этого условия тоже включает­ся в цикл:

1.                 Начало цикла.

2.                 Пока есть контейнер для погрузки, выполнять действия:

3.                 Поднять краном очередной контейнер.

4.                 Переместить контейнер к вагону.

5.                   Погрузить контейнер в вагон.

6.                  Вернуть кран в исходное положение.

7.                     Пока в вагоне есть свободное место, повторять действия цикла.

8.                Конец цикла.

При нарушении либо условия 2, либо условия 7 исполнитель переходит к действию, следующему за строкой 8. Конец цикла.

Мы рассмотрели два вида циклических алгоритмов: с предва­рительным условием (предусловием) и с последующим условием (постусловием).

Рассмотрим второй вариант циклических алгоритмов — с заданным заранее количеством повторений. Как уже было ска-

21

зано, по таким алгоритмам работают исполнители, не умеющие оценивать выполнение (или невыполнение) того или иного усло­вия, но зато умеющие работать с числами.

Например, на химическом предприятии нужно обеспечить ав­томатическое заполнение жидкостью 10 резервуаров. Счетчик ко­личества повторяющихся операций в исходном состоянии уста­новлен на ноль. Резервуары расположены в один ряд, вплотную друг к другу.

Шланг, из которого вытекает жидкость, может перемещаться вдоль резервуаров и в исходном положении находится вблизи пер­вого резервуара.

Каждый резервуар имеет указатель, сигнализирующий о его заполнении. Алгоритм заполнения резервуаров может быть следу­ющим:

/. Начало цикла.

2.                Переместить шланг на ширину резервуара.

3.                   Открыть вентиль на шланге.

4.              Проверить наличие сигнала указателя о заполнении резервуара.

5.                 При поступлении сигнала закрыть вентиль.

6.                Увеличить содержимое счетчика на 1.

7.               Пока содержимое счетчика не превысит 10, повторять дей­ствия.

Это алгоритм с постусловием, так как только после запол­нения очередного резервуара определяется, нужно ли повто­рять операцию заполнения еще раз (т.е. заполнены ли все 10 резервуаров). Но можно составить этот алгоритм и с предусло­вием:

1.             Пока содержимое счетчика меньше 10, выполнять действия:

2.                Увеличить содержимое счетчика на 1.

3.                 Переместить шланг на ширину резервуара.

4.                   Открыть вентиль на шланге.

5.             Проверить наличие сигнала указателя о заполнении резервуара.

6.                 При поступлении сигнала закрыть вентиль.

7.                 Конец цикла.

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

В двух последних алгоритмах фактически присутствует провер­ка условия Если сигнал указателя поступил... Очередное действие ...закрыть вентиль выполняется только при ответе «Да», т.е. этот участок алгоритма содержит ветвление. Но так как мы рассматри­ваем организацию циклов, на которую наличие ветвления внутри цикла не влияет, этот участок алгоритма приведен без излишней детализации.

22