Способы описания алгоритмов. Разновидности структур алгоритмов

Определение алгоритма. Структурная схема алгоритма. Виды блоков структурной схемы. Их назначение согласно ГОСТ. Правила построения структурной схемы алгоритма. Линейная, разветвляющаяся и циклическая структуры алгоритмов.

Алгоритм и его свойства

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

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

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

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

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

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

Алгоритмизация - техника составления алгоритмов и программ для решения задач на ЭВМ.

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

К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления:

а) словесный (записи на естественном языке);

б) структурно - стилизованный (записи на языке псевдокода);

в) программный (тексты на языках программирования);

г) графический (схемы графических символов).

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

Пример. Записать алгоритм нахождения наибольшего общего делителя двух натуральных чисел (m и n) на естественном языке. При таком словесном способе содержание алгоритма может быть следующим:

1) если числа равны, то необходимо взять любое из них в качестве ответа, в противном случае - продолжить выполнение алгоритма;

2) определить большее из чисел;

3) заменить большее число разностью большего и меньшего чисел;

4) повторить алгоритм с начала.

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

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

Определение принадлежности точки треугольнику (действ XA, YA, XB, YB, XC, YC, XD, YD целое z лит а);

арг XA, YA, XB, YB, XC, YC, XD, YD;

рез z,а;

нач

действ S1, S2, S3, S4

вычислить значение S1, равное площади тр-ка АВС;

вычислить значение S2, равное площади тр-ка АВD;

вычислить значение S3, равное площади тр-ка АСD;

вычислить значение S4, равное площади тр-ка СDВ;

если S1 = S2+S3+S4

то z := 1,

а := “точка внутри треугольника”,

иначе z := 0,

а := “точка вне треугольника”,

все

напечатать значение а:

кон

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

Пример. Программа на языке Бейсик перевода температуры из градусов Цельсия в градусы Фаренгейта.

PRINT “Перевод температуры из град. Цельсия в град. Фаренгейта”

6 PRINT “Укажите температуру в град. Цельсия”

INPUT C

IF C = 9999 THEN 7

F = C*1.8 +32

PRINT C, F

GOTO 6

7 END

Для графического изображения алгоритмов используются графические символы. Наиболее распространенными являются блочные символы (блоки), соединяемые линиями передач управления. Существует государственный стандарт на выполнение графической записи алгоритма. Графическая запись алгоритма является наиболее наглядной. Перечень условных графических символов, их наименования, форма, размеры и отображаемые функции устанавливаются ГОСТ 19.003-80. Основные графические символы, используемые для описания алгоритмов, приведены в перечисленной литературе [1, 2].

Схема алгоритма перевода температуры из шкалы Цельсия в шкалу Фаренгейта приведена ниже. Перевод осуществляется по формуле:

Температура по Фаренгейту = (температура по Цельсию) * 180/100 +32
СХЕМА

 
 

 


Схемы алгоритмов

Использование схем позволяет представить алгоритм в наглядной форме, поэтому они наиболее часто используются.

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

 

V:= выражение

 
 


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

 
 


ДА НЕТ

Условие?

 

Если условие выполняется, то есть имеет значение ДА, то следующим выполняется этап по направлению ДА. Если условие не выполняется, то осуществляется переход по направлению НЕТ.

Начало и конец вычислительного процесса изображаются овалом, в котором записываются слова “Начало” или “Останов”.

 

При решении задач на ЭВМ исходные данные задаются при вводе в машину. Ввод данных может осуществляться разными способами, например, с клавиатуры, с перфоленты, с диска и т. д. Задание численных значений исходных данных мы будем называть вводом, а фиксацию результатов расчета выводом. Ввод исходных данных и вывод результатов изображаются параллелограммом. Внутри него пишется слово “Ввод” или “Вывод” и перечисляются переменные, подлежащие вводу или выводу.

 
 

 

 


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

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

 

 
 


Комментарий

       
   
 
 


По стандарту высота блока равна а, ширина 2а, где размер а выбирается из ряда 10, 15, 20, мм. Блоки “начало” и “конец” имеют высоту 0.5а.

Линии потока проводят параллельно внешним краям рамки листа. Направление линий потока сверху вниз и слева направо принимают за основное; если линии потока основного направления не имеют изломов, то их направление стрелками можно не обозначать. В остальных случаях направление линий потока обозначать стрелкой обязательно. Записи внутри символа или рядом с ним должны выполняться машинописью или чертежным шрифтом и должны быть краткими. В левом верхнем углу в разрыве линий ставится номер блока.

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