Формы представления алгоритмов
Ключевым этапом разработки программы является этап разработки алгоритма и структур данных. Результат этого этапа – формализованное описание или представление алгоритма. Под формой представления алгоритма будет понимать некоторую систему соглашений или правил, позволяющую однозначно передать логику решения задачи.
Известны следующие формы представления алгоритмов:
Ø словесное описание последовательности шагов обработки данных и условий их выполнения на естественном языке;
Ø запись алгоритма с помощью псевдокода, представляющего собой набор типовых синтаксических конструкций, составленных из ключевых слов и отдельных символов алфавита по определенным правилам;
Ø изображение структуры алгоритмов в виде блок-схем, представляющих собой последовательность графических символов, отображающих определенные действия, соединяемых линиями со стрелками, указывающими направление передачи управления от одного действия к другому.
Алгоритмы пишутся для людей, которые участвуют в процессе разработки и сопровождения программ. Описания алгоритмов являются частью документации процесса проектирования программ. Словесная форма представления алгоритмов наименее формализована, использует естественный язык, принятый в общении, и поэтому должна быть наиболее понятной. Однако, эта форма представления получается весьма громоздкой, и логика решения задачи может теряться за многословностью.
Графическое изображение алгоритмов в виде блок-схем является наглядным, однозначно отображает вычислительный процесс. При подготовке блок-схем необходимо соблюдать обозначения и выполнять стандартные правила. Этими правилами предусматривается определенная форма блок - символов для обозначения типичных действий, в соответствии с ГОСТами.
Основные компоненты блок-схем программ показаны в табл. 3.1.
Табл. 3.1.
Табл. 3.1(продолжение).
Табл. 3.1(продолжение).
Обозначение
| Назначение
| Примеры
|
Символ Соединитель
|
Разрыв линии потока управления,
Перенос части блок-схемы на другую страницу
|
|
Недостатком графического представления алгоритмов является отсутствие строгих правил задания и определения структур данных, над которыми производятся действия. Такая неопределенность в описании процесса обработки данных может быть источником ошибок при написании программы по блок-схеме.
Третьей формой представления алгоритма является псевдокод. Использование псевдокода позволяет в большей степени формализовать процесс описания алгоритма, чем словесная форма и блок-схемы. Описание алгоритма на псевдокоде наиболее приближено к языкам программирования высокого уровня, хотя не является программой, исполняемой на ЭВМ.
Псевдокод – это частично формализованный язык описания алгоритмов или проектов программ. В качестве ключевых слов в нем используются слова естественного языка. Псевдокод включает в себя средства описания структур данных и описания действий.
Рассмотрим правила описания данных. Обрабатываемые алгоритмами данные характеризуются структурой, типом и назначением. Назначение данных определяет смысловое содержание данных, свойства реальных объектов, являющихся предметом данной задачи. По своему назначению данные делятся на три категории: входные данные, выходные данные и промежуточные данные задачи (алгоритма). Тип данных определяет набор допустимых значений и форму представления данных задачи в ЭВМ. По своему типу данные делятся на арифметические (числовые), символьные и логические. Эти типы данных называются базовыми или стандартными. Структура данных определяет способ объединения данных базовых типов. В алгоритмах используются следующие структуры данных: скаляры, массивы и записи. Скаляр – это именованная структура данных, содержащая неделимую единицу данных. В алгоритмах и программах являются простые переменные и константы.
Константы – это данные, которые при выполнении алгоритма (программы) всегда определены и неизменны. Переменные - это имена данных, которые в процессе выполнения программы могут изменять свое значение. В описании алгоритма на псевдокоде скалярные данные объявляются с помощью ключевого слова СКАЛЯР.
Массив - это упорядоченный набор однотипных переменных (элементов массива), объединенных общим именем и отличающихся номерами (индексами). С другой стороны, массив – это область памяти, в которой могут размещаться совокупности данных одного и того же типа. На псевдокоде массивы объявляются с помощью ключевого слова МАССИВ.
Для обращения к элементам массива используется имя массива с индексом, определяющим место расположение элемента в массиве. Массивы в программировании аналогичны таким понятиям в математике, как векторы и матрицы.
Запись – это именованная совокупность элементов различных типов. На псевдокоде записи объявляются с помощью ключевого слова ЗАПИСЬ. Доступ к элементам записи осуществляется по составному имени, включающему имя записи и имя элемента.
Общий вид описания алгоритма на псевдокоде может быть представлен следующим образом:
Алгоритм <название>
Входные данные:
< объявления >
Выходные данные:
< объявления >
Промежуточные данные:
< объявления >
Начало
<последовательность действий>
Конец
Любой алгоритм может быть представлен в виде описания последовательности действий. Под действием будем понимать либо базовую операцию, либо базовую структуру. В качестве базовых операций используются:
- операция присваивания значения переменной:
<переменная > := <выражение>,
где <выражение> - либо другая переменная, либо константа, либо формула, значение которой должно быть вычислено и присвоено переменной, указанной слева от знака := (присвоить). Например,
A:=5;
B:= C/sin(alfa);
D:=D+1.
- операция ввода/вывода:
ввод(<список ввода>)
где <список ввода> - список переменных, значения которых должны вводиться;
вывод(<список выражений>)
где <список выражений> - список переменных, констант и формул, значения которых должны выводиться и отображаться на экране дисплея. Например,
ввод(A,B,C);
вывод(‘A= ‘,A).
Базовые структуры алгоритмов образуются из базовых операций и других базовых структур по строго определенным правилам структурирования алгоритмов. Базовые структуры бывают трех типов:
· следование;
· разветвление;
· цикл.
Следование – это структура, указывающая, что действия должны быть выполнены друг за другом:
<действие 1>
<действие 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.7).
Цикл «ПОКА» называется циклом с выходом по условию с предусловием, так условие продолжения повторяющихся действий перед выполнением очередной итерации:
ЦИКЛ ПОКА <условие>
<действие>
КОНЕЦ_ЦИКЛА
Блок-схема цикла «ПОКА» показана на рис. 3.8.
Выход из цикла происходит, когда условие не будет выполняться. Пока условие выполняется, действие, указанное в цикле, повторяется. Каждое выполнение действия в цикле называется итерацией. В цикле «ПОКА» действие может не выполниться ни разу.
Цикл «ДО» называется итерационным циклом с постусловием, так как условие выхода из цикла проверяется после выполнения действия, указанного в цикле:
ЦИКЛ
<действие>
ДО <условие>
Блок-схема цикла «ДО» показана на рис. 3.9.
До тех пор, пока условие не выполняется, указанное действие будет повторяться. Если условие выполняется, то происходит выход из цикла.
|