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

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

Известны следующие формы представления алгоритмов:

Ø словесное описание последовательности шагов обработки данных и условий их выполнения на естественном языке;

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

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

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

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

Основные компоненты блок-схем программ показаны в табл. 3.1.

Табл. 3.1.

Обозначение	Назначение	Примеры
Символ Процесс	Блок вычислений и обработки данных	I=J+2
Символ Решение	Блок проверки условия
Символ Модификация	Блок организации и начала цикла

Табл. 3.1(продолжение).

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

Табл. 3.1(продолжение).

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

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

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

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

Рассмотрим правила описания данных. Обрабатываемые алгоритмами данные характеризуются структурой, типом и назначением. Назначение данных определяет смысловое содержание данных, свойства реальных объектов, являющихся предметом данной задачи. По своему назначению данные делятся на три категории: входные данные, выходные данные и промежуточные данные задачи (алгоритма). Тип данных определяет набор допустимых значений и форму представления данных задачи в ЭВМ. По своему типу данные делятся на арифметические (числовые), символьные и логические. Эти типы данных называются базовыми или стандартными. Структура данных определяет способ объединения данных базовых типов. В алгоритмах используются следующие структуры данных: скаляры, массивы и записи. Скаляр – это именованная структура данных, содержащая неделимую единицу данных. В алгоритмах и программах являются простые переменные и константы.

Константы – это данные, которые при выполнении алгоритма (программы) всегда определены и неизменны. Переменные - это имена данных, которые в процессе выполнения программы могут изменять свое значение. В описании алгоритма на псевдокоде скалярные данные объявляются с помощью ключевого слова СКАЛЯР.

Массив - это упорядоченный набор однотипных переменных (элементов массива), объединенных общим именем и отличающихся номерами (индексами). С другой стороны, массив – это область памяти, в которой могут размещаться совокупности данных одного и того же типа. На псевдокоде массивы объявляются с помощью ключевого слова МАССИВ.

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

Запись – это именованная совокупность элементов различных типов. На псевдокоде записи объявляются с помощью ключевого слова ЗАПИСЬ. Доступ к элементам записи осуществляется по составному имени, включающему имя записи и имя элемента.

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

Алгоритм <название>

Входные данные:

< объявления >

Выходные данные:

< объявления >

Промежуточные данные:

< объявления >

Начало

<последовательность действий>

Конец

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

- операция присваивания значения переменной:

<переменная > := <выражение>,

где <выражение> - либо другая переменная, либо константа, либо формула, значение которой должно быть вычислено и присвоено переменной, указанной слева от знака := (присвоить). Например,

A:=5;

B:= C/sin(alfa);

D:=D+1.

- операция ввода/вывода:

ввод(<список ввода>)

где <список ввода> - список переменных, значения которых должны вводиться;

вывод(<список выражений>)

где <список выражений> - список переменных, констант и формул, значения которых должны выводиться и отображаться на экране дисплея. Например,

ввод(A,B,C);

вывод(‘A= ‘,A).

Базовые структуры алгоритмов образуются из базовых операций и других базовых структур по строго определенным правилам структурирования алгоритмов. Базовые структуры бывают трех типов:

· следование;

· разветвление;

· цикл.

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

<действие 1>

<действие 2>

Блок-схема структуры «Следование» показана на рис. 3.2.

		Рис 3.2

Структура «Разветвление» обеспечивает выбор одного из двух альтернативных действий, в зависимости от того, выполняется или не выполняется некоторое условие, и на псевдокоде записывается следующим образом:

ЕСЛИ <условие> ТО

<действие 1>

ИНАЧЕ

<действие 2>

КОНЕЦ_ЕСЛИ

Блок-схема структуры «Разветвление» показана на рис. 3.3.

На рис. 3.3 показано, что действие 1 выполняется, если выполняется условие, действие 2 выполняется, если условие не выполняется. После выполнения одного из двух действий, осуществляется переход на алгоритмическую операцию и структуру, следующую за структурой «Разветвление».

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

ЕСЛИ <условие> ТО

<действие >

КОНЕЦ_ЕСЛИ

Блок-схема сокращенной структуры «Разветвление» показана на рис. 3.4.

Обобщением структуры «Разветвление» является структура «Множественный выбор» :

ВЫБОР ПО <Var>

ЕСЛИ Var=Const1 ТО <действие 1 >

ЕСЛИ Var=Const2 ТО <действие 2 >

…………

ЕСЛИ Var=Constn ТО <действие n >

ИНАЧЕ <действие >

КОНЕЦ_ВЫБОР

В зависимости от значения переменной Var выполняется одно из указанных действий. Блок-схема структуры «Выбор» показана на рис. 3.5.

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

Различаются следующие типы структуры «Цикл»:

v цикл «ОТ ДО»;

v цикл «ПОКА» с предусловием и с постусловием;

v цикл «ДО».

Цикл «ОТ ДО» называется циклом с заданным числом повторений. Этот цикл управляет повторением выполнения действия с помощью переменной цикла:

ЦИКЛ ОТ I= N1 ДО N2 ШАГ <N3>

<действие>

КОНЕЦ_ЦИКЛА

где I – параметр цикла;

N1 – начальное значение параметра цикла;

N2 – конечное значение параметра цикла;

N3 – шаг изменения значения параметра цикла.

Значения N1, N2, N3 вычисляются один раз при входе в цикл. Переменная I принимает значения от N1 до N2, N3 = 1 (по умолчанию). Когда значение I становится больше N2, происходит выход из цикла. Блок-схема цикла «ОТ-ДО» показана на рис. 3.6.

		Рис. 3.6

Блок-схема, показанная на рис. 3.6, может быть представлена с помощью графического символа «Модификация» (см. рис. 3.7).

Цикл «ПОКА» называется циклом с выходом по условию с предусловием, так условие продолжения повторяющихся действий перед выполнением очередной итерации:

ЦИКЛ ПОКА <условие>

<действие>

КОНЕЦ_ЦИКЛА

Блок-схема цикла «ПОКА» показана на рис. 3.8.

		Рис. 3.8

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

Цикл «ДО» называется итерационным циклом с постусловием, так как условие выхода из цикла проверяется после выполнения действия, указанного в цикле:

ЦИКЛ

<действие>

ДО <условие>

Блок-схема цикла «ДО» показана на рис. 3.9.

До тех пор, пока условие не выполняется, указанное действие будет повторяться. Если условие выполняется, то происходит выход из цикла.