Способы записи алгоритмов 2.3.1. Словесная запись

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

Словесная запись алгоритма — это запись последовательности действий на одном из языков человеческого общения.

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

Графическое представление

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

Графическое представление (блок-схема) алгоритма — это на­бор специальных графических символов, расположенных в по­рядке выполнения действий алгоритма.

Для этого способа записи алгоритмов используются стандар­тизованные графические обозначения (символы).

Начало алгоритма обозначается знаком

 

 

25

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

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

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

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

направлении ответа «Да», а если условие не выполнено — в на­правлении ответ «Нет»:

f - v * i

Часто для исполнения алгоритма необходим ввод информации в виде чисел или в иной форме. Результатом исполнения алгорит­ма (или его части) может быть вывод информации в том или ином виде. Операция ввода данных или вывода результатов обо­значается следующим образом:

27

 

 

 

Символ вызова вспомогательного алгоритма имеет вид

 

 

Есть и другие символы для обозначения различных операций в алгоритме.

Графические символы соединяются между собой прямыми ли­ниями в соответствии с последовательностью действий, ведущих к достижению цели. Стандартное направление перехода от симво­ла к символу — сверху вниз и слева направо. Если по каким-то причинам расположить символы в таком порядке не удается и переход к очередному символу должен произойти в ином направ­лении, то это направление указывают стрелкой.

28

Символ вызова вспомогательного алгоритма имеет вид

Составим блок-схемы некоторых из рассмотренных ранее ал­горитмов. Блок-схемы двух алгоритмов с ветвлением — «Взять хлеб» и сортировки изделий — приведены на рис. 2.1, 2.2. Они наглядно показывают преимущество графического представления алгорит­мов — легко прослеживается последовательность действий как при выполнении, так и при невыполнении проверяемого условия.

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

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

Линия возврата фактически заменяет строку Конец цикла, ог­раничивающую цикл снизу при словесном описании алгоритма,

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

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

Рассмотрим блок-схему циклического алгоритма погрузки кон­тейнеров из подразд. 2.2.3, где проверка условия повторения цик­ла производится после его исполнения (рис. 2.4). Вслед за симво­лом Начало следуют действия алгоритма, поэтому цикл исполня­ется всегда, как минимум, один раз. Если погрузка контейнера

30

привела к отсутствию свободного места в вагоне, то проверка ус­ловия сразу выводит на символ Конец. Линия возврата по-прежне­му охватывает цикл, указывая его нижнюю и верхнюю границы.

Блок-схема расширенного варианта этого алгоритма, содержа­щего условия, проверяемые как до, так и после выполнения ко­манд цикла (см. подразд. 2.2.3), показана на рис. 2.5. Проследите по этому рисунку ход исполнения алгоритма при различных комби­нациях условий наличия свободного места в вагоне и наличия контейнеров для погрузки.

Рассмотрим блок-схемы вспомогательных алгоритмов. У алго­ритма, используемого в качестве вспомогательного, есть одна осо­бенность: в нем производятся действия с информацией, передан­ной ему из основного алгоритма, и туда же при необходимости сообщается результат выполнения вспомогательного алгоритма. Поэтому блок-схема вспомогательного алгоритма содержит сим­вол ввода данных, а при необходимости — и символ вывода ре­зультатов, что подчеркивает взаимодействие вспомогательного алгоритма с основным.

На рис. 2.6 приведена блок-схема алгоритма «Нагрев до t». Сим­вол ввода данных указывает на получение из основного алгорит­ма значения температуры нагрева t. После выполнения алгоритма нагрева продолжается выполнение основного алгоритма с дей-

 

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

Алгоритмический язык

Словесное и графическое представления алгоритмов позволя­ют наглядно проследить последовательность действий как в про­стых, так и в сложных алгоритмах. Однако наглядность имеет зна­чение только для человека, но не для машины. Машина выполня­ет одно за другим действия, предписанные алгоритмом, который составил для нее человек.

Возможно, со временем машины научатся мыслить и смогут сами анализировать ситуации, создавать и выполнять алгоритмы, продвигаясь к ими же поставленным целям. У нас вызывает сегод­ня восхищение «умная» машина, обыгрывающая лучших гроссмей­стеров в шахматы. По сути же она просто быстрее, точнее, в боль­шем объеме и за меньшее время перебирает возможные варианты игры, которые заложил в нее человек. Так что единственный спо­соб заставить машину совершить какое-то действие — дать ей ко­манду, точно и однозначно соответствующую именно этому дей­ствию. Причем машина должна эту команду правильно и одно­значно понять.

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

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

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

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

32

Перед названием каждого алгоритма, записанного на алгорит­мическом языке, ставится служебное слово АЛГ (буквы заглав­ные, без точки). Для указания начала и конца алгоритма исполь­зуются служебные слова НАЧ и КОН. Каждый шаг алгоритма за­писывается отдельной строкой.

Общий вид линейного алгоритма на алгоритмическом языке:

АЛГ «<название>» НАЧ

<действие 1>

<действие 2>

КОН

Угловые скобки означают, что в данной строке должно быть записано то, что указано в этих скобках.

Для записи алгоритмов с ветвлением используются служебные слова ЕСЛИ, ТО, ИНАЧЕ, ВСЕ (конец ветвления). Общий вид ветвления:

ЕСЛИ <условие> ТО

<действие 1> ИНАЧЕ

<действие 2> ВСЕ

Запишем на алгоритмическом языке алгоритм, блок-схема ко­торого приведена на рис. 2.2.

АЛГ «Алгоритм сортировки изделий» НАЧ

поместить изделие в измерительное устройство

измерить диаметр изделия ЕСЛИ диаметр больше заданного ТО

поместить изделие в магазин № 1 ИНАЧЕ

поместить изделие в магазин № 2 ВСЕ КОН

Бывает так, что после строки ИНАЧЕ в алгоритме с ветвлени­ем располагается не действие, а новое условие. Тогда это второе условие вводится не в отдельной строке ЕСЛИ, а в той же строке, в которой находится ИНАЧЕ:

ИНАЧЕ ЕСЛИ <условие 2> ТО

<действие 2> ИНАЧЕ

<действие 3>

33

Последнее ИНАЧЕ относится к условию 2, т.е. соответствует невыполнению этого условия. Сочетание служебных слов ИНАЧЕ ЕСЛИ часто заменяют служебным словом ИНЕС.

В циклических алгоритмах используются служебные слова ПОКА, ЦИКЛ, КЦИКЛ (конец цикла). Общий вид циклического участка алгоритма:

а)                    с предусловием —

ПОКА <условие>

<действие> КЦИКЛ

б)                   с постусловием —

цикл

<действие> ПОКА <условие>

Запишем циклический алгоритм сортировки изделий, блок-схема которого приведена на рис. 2.3. Судя по блок-схеме, это алгоритм с предусловием. Поэтому верхней границей цикла явля­ется условие Есть изделия на конвейере! Далее следуют действия цикла, а расположение нижней границы КЦИКЛ показывает ли­ния возврата. Имеющееся в алгоритме ветвление входит в цикл и заканчивается перед концом цикла. Для удобства чтения алгорит­ма действия, образующие цикл, сдвигаются при записи вправо — так цикл легче увидеть. Аналогично можно сдвинуть участок с ветвлением. Алгоритм записывается в порядке продвижения по блок-схеме и выглядит следующим образом:

АЛГ «Циклический алгоритм сортировки изделий» НАЧ

ПОКА есть изделия на конвейере

поместить изделие в измерительное устройство

измерить диаметр изделия

ЕСЛИ диаметр больше заданного ТО

поместить изделие в магазин № 1 ИНАЧЕ

поместить изделие в магазин № 2 ВСЕ КЦИКЛ

кон

Рассмотрим последовательность действий в этом алгоритме. Пока предусловие Есть изделия на конвейере не нарушено, выполняется измерение диаметра изделия и оно помещается в магазин № 1 или № 2. Служебное слово ВСЕ означает конец ветвления, после которого следует переходить к следующей строке алгоритма. В ней помещено слово КЦИКЛ (конец цикла), требующее возврата к

34

началу цикла, т.е. к строке ПОКА, после чего цикл повторится. Когда условие в строке ПОКА нарушится, по правилам выполне­ния циклических алгоритмов надо будет перейти к строке, следу­ющей за указателем конца цикла КЦИКЛ (в нашем случае — это строка КОН), и выполнение алгоритма заканчивается.

Запишем на алгоритмическом языке более сложный алгоритм (см. рис. 2.5).

В этом алгоритме, как видно из блок-схемы, есть и предусло­вие (Есть контейнер для погрузки?), и постусловие (В вагоне есть свободное место?), поэтому в нем сочетаются записи в виде ПОКА... КЦИКЛ и в виде ЦИКЛ...ПОКА.

Первый элемент блок-схемы при продвижении от начала алго­ритма — линия возврата, идущая от символа постусловия. В алго­ритмах с постусловием она указывает место, с которого возоб­новляется цикл при его повторении. В алгоритмическом языке это место обозначается служебным словом ЦИКЛ.

Далее расположен графический элемент предусловия, вводи­мого словом ПОКА, после которого идет последовательность дей­ствий вплоть до постусловия. Постусловие тоже вводится служеб­ным словом ПОКА. Если условие выполнено, то в алгоритмах с постусловием следует возврат к строке ЦИКЛ, а если не выпол­нено — переход к следующей за постусловием строке (в нашем случае — к окончанию алгоритма КОН).

Все это происходит, если не нарушено предусловие Есть кон­тейнер для погрузки. Когда же это условие нарушено, в алгоритмах с предусловием происходит переход к строке, следующей за ука­зателем конца цикла КЦИКЛ (в нашем случае — к окончанию алгоритма КОН).

В итоге этот алгоритм на алгоритмическом языке записывается следующим образом:

АЛГ «Алгоритм погрузки контейнеров» НАЧ

ЦИКЛ

ПОКА есть контейнер для погрузки

поднять очередной контейнер

переместить контейнер к вагону

погрузить контейнер в вагон

вернуть кран в исходное положение ПОКА в вагоне есть свободное место КОН

КЦИКЛ

кон

Сдвиг строк при записи позволяет легко сориентироваться, где начинается и заканчивается цикл ПОКА...КЦИКЛ, а где ЦИКЛ... ПОКА.

35

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

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

АЛГ «<название>» НАЧ

<действие                               1>

<действие                              2>

<название                             вспомогательного алгоритма 1>

<действие                              3>

<название                             вспомогательного алгоритма 2>

<действие                              4> КОН

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

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

Контрольные вопросы

1.            Сформулируйте понятие алгоритма.

2.            В чем особенность восприятия алгоритмов машинами?

3.        Дайте определение программы.

4.             Назовите виды алгоритмов.

5.             Что такое линейный алгоритм? Приведите пример.

6.              Что такое условный алгоритм? Приведите пример.

7.           Что такое циклический алгоритм? Приведите пример.

8.             Что такое вспомогательный алгоритм? Приведите пример.

9.             Расскажите о способах записи алгоритмов.

10.                Изобразите и поясните графические символы, применяемые для записи алгоритмов.

11.           Что такое блок-схема алгоритма?

12.            Сформулируйте понятие алгоритмического языка.

ГЛАВА 3