3.2. Формы представления алгоритмов

Алгоритмы имеют несколько форм представления: словесную, формульно-словесную, табличную, в виде блок-схем.

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

Пример: Записать алгоритм вычисления y по формуле:

1) умножить x на3;

2) к результату первого действия прибавить 1;

3) из результата второго действия извлечь корень;

4) умножить x на x;

5) из результата четвертого действия вычесть 3;

6) результат пятого действия разделить на результат третьего. Полученный результат считать значением y.

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

Пример: Выражение

задает объем усеченного конуса. Здесь h-высота, R и r - соответственно радиусы нижнего и верхнего основания.

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

Пример: Для предыдущей формулы составим табличную запись алгоритма (рис. 3.1)

R	r	H	h	1/3h	R2	Rr	r2	R2+Rr+r2	V
									

Рис.3.1. Табличная запись алгоритма

Второй тип таблицы называется решающей таблицей. В простейшем случае она включает 4 части: перечень условий, указатель условий, перечень действий, указатель действий (рис.3.2).

Перечень условий содержит все условия, а перечень действий - все действия, проверка и выполнение которых необходимы в процессе решения задачи. Они располагаются одно за другим; в строке записывается только одно условие или действие. Правая часть делится на несколько столбцов, в которых определяется, какие условия следует проверить, а какие действия следует выполнить в результате проверки этих условий. На пересечении соответствующих столбцов и строк ставится Y в том случае, если условие должно выполняться, N - если нет и "-", если условие не учитывается.

	Номер таблицы	1	2	3		k
Перечень  условий  	Условие 1	Y	N	Y		N	 Указатель  условий 
	Условие 2	-	Y	Y		N
						
	Условие m	Y	-	Y		-
Перечень  действий  	Действие 1	X		X			 Указатель  действий 
	Действие 2		X			X
						
	Действие n	X		X		X

Рис.3.2. Общий вид решающей таблицы

Когда условие требует выполнения некоторого действия, то на пересечении соответствующих столбцов и строк, ставится символ X. В случае отсутствия действия позиция остается незаполненной.

Если условие формируется так, что возможны два ответа, "да" - "нет" или "Y" - "N", то таблицы называются таблицами с ограниченными входами. Если ответов несколько, то таблицы называются таблицами с расширенными входами. При этом простое условие записывается так же, как и в таблицах первого вида, сложные действия распределяются между столбцами.

Пример: Алгоритм поиска HOD в виде решающей таблицы с расширенными входами показан в таблице 3.2.

Таблица 3.2.

Таблица № 0001	1	2	3
Условие проверки	a > b	a < b	а = b
a = a – b	X
b = b – a		X
Перейти к началу	X	X
НОД = а (или b)			X
Конец			X

Блок-схемой называется графическое изображение алгоритма, дополненное элементами словесной записи, в котором каждое предписание алгоритма представляется в виде геометрического символа, имеющего определенную конфигурацию в зависимости от характера выполняемой операций или отображаемой функций.

Для однозначного обозначения одинаковых процедур формы, размеры и правила оформления определены ГОСТ 19.003-80 «Схема алгоритмов и программ. Обозначения условные и графические» и ГОСТ 19.002-80 «Схема алгоритмов и программ. Правила оформления».

Наиболее употребительные символы приведены в табл. 3.3.

При начертании символов их размеры выбираются кратными 5, размер (а) равным 10,15,20.... размер (b) составляет  b=1,5a.

Табл. 3.3

№ п/п	Название Символа	Обозначения и размеры	Отображаемые Функции
1	Процесс		Выполнение действий или последовательности действий
2	Решение		Выбор направления выполнения алгоритма в зависимости от некоторого условия
3	Модификация (подготовка)		Выполнение операций, меняющих команды или группы команд. Начало цикла
4	Типовой процесс		Вычисления по подпрограмме, стандартной программы
5-6	Данные		Ввод исходных данных или вывод результатов
7	Документ		Вывод, печать результатов на бумаге
8	Перфокарта		Ввод и вывод данных, носителем которых являются перфокарты
9	Процессор (оперативная память)		Операция по преобразованию информации
10	Магнитный диск		Ввод вывод данных, носителем которых является магнитный диск
11	Магнитная лента	a	Ввод вывод данных, носителем которых является магнитный ленте
12	Пуск - остановка (знак завершения)		Начало, конец, алгоритма, вход и выход в подпрограмму
12	Линии потока		Указание последовательности связей между символами
13	Соединитель		Указание связей между прерванными линиями
14	Межстраничный соединитель		Указание связей между элементами схемы, расположенными на разных местах

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

Выходы символа "Решение" помечаются символами "да"/"нет"- т.е. выполняется или не выполняется условие. Условие записывается внутри символа (рис.3.4). Содержание надписи внутри символа или рядом должно быть кратким, без сокращений, за исключением допустимых сокращений. Записи представляются так, чтобы их можно было читать слева направо, сверху вниз.

Для удобства нахождения символа задаются их координаты в виде цифр, букв или цифр и букв. Они представляются сверху слева в разрыве контура (рис.3.5).

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

Для блок-схем обязательны следующие правила: каждый блок имеет только один вход и выполнение описанных в них действий всегда начинается с первого; входить в середину блок-схемы нельзя. Вход в блок-схему обозначается символом "начало", заканчивается блок-схема символом "конец".

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

Межстраничный соединитель маркируется двумя строками символов: первая строка определяет лист, вторая является идентификатором самого соединения (рис.3.7).

В качестве примера рассмотрим блок-схему алгоритма Евклида нахождения НОД двух чисел (рис.3.8).

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

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

Логические описывают условия, от которых зависит направление решения.

Варьирующие предусматривают изменение вспомогательных величин, называемых параметрами. Обычно параметры являются либо номерами изменяемых объектов, носящих одинаковые номера (массивы), либо номерами операторов, по какой-то причине объединенных в одну группу.

Полная последовательность операторов, задающая весь процесс решения, называется схемой решения. Операторы на схеме обычно обозначаются условными (стандартными) символами. Наиболее употребительными являются следующие:

Nо - начало процесса;

В - ввод исходных данных;

D(A) - действующий (арифметический);

Р - логический;

V - варьирующий;

W - оператор печати (вывода);

E - оператор останова.

Знаки переходов имеют вид полускобок с числовыми индексами. Левыми полускобками ₃ ⁵ указывается передача управления. Правая нижняя полускобка указывает прием управления ₃^ ₅^, она может соответствовать как верхнему, так и нижнему знакам передачи управления Соответствие определяется равенством числовых индексов После логического оператора могут стоять верхняя и нижняя полускобка передачи управления. Верхняя полускобка соответствует " да ", т.е. выполнению условия. Нижняя полускобка соответствует невыполнению условия, т.е. " нет " Р ( а > б ) ₃ ⁵.

Операторы получают номера индексов согласно порядка их действия. Если оператор зависит от параметров, например i, j, то он обозначается так и т.д. Условие записывается в виде функции, где в скобках указывается соответсвующее условие. Варьирующие изменяют параметры V ( i,j ). Операторная схема алгоритма Евклида имеет вид:

N₀ B₁ (a,b) ₁^ P₁(а>b)_² P₂(b>a) _^3 _{4 2}^ D₁(а=a-b) ^ _{1 3}^

D₂ (b=b-a)^_{1 4}^ D₃(НОД=а(b))W₁ E_1.