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

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

....

Иначе

< список операторов 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 алгоритма на псевдокоде.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. В чем заключается постановка экономических задач и какие этапы она содержит.

2. Что понимается под алгоритмом решения задачи?

3. Какие свойства алгоритма вы знаете?

4. В каких формах могут быть представлены алгоритмы? Каковы их достоинства и недостатки?

5. Из каких частей состоит решающая таблица?

6. Какие правила существуют при составлении блок схем?

7. Сколько типов алгоритмов вы знаете?

8. Какие алгоритмы называются разветвляющимися?

9. Какие алгоритмы называются циклическими? Какие существуют циклические алгоритмы?

10. В чем заключается структурный подход при разработке алгоритмов?

11. Какие базовые структуры вы знаете?

12. Что представляет собой запись алгоритма на псевдокоде?