3.5. Способы описания алгоритмов

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

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

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

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

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

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

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

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

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

Данные. Под данными понимаются некоторые постоянные и переменные величины. По назначению они делятся на арифметические, символьные и логические. Арифметическими называются данные, значениями которых являются числа; символьные (строковые) - наборы символов, заключенные в апострофы или кавычки (например: "информатика"); логические - это данные, принимающие только два значения: истина(1) и ложь(0). Арифметические данные представлены различными типами: целые, вещественные, вещественные с двойной точностью. Данные подразделяются на константы, переменные и массивы.

Константы в алгоритмах обозначаются своими значениями. Для обозначения переменных используют идентификаторы – имена переменных, начинающиеся с буквы. Массив это упорядоченная последовательность переменных, имеющих общее имя и отличающихся порядковыми номерами, которые указывают положение элемента в массиве. Массивы могут быть целыми, вещественными, символьными. Массивы могут быть одномерными, двухмерными и многомерными. Например: А[10,20] - массив (1:10,1:20), целый. В квадратных скобках указываются максимальные значения индексов, т.е. размерность массива.

Операции. При преобразовании данных с ними могут выполняться следующие операции: арифметические (сложение "+", вычитание "-", деление "/", умножение "" или "", степень "^" и т.д.); сравнения (больше ">", меньше "<", равны "=", неравны " ", меньше или равны " ", больше или равны " "); логические (коньюнкции "^", дезьюнкции "v " и т.д.) и строковые (соединения строк "+").

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

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

Примеры:

- арифметическое выражение;

(2x  3)  (x  8) - логическое выражение;

"персональный " + "компьютер" - строковое выражение.

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

< > -синтаксические понятия языка;

{ } - альтернатива, т.е. выбор одного из указанных внутри фигурных скобок параметров;

[ ] - необязательная альтернатива (т.е. выбор одного или нескольких параметров или отсутствие выбора из указанных выше скобок;

... - повторение, продолжение;

::= - разделение частей синтаксических правил.

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

Выделяются следующие операторы:

- оператор общей обработки;

- операторы ввода-вывода (чтения-записи);

- операторы управления;

- операторы описания данных.

Оператор общей обработки представляет собой конечное описание некоторого реально выполняемого элементарного действия. Сюда же относится и оператор присваивания: X :=B, где X-переменная или элемент массива; B-выражение соответствующего типа.

Оператор ввода предназначен для ввода и присвоения значений переменным или элементам массива, перечисленных в списке переменных.

Ввод [<имя устройства>]<список переменных>.

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

Ввод клавиатура <список переменных>.

Список переменных содержит список переменных или элементов массива любого типа:

<список переменных>::=A,B,C,...,D[2,3].

Оператор вывода предназначен для вывода информации на различные устройства.

Вывод [<имя устройства>]<список переменных>.

Имя устройства в операциях ввода и вывода можно не указывать. Тогда принимаются стандартные устройства: вывод на экран дисплея, ввод с клавиатуры.

Для вывода данных на печать можно использовать оператор:

Печать<список переменных>.

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

Оператор безусловного перехода имеет вид:

Перейти <метка>.

Операторы языка могут быть помечены меткой, отделяемой от оператора двоеточием ":". Метка представляет собой группу символов  перед оператором, на который передается управление или номер строки в записи алгоритма:

<метка>:<оператор>.

Оператор условного перехода имеет два формата:

а) если б) если

<условие> <условие>

то то

<список операторов1> <список операторов>

иначе все если

<список операторов2>

все если

Если условие истинно, то выполняется группа операторов в <списке операторов1>, если условие ложно, то выполняется группа операторов в <списке операторов2>.

Оператор выбор имеет следующий формат:

<параметр>

Условие <условие>

<список операторов 1>

Условие <условие>

<список операторов 2>

....

Иначе

<список операторов n>

Все-выбор

Операторы цикла имеют два формата: цикл-пока, цикл-до, описание которых имеет вид:

цикл-пока цикл-до

пока<условие> повторять

повторять <список операторов >

<список операторов> до <условие>

Все-цикл Все – цикл

Оператор обращения к процедуре имеет вид:

Выполнить<имя процедуры>[<список параметров>]

где <имя процедуры> - набор любых символов, начинающихся с буквы.

Например; Выполнить PROC [A, B, C].

Процедура имеет следующую структуру:

Процедура<имя-процедуры>[<список параметров>]

<список операторов>

Возврат

Процедура начинается с ключевого слова “процедура” и заканчивается ключевым словом “возврат”.

Оператор остановки предназначен для указания прекращения действий и записывается стоп.

Описание данных. Все переменные, массивы и другие объекты, используемые при описании алгоритма, должны быть описаны в соответствии с синтаксическими правилами:

<имя объекта> - <данные>, <тип данного>, [<начальное значение>, <диапазон>, <список значений>]

Например:

PI - переменная, вещественный, значение:=3,14;

A[10,20] - массив (1:10,1:20),вещественный, значение:=0;

KL - переменная, логический, значение:=.Т.,.F.;

TEXT - строка (1:100),строковый (тип), значение:=’январь’, ‘февраль’,...

Пример описания алгоритма поиска НОД двух чисел:

Алгоритм НОД

А - переменная, целая, значение:=0

В - переменная, целая, значение:=0

NOD - переменная, целая

Начало

Ввод А,В

1:если А>B

то А:=А-В

перейти к 1

Все-если

если В>А

то В:=В-А

перейти к 1

Все-если

Если A < 0  B < 0

То стоп

Все-если

NOD:=A

стоп

Задание 3.5

Составить описание приведенного в задании 3.3 алгоритма на псевдокоде.