Приложение А. Соглашения, принятые

для опи£аи14Я алгоритмов

В этом приложении содержится объяснение соглашений, которые применялись при изложении алгоритмов в этой книге. Мы говорим «соглашения», а не «правила», потому что они не подразумеваются зафиксированными раз и навсегда; наоборот, подразумевается, что эти соглашения достаточно гибкие для того, чтобы изложить любой алгоритм в виде, удобном для чтения и понимания.

Далее следует пример (из разд. 1.2) формы, в которой были описаны алгоритмы.

Algorithm МАХ. Даны n действительных чисел в одномерном массиве r{1), r(2), . . ., r{n); найти такие м и j, что M=rIj)= max r{k)- В случае, когда два или более элементов r имеют

наибольшее значение, выбирается наименьшее значение J. Шаг 0. [Инициализация] Set 7И-<-/?(1); and У-«-1. Шаг 1. [yV=l?] If yV=l then STOP fi.

Шаг 2. [Проверка каждого числа] For к-(-2 to n do шаг 3 od; and STOP.

Шаг 3. [Сравнение] If M<:r(k) then set Mr{k); and j k- (Теперь M - наибольшее число из проверенных, а к - его номер в массиве.) В оставшейся части этого приложения объясняется этот формат.

Общий формат. Общий формат изложения алгоритма проиллюстрирован ниже.

Algorithm ИМЯ ( ). Описание назначения алгоритма вместе с описанием соответствующих параметров и переменных ввода и вывода.

Шаг 0. [ ] Операторы.

Шаг 1. [ ] Операторы

(Комментарии.)

Шаг 2. [ ] Операторы.

Шаг к- [ ] Операторы. (Комментарии.)

Шаг к+1. I 1 Операторы.

Шаг n. [ ] Операторы.

Имя и описание. Начало «Algorithm ИМЯ ( )» выделено жирньш шрифтом. Описание алгоритма читается как абзац с последующими строками, продолжающимися вниз от левого края.

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

Algorithm SIS (Straight Insertion Sort - прямое включение) Algorithm PARSORT (PARallel Sort - параллельная сортировка)

Сразу за именем алгоритма следует краткое описание его назначения, включая описание требуемого ввода и получаемого вывода. Где необходимо, также дается описание появляющихся в алгоритме переменных, назначение которых не сразу очевидно.

Шаги. Перенумерованные шаги алгоритма - Шаг i - выделены курсивом и начинаются с левого края. Некоторые шаги могут быть дважды (трижды и т. д.) сдвинуты вправо, чтобы подчеркнуть логические уровни, повысить наглядность и т. п. Если для операторов внутри Шага i требуется больше одной строки, последующие строки начинаются ниже и правее номера шага.

Шаги алгоритма указываются обозначениями Шаг i, где i - неотрицательное целое число. Нумерация шагов всегда последовательная и начинается с О и.пи 1; Шаг О обычно используется д.пя установки в начальное состояние (инициализации) переменных или массивов. Шаг используется для определения смысловой логической единицы в детализированном изложении алгоритма, для которого дальнейшая детализация не кажется необходимой для понимания.

Скобки. Сразу за Шагом i следует краткая фраза, заключенная в скобки [ ], описывающая цель шага. Эти скобки могут бы1ь опущены в случае, когда цель шага очевидна и не требует объяснения. Скобки служат другой полезной цели, когда они используются для комментариев или замечаний по реализации алгоритма; это помогает прямо показать, где конкретный шаг реализован в кодах.

Пунктуация и комментарии к операторам. За фразой в скобках следует последовательность из одного или более операторов, отделенных точками с запятой (;). Эта последовательность оканчивается точкой. Сразу за последней точкой с запятой и перед последним оператором в последовательности может появиться слово and для удобства чтения. После всех операторов внутри шага могут появиться дополнительные комментарии, заключенные в круглые скобки; они используются для объяснения особенностей алгоритма или различных этапов вычислений.

Соглашения о языке операторов. Предполагается, что все операторы можно читать как предположения или как последовательность команд. Например, вместо того чтобы писать COST f-О, мы можем писать Set COST 0. В этом случае мы говорим, что Set - элемент языка операторов, тогда как COST- переменная, выбранная разработчиком алгоритма. Все слова языка операторов выделяются жирным шрифтом; к ним относятся:

and do else fi for goto if od set then through to while

Если с этих слов начинается предложение, начальные буквы - заглавные, например Set, Do, If.

Чтобы отличить имена переменных и логические операции от слов языка операторов, имена переменных и логические операции пишутся полностью заглавными буквами. Обращаем внимание на разницу между AND и and в следующем примере:

If /<10 AND /<10 then set II+l; and set JJ+{ fi.

Операторы присваивания. Операторы присваивания записываются с помощью стрелки (-«-). Слово set необязательно; например,

Set / 1 или

Set /1; J2; and K<-3.

Операторы If. Операторы if могут быть двух видов, а именно:

И KJ then set +1 fi или If KJ then set I I+l else set J J-1 fi.

После then и else могут появляться заключенные в скобки предложения, если они улучшают или понимание, или читаемость, или и то и другое; например.

If KJ then [исключаем вершину] set /-<- /-f 1

else [сдвигаем указатель] set PTR LEFT (PTR) fi.

Обычно мы рекомендуем ставить fi в конце оператора if, особенно когда его отсутствие может повлечь двусмысленность или неправильность оператора.

Рассмотрим оператор

И KJ then set I I+l

else set +1; К I.

Oh может быть интерпретирован одним из двух способов:

И KJ then set I I+l

else set JJ+1; set /4-1 fi.