В реальной жизни не все так просто. Вы захотели съесть бутерброд, открыли хлебницу — а хлеба в ней нет! Что делать? Если очень хочется есть, то придется пойти в магазин, купить хлеб и принести его домой. Таким образом, ваши действия будут зависеть от условия: есть ли хлеб в хлебнице?
В этой ситуации последовательность ваших действий после появления желания съесть бутерброд будет следующей:
/. Открыть хлебницу.
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