Соглашения, принятые для описания алгоритмов

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

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

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

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

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

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

.

.

.

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

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

.

.

.

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

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

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

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

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

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

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

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

Соглашения о языке операторов.Все слова языка операторов выделяются жирным шрифтом; к ним относятся:

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

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

Set, Do, If.

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

IfI<10AND J<10then setI←I+1; and setJ←J + lfi.

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

Set ←1 или

Set←1; J ←2; and /←3.

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

IfI<J then setI ←I+1 fi или

If I<J then set I ←I+1

else set J ←J-1 fi.

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

If I<J then [исключаем вершину] set I ←I+1

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

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

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

If I<J then set I←I+1

else set J←J+l; K← 1.

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

If I<J then set I←I+1

else set J←J+l; K← 1 fi.

или

If I<J then set I←I+1

else set J←J+lfi; set K← 1.

В первом операторе К полагается равным 1, если только I не меньше J; во втором операторе К. полагается равным 1 независимо от значения I или J.

Операторы цикла. Операторы цикла появляются в разных формах; например,

1. Шаг i. [ ] Do шаг i+l while I≤M od.

Шаг i+1[ ] If COST(I, J) ≤ MIN

then set MIN←COST(I, J); andI←I+1 fi.

2. Шаг i. [ ] Do through шаг i+З while J>0 od.

Шаг i+l. [ ] Операторы.

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

Шаг i+3. [ ]Операторы.

Шаг i +4. [ ] Операторы.

Порядок выполнения цикла 2 следующий: выполняются шаги i+1, i +2 и i +З, затем проводится проверка, положительно ли J: J>0; если J≤0, то следующим выполняется шаг i+4; если J>0, то выполняются опять шаги i+l, i+2 и i+3 и J еще раз сравнивается с нулем и т. д. Предполагается, что где-то в пределах шагов i+l, i+2 или i+З значение J меняется; в противном случае существует возможность бесконечного цикла.

3. Шаг i. [ ] While PTR>0 do PTR ←LEFT (PTR) od.

4. Шаг i. [ ] WhileJ >0 do through шаг i+2 od.

Шаг i+l. [ ] Операторы.

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

Шаг i+З. [ ] Операторы.

Выполнение цикла while-do отличается от выполнения цикла do-while только тем, что в одной форме проверка осуществляется перед первым выполнением шага (шагов), предписанного оператором do, а не после. Использование od, как в форме 3, служит для опре­деления конца действия do; его применение идентично применению fi.

5. Шаг i. [ ] For I ←1 to N do шаг i+1 od.

Цель формы 5 — допустить выполнение типичного DO- или FOR-цикла с приращением, равным 1, вместо того, чтобы инициализиро­вать индексную переменную I и увеличивать ее внутри цикла do-while или while-do.

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

Библиографический список

1.	Киммел П. и др. Borland C++ 5: Пер. с англ. – СПб.: BHV – Санкт-Петербург, 2000. – 976 с.: ил.
2.	Керниган Б., Ритчи Д. Язык программирования С: Пер. с англ. – СПб.: Невский Диалект, 2000. – 352 с.: ил.
3.	Дейтел Х. Как программировать на С++. –М.: Бином, 2000.-1024с.
4.	Страуструп Б. Программирование: принципы и практика использования C++, исправленное издание = Programming: Principles and Practice Using C++ — М.: «Вильямс», 2011. — С. 1248. — ISBN 978-5-8459-1705-8.
5.	Айвор Хортон Visual C++ 2010: полный курс = Ivor Horton's Beginning Visual C++ 2010 — М.: «Диалектика», 2010. — С. 1216. — ISBN 978-5-8459-1698-3.
6.	Страуструп Б.. Язык программирования C++ = The C++ Programming Language / Пер. с англ — 3-е изд. — СПб.; М.: Невский диалект — Бином, 1999. — 991 с. — 3000 экз. — ISBN 5-7940-0031-7 (Невский диалект), ISBN 5-7989-0127-0 (Бином), ISBN 0-201-88954-4 (англ.).
7.	Страуструп Б. Язык программирования C++. Специальное издание = The C++ programming language. Special edition — М.: Бином-Пресс, 2007. — 1104 с. — ISBN 5-7989-0223-4.
8.	Герберт Шилдт Полный справочник по C++, 4-е издание = C++: The Complete Reference, 4th Edition — М.: «Вильямс», 2011. — С. 800. — ISBN 978-5-8459-0489-8.
9.	Дэвид Р. Мюссер, Жилмер Дж. Дердж, Атул Сейни C++ и STL: справочное руководство, 2-е издание (серия C++ in Depth) = STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, 2nd edition, (C++ in Depth Series) — М.: «Вильямс», 2010. — С. 432. — ISBN 978-5-8459-1665-5.
10.	Джесс Либерти, Дэвид Хорват. Освой самостоятельно C++ за 24 часа = Sams Teach Yourself C++ in 24 Hours, Complete Starter Kit — 4-е изд. — М.: Вильямс, 2007. — 448 с. — ISBN 0-672-32681-7.

11.	Стефенс Д. Р. C++. Сборник рецептов — КУДИЦ-ПРЕСС, 2007. — 624 с. — ISBN 5-91136-030-6.
12.	Крячков А.В., Сухинина И.В., томшин В.К. программирование на С и С++. Практикум. – М.: Горячая линия-Телеком, 2000. – 352 с.
13.	Подбельский В.В. Язык С++: Учебник. – М.: Финстат, 2000. – 356 с.
14.	Тимофеев В.В. С/С++. Программирование в среде С++ Builder 5. – М.: Бином, 2000. – 420 с.
15.	Фомин С.С., Подбельский В.В. Программирование на языке Си: Учебное пособие. – М.: Финстат, 1999. – 600 с.
16.	Фридман А.Л. Основы объектно-ориентированного программирования на языке С++: Учебный курс. – М.: Радио и связь, 1999. – 208 с.
17.	Шамис В.А. С++ Builder 4. Техника визуального программирования. – М.: Нолидж, 2000. – 656 с.
18.	Шилд Г. Программирование на Borland С++. – М.: Попурри, 1998. – 400 с.
19.	Беляев Ю.И., Предместьин В.Р., Колесников С.А. Принципы программирования на Си: Учебно-методическое пособие /Российский химико-технологический университет им. Д.И. Менделеева. Новомосковский институт. – Новомосковск, 2001. – 71 с.