Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

а) Точка входа или выхода

Операционный блок (функциональный узел)

Решающий блок (предикатный узел)

Циклическая конструкция

Поток управления

б)

Цикл «Уcл4>^ Не «Усл4»

s7

Цикл «Усл4»

\/

s8

( )

ГЦикл «Усл2» Не «Усл2»

Нет

< ^ У с л З ^

Да

s4

s5

1

s6

1

Цикл «Усл2»

f Конец J

Рис. 3. Схема алгоритма:

а) основные обозначения; б) пример использования

а)		Заголовок программы
Программа		Тело программы
Простая	конструкция	Оператор
Условная	конструкция
Циклическая конструкция		Условие
		Тело цикла
б)	Пример программы
		s1
т		Усл1	F
	s2	Усл2
		т \ УслЗ	/ ^
	S3	s4	s5
		s6
Усл4		s7
		s8
	Рис. 4. Диаграмма	Нэсси-Шнейдермана:
а)	графические элементы; б) пример использования
2.1.2. Структурное и модульное программирование
Применительно к решению задачи на ЭВМ, можно сформули­
ровать, что алгоритм, или программа для вычислительной			машины

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

В 1965 г. профессор Эйндховенского университета Дейкстра (Нидерланды) начал пропагандировать стиль программирования, получивший название "программирование без оператора goto (без­ условного перехода)", первоначально принятый большинством про­

граммистов негативно. Однако, в течение нескольких	последующих
лет этот же стиль, получивший название структурного	программи-

21

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

а) Состояние Р-схемы
Совмещение двух состояний в
одно (цикл)
Дуга Р-схемы	Условие
	Действие
Усл1	склгыэ
б)
	Усл4
	s7

Рис. 5. Р-схема:

а) графические элементы; б) пример использования

Основными управляющими конструкциями структурного про­ граммирования являются:

•СЛЕДОВАНИЕ - если в записи алгоритма (программы) подряд написаны несколько действий (операторов) друг за другом, то они

	будут выполняться последовательно в таком же порядке.
•	ЕСЛИ-ТО-ИНАЧЕ - условная конструкция,		определяющая раз­
	ветвление в порядке выполнения действий (операторов). Дослов­
	ный перевод этой конструкции if-then-els е.
•	ЦИКЛЫ. В структурном программировании		предусмотрены цик­
	лические	конструкции трех видов:
	1.	Цикл с предусловием ПОКА-ДЕЛАЙ: пока истинно		некото­
рое условие, делай то-то и то-то (дословный английский				перевод
этой конструкции while).
	2.	Цикл с постусловием ПОВТОРЯЙ-ПОКА	(do-while).	Отли­

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

22

3. Цикл с заранее заданным числом повторений (Jor).

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

Ветвление (условная	конструкция)
1) Общий случай (рис. 6 <з)

"ЕСЛИ" УСЛОВИЕ	"ТО"ВЕТВЬ'ТО "ИНАЧЕ" ВЕТВЬ-ИНАЧЕ "ВСЕ"
а)	(«ЕСЛИ»)
(«ИНАЧЕ») Нет
	-4-
ВЕТВЬ-ИНАЧЕ	ВЕТВЬ-ТО

(«ВСЕ»)

б)	... («ЕСЛИ»)

(«ИНАЧЕ») Нет

ВЕТВЬ-ТО

			... («ВСЕ»)
			Рис. 6. Ветвление (условная конструкция):
			а) общий случай; б) частный случай
/ /	C++	реализация
±f(	А >	В	)
	D =	Е;	// ВЕТВЬ-ТО

23

/ / ...

else
{	С	=	F/	//	ВЕТВЬ-ИНАЧЕ
/ / . . .
}
	2) Частный случай (см. рис. 6 б)
				"ЕСЛИ" УСЛОВИЕ	"ТО" ВЕТВЬ-ТО "ВСЕ"
//	C+-h			реализация
±f(	А	>	В	)
{	D	=	Е;	//	ВЕТВЬ-ТО
/ / . . .

;

Циклы

1) С предусловием (рис. 7, 8). Пример

SUMMA = Y,I

"ПОКА" УСЛОВИЕ "ДЕЛАТЬ" ТЕЛО-ЦИКЛА "ВСЕ"

//C++: ЦИКЛ С ПРЕДУСЛОВИЕМ

SUMMA = 0 / 1 = 1 /									//	ПОДГОТОВКА	ЦИКЛА
while		(	I	<=	20	)
{	SUMMA			+=	I/				//	Эквивалентно	SUMMA = SUMMA + I;
}	I	+=		1/
//	C++:		ЦИКЛ		FOR		(CM,	РИС,		8)
for(	1=1/				I	<=	20/	I++	)
//	I++		эквивалентно					1 =	1 +	1 /
{	SUMMA			+=		I/
}

2) С постусловием (рис. 9). Пример: SUMMA =20 ^I

"ПОВТОРЯЙ" ТЕЛО-ЦИКЛА "ПОКА" УСЛОВИЕ

//C++: ЦИКЛ С ПОСТУСЛОВИЕМ

SUMMA = 0 / 1 = 1 /

// ПОДГОТОВКА ЦИКЛА

24

do

{				//	Эквивалентно	SUMMA = SUMMA + J ,
SUMMA		-h=	I;
I	+=	1;
}
while(	I	<= 20	)	;
					SUMMA = 1 + 2 + ... + 20
					SUMMA:=0;
						I := 1;
						(«ПОКА»)
	SUMMA := SUMMA + I;					УСЛОВИЕ
		I :=! + 1;			(«ДЕЛАТЬ»)
		ТЕЛО-ЦИКЛА				Нет («ВСЕ»)

Вариант по ГОСТ

SUMMA:=0;

I := 1;

Цикл «I» I > 2 0

SUMMA := SUMMA+1;

I := 1 + 1;

Цикл «I»

Рис. 7. Цикл с предусловием (while)

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

25

ные подзадачи, оформленные в виде отдельных модулей, которые в языках Си/С-ь+ называются функциями.

Вариант по ГОСТ

SUMMA := 0;
Цикл «I»		1, 20, +1 - начальное, конечное
I > 2 0		значения "1" и шаг изменения "1"
SUMMA	:=
SUMMA	+ I

Цикл «I»

Рис. 8. Цикл с предусловием {for)

Для определения рационального размера функции и количест­ ва ее параметров можно использовать "правило семь ± два". Смысл этого правила заключается в том, что человек хорошо вос­ принимает до семи некоторых элементов - параметров функции, операторов языка программирования и т.п. Таким образом, при хо­ рошо выполненной декомпозиции размер функции не превосходит обычно 2 5 - 8 1 строк текста, а количество параметров не превышает

5 - 9 . Размер функции 2 5 - 8 1	строк текста получается, если в ее бло­
ке содержится не более 5 - 9	элементарных конструкций, каждая из

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

Модульное программирование, получившее также название

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

26

		Вариант по ГОСТ
SUMMA= 1 + 2 + ... + 20
		SUMMA:=0;
		I := 1;
SUMMA:=0;
I := 1;		Цикл «I»
	(«ПОВТОРЯЙ»)
SUMMA := SUMMA + I;		SUMMA := SUMMA + I
I := I + 1;	ТЕЛО-ЦИКЛА	I := I + 1;
	(«ПОКА»)	I > 2 0
	УСЛОВИЕ
		Цикл «I»

Нет

Рис. 9. Цикл с постусловием

2.2. Язык программирования и его описание (на примере языков Си/С++)

Совокупность понятий, относящихся к указанной в заголовке теме, иллюстрирует рис. 10. На нем сразу же обращают на себя вни­ мание слова "ЯЗЫК ПРОГРАММИРОВАНИЯ", "АЛФАВИТ", "СИНТАКСИС + СЕМАНТИКА" и "цветок с лепестками". Обсудим эти понятия подробнее.

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

1. Он должен быть достаточно простым^ чтобы быть доступ­ ным широкому кругу людей.

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

3.Алгоритм, записанный на некотором языке, должен быть сначала переведен на машинный язык ЭВМ. Переводом занимается

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

функционировании транслятора.

27

Этим требованиям в достаточной степени удовлетворяют язы­ ки Си/С++.

Языки Си/С++, как и любые другие языки программирования, полностью определяются заданием их алфавита (словаря исходных символов), точным описанием их синтаксиса (грамматики) и се­ мантики (смысла) - "СИНТАКСИС + СЕМАНТИКА" (см. рис. 10).

	- напоминает о том, что, например, буквы греческого алфавита
		использовать нельзя
	ж нельзя пользоваться римскими символами
		/* */
		\ \п \г \t	\"	\'
		и др.
		/ * + - ;	%	»	«
		< > < = > =	== !=
		& I - '^ ! . - > { } ( ) &&
		: = += - = *= /= %=			» = « =
	Строч­	&= 1= '^= [ ] ++			- ,
		Только в языке C++
	ные и
		:: // .* ->*
	пропис­
		и др.
	ные ла­
	тинские	Специальные символы
	буквы
	J..	АЛФАВИТ (ЛИТЕРЫ)
		СИНТАКСИС + СЕМАНТИКА
	Простота				Однозначность
	ЯЗЫК ПРОГРАММИРОВАНИЯ
	Рис. 10. Язык программирования и его описание
	Алфавит	языка - набор основных			символов (литер), исполь­

зуемых для записи алгоритма. На рис. 10 изображены литеры языков Си/С++ - три "лепестка цветка". Следует отметить, что некоторые литеры алфавита являются составными, изображаются двумя или тремя символами, но рассматриваются как неделимые (например,

"+=" или	" » = " ) .
Рис. 1 1 содержит информацию о способах		описания	синтакси­
са языка,	где обращают на себя внимание две фамилии — Д. Бэкус и
Н. Вирт	и приведена информация, касающаяся	способов	описания

28

синтаксиса языка, предложенных Д. Бэкусом и Н. Виртом в проти­ вопоставлении друг другу (две параллельных колонки).

Из допустимых символов языка, указанных на рис. 10, можно писать программу на языке Си/С++, но не в произвольном виде, а в соответствии с синтаксисом языка. Удобными способами описания синтаксиса языка являются следующие способы.

1. Использование	металингвистических	формул (предложены
Д. Бэкусом, автором языка АЛГОЛ-60).
2. Синтаксические	диаграммы (предложены Н. Виртом, авто­
ром языка Паскаль).

На рис. 11 приведены определения одних и тех же понятий как через металингвистические формулы, так и через синтаксические

диаграммы.
Металингвистическая	формула позволяет определить некото­

рое понятие путем перечисления всех его значений. Она использует следующие обозначения:

"::=" - знак, который читается как "это есть по определению"; <Определяемое_понятие> - пишется слева от "::=";

I - обозначает "ИЛИ";

( ) — круглые скобки, обозначают "И"; { } — фигурные скобки, обозначают неограниченное повторение

ноль, один, два и т.д. раз, заключенной в них конструкции; [ ] — квадратные скобки, обозначают необязательность конст­

рукции, заключенной в эти скобки.

Из рис. 11 следует, что в языке Си два имени, имеющие совпа­ дающие восемь первых символов, будут восприниматься одинако­ выми. Вместе с тем отметим, что в интегрированных средах про­ граммирования на языке C++ различимая длина идентификаторов может задаваться программистом с помощью соответствующей оп­ ции. Прописные и строчные буквы идентификаторов различимы. Так, в частности, ALPHA и alpha - разные идентификаторы.

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

29