Словесная запись алгоритмов

Лекция 5,6 Определение алгоритма, его свойства. Способы описания.(Алгоритмизация)

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

1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.

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

3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.

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

5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.

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

1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.

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

3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.

Средства записи алгоритмов

Словесная запись алгоритмов

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

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

К настоящему времени в информатике сложились вполне определенные традиции в представлении алгоритмов.

Самой распространенной формой представления алгоритмов, адресуемых человеку, является обычная словесная запись. В этой форме могут быть выражены любые алгоритмы. Но если такой алгоритм предназначен для его дальнейшей реализации на вычислительном устройстве, то принято придерживаться более формализованного способа построения фраз с тщательно отобранным набором слов. Кроме того, необходимо указывать начало и конец алгоритма, отмечать момент ввода в вычислительное устройство значений исходных данных и вывода/печати полученного результата. В вычислительных алгоритмах широко используется общепринятая математическая символика, язык формул. Вводится необходимая в вычислительной практике операция присваивания: y:=A

(читается: «у присвоить значение А»), где у — переменная; А — не-которое выражение/формула. Следует сначала выполнить все действия, предусмотренные формулой А, а затем полученный результат сохранить в качестве значения переменной y. Выражение A в частном случае может быть переменной или числом. Например,

х:= sin a — присвоить переменной х значение синуса;

у:= х — присвоить переменной у значение переменной х;

Z:= 5,7 — считать значением переменной z число 5,7;

к:= к + 1 — значение переменной к увеличить на единицу.

Введенные соглашения позволяют представлять словесные алгоритмы в компактной и наглядной форме.

Пример Составим алгоритм определения максимального числа из трех чисел: z = mах(а, b, с).

Решение. Решение задачи на ЭВМ можно получить, действуя следующим образом. Сначала найдем наибольшее из двух чисел, например, сравнив между собой а и Ь. Предположим, что исполнитель может выполнить операцию сравнения «больше». Найденное наи-большее число сохраним как значение переменной z. Далее сравним значение переменной z с оставшимся числом с. Если с больше z, то присвоим г новое значение — значение с, в противном случае значение z останется прежним. В результате переменная z будет равна наибольшему из а, b, с и будет являться искомым результатом.

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

Начало.

1. Ввести а, b, с.

2. Если а > b, то z:= а, иначе z:= b.

3. Если с > z, то z:= с.

4. Вывести z.

Конец.

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

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

В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица 1

символ	название	интерпретация
	данные	данные, носитель данных не определён
	процесс	функция обработки данных любого вида (выполнение определённой операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться)
	предопределённый процесс	предопределённый процесс, состоящий из одной или нескольких операций или шагов, которые определены в другом месте (в подпрограмме, модуле)
	подготовка	модификация команды или группы команд с целью воздействия на некоторую последующую функцию
	решение	решение или функция переключательного типа, имеющая один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определённых внутри этого символа; соответствующие результаты вычислений могут быть записаны по соседству с линиями, отображающими эти пути
	граница цикла	начало и конец цикла; обе части имеют один и тот же идентификатор; условия инициализации, приращения, завершения, и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условия
	соединитель	выход в часть схемы и вход из другой части схемы; используется для обрыва линии и продолжении её в другом месте; соответствующие символы-соединители должны содержать одно и то же уникальное обозначение
	терминатор	вход из внешней среды и выход во внешнюю среду(начало и конец программы)
_______________	линия	поток данных или управления; для направлений справа -налево и снизу-вверх добавляются стрелки
- - - - - - - - - - - - - -	пунктирная линия	используется для обведения аннотируемого участка
- - - - - - - - - [	комментарий	пояснительные записи и примечания
______... _____	пропуск	пропуск символа или группы символов, в которых не определены ни тип ни число символов; используется только в символах линии или между ними; служит для отображения общих решений с неизвестным числом повторений.

 

 

Приведем основные свойства граф-схем.

1. Графическое представление.

2. Поддержка описания управляющей части алгоритма.

3. Возможность реализации синтаксического контроля.

4. Возможность проверки управляющей части алгоритма.

.

Пример 1 Рассмотрим задачу определения наибольшего общего делителя (НОД) двух целых положительных чисел М, N.

В математике известен алгоритм решения этой задачи — алгоритм Евклида, который заключается в последовательном делении сначала большего числа на меньшее, затем меньшего на полученный остаток, первого остатка на второй остаток и так до тех пор, пока в остатке не получится нуль. Последний по счету делитель и будет искомым результатом. Запишем алгоритм Евклида, рассматривая деление как много-кратное вычитание:

1) если числа равны между собой, то взять в качестве НОД любое из них;

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

Алгоритм Евклида может быть представлен следующей словесной записью:

Начало.

1. Ввести М, N.

2. Пока М<>N выполнять:

если М> N, то М:= М - N;

иначе N:= N - М.

3. НОД:= М.

4. Вывести НОД.

Конец.

Блок-схема алгоритма Евклида представлена на блок-схеме 6.1, где блок 1 есть подготовка цикла, блок 2 — управление циклом, блоки 3, 4,5 - тело цикла (разветвляющаяся структура), из них блоки 4, 5 яв­ляются блоками модификации значений переменных цикла М и N

 

Блок-схема алгоритма Евклида.

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

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

Именно так мы поступили при разработке алгоритма Евклида, при этом использовали и словесную форму записи, и блок-схему.

ГОСТ 19.701—90 (ИСО 5807-85) предусматривает использование циклической структуры общего вида (безотносительно к типу цикла), представленной в таблице1 (границы цикла).Условие продолжения или окончания цикла может быть указано как в верхнем, так и в нижнем блоке. Ее применение целесообразно только в простых алгоритмах, в более сложных она теряется в общей структуре алгоритма ввиду отсутствия явной передачи управления.

Структурограммы

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

1. Блок обработки (вычислений). Каждый блок является блоком обработки. Каждый прямоугольник внутри любого блока представляет собой также блок обработки.

Вычислить у:= sin х/( 1 +ах+Ьх 2)

 

2. Блок следования. Этот блок объединяет ряд следующих друг за другом процессов обработки.

у:= fl+sinx

z:=x2/ 2+tgx

 

3. Блок решения. Этот блок применяется для обозначения структуры ветвления. Условие располагается в верхнем треугольнике, варианты решения — по сторонам треугольника, процессы обработки — в нижних прямоугольниках. Если блок решения является сокращенным (отсутствует одна из ветвей), то структурограмма видоизменяется соответствующим образом.

 

Вывод X, У

 

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

 

 

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

 

 

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

Р ис. Структурограмма алгоритма Евклида

На рисунке приведен пример структурограммыагоритма Евклида.