Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Программная реализация основных алгоритмических структур на языке высокого уровня Паскаль).pdf

ВВЕДЕНИЕ

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

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

Для достижения цели работы поставлены задачи:

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

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

- рассмотрены основные алгоритмические структуры;

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

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

При подготовке работы в качестве источников использованы учебное пособие Г.Р. Кадыровой «Основы алгоритмизации и программирования»; учебное пособие «Программирование и основы алгоритмизации» авторов А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин; учебное пособие В. В. Фаронова «Турбо Паскаль 7. 0» и другие.

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

1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ АЛГОРИТМОВ

1.1 Понятие и принципы построения алгоритмов

Алгоритм является точным предписанием, определяющим последовательность действий для получения нужного результата из исходных данных [2; С. 6].

Данное определение алгоритма не считается строгим - не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата». Поэтому обычно формулируется несколько общих свойств алгоритмов, отличающих алгоритмы от других инструкций. Такие свойства представлены:

• дискретностью (прерывностью, раздельностью) - алгоритм должен быть процессом решения задачи в виде последовательного выполнения простых шагов. Каждое действие алгоритма выполняется только после конца исполнения предыдущего;
• определенностью - каждое правило алгоритма должно быть четко, однозначно и без произвола. Благодаря определенности выполнение алгоритма происходит механически и не нужны никакие дополнительные указания или сведения о решаемой задаче [7; С. 5];
• результативностью (конечностью) - алгоритм должен решать задачу за конечное количество шагов;
• массовостью - алгоритм решения задачи разрабатывают в общем виде с целью применения для однотипного класса задач с различными исходными данными, выбираемыми из некой области, называемой областью применимости алгоритма [12; С. 15];

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

Первое правило – при построении алгоритма, прежде всего, задается множество объектов, с которыми будет работать алгоритм. Название данных является формализованным (закодированным) представлением этих объектов. Алгоритм начинает работу с входными данными, и в результате своей работы выдает данные, называемые выходными. Таким образом, алгоритмом преобразуются входные данные в выходные. Этим правилом сразу отделяются алгоритмы от «методов» и «способов». Для построения алгоритма нужны формализованные входные данные [7; С. 5].

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

В теории алгоритмов размеры памяти не ограничены, т.е. алгоритму можно предоставить любой необходимый для работы объем памяти. Практическая работа с алгоритмами (программирование) начинается именно с этих двух правил. В языках программирования распределение памяти осуществляют декларативные операторы (операторы описания переменных). При запуске программы транслятором языка анализируются все идентификаторы в тексте программы и отводится память для соответствующих переменных [2, С. 6].

Третье правило – дискретность. Алгоритм состоит из отдельных шагов, которые являются конечными.

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

Пятое правило – сходимость (результативность). Завершение работы алгоритма должно быть после конечного числа шагов с указанием, что считается результатом работы алгоритма [12, С. 15].

Итак, алгоритм – понятие теории алгоритмов, каждому определенному набору входных данных ставящий в соответствие некоторый набор выходных данных, т.е. вычисляющий (реализующий) функцию. Рассматривая конкретные вопросы в теории алгоритмов всегда имеют в виду какую-то конкретную модель алгоритма [8; с. 4-7].

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

 Основные способы описания алгоритмов состоят из:

• словесно-формульного (на естественном языке);
• структурного или блок-схемного;
• с использованием специальных алгоритмических языков;
• посредством граф-схем (графом называют совокупность точек и линий, в которой каждой линией, называемой ребром, соединяется две точки, называемые вершинами);
• посредством сетей Петри [2; с. 6-7].

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

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

у=3b-(х+7).

Словесно-формульный способ записи алгоритма решения этой задачи может выглядеть так: 

1. Ввод значений а и х. 

2. Сложение х и 7. 

3. Умножение b на 3. 

4. Вычитание из 3b суммы (х+7). 

5. Вывод результата у [7; с. 9-10].

Блок-схемы. Наиболее удобным для программиста является блок-схемное описание алгоритма, изображаемое геометрическими фигурами (блоками), связанными линиями со стрелками. В блоках записывают последовательность действий [13].

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

Программы должны быть оформлены в соответствии с определенными требованиями. В настоящее время действует единая система программной документации (ЕСПД), устанавливающая правила разработки, оформления программ и программной документации. ЕСПД определяет и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД) [12; С. 17].

Операции обработки данных и носители информации изображены на схемах соответствующими блоками. В одной схеме рекомендуется изображение блоков одинаковых размеров с их нумерацией. Линии соединений блоков и указывающие последовательность связей между ними, проводятся параллельно линиям рамки. Стрелку в конце линии можно не ставить, если линия направляется слева направо либо сверху вниз. В блок может входить несколько линий. Из блока (кроме логического) может выходить только одна линия. Из логического блока выходят две линии и он может иметь в качестве продолжения один из двух блоков [15].

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

В качестве идентификатора, как правило, используют порядковый номер блока, к которому направляется соединительная линия. Если схема расположена на более чем одном листе, то при разрыве линии вместо окружности используют межстраничный соединитель. Внутри каждого соединителя указывают адрес — откуда и куда направляется соединительная линия. Запись адреса в две строки: в первой указывается номер листа, во второй — порядковый номер блока. Основные блоки схем алгоритмов даны в табл. 1 Приложения [13].

Блок-схема должна состоять из всех разветвлений, циклов и обращений к подпрограммам, содержащихся в программе [15].

1.3 Основные алгоритмические структуры

Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом [2; с. 8-9].

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

Линейными алгоритмами описываются линейные вычислительные процессы, выполнение этапов которого однократно и последовательно. Линейный алгоритм включает последовательное выполнение этапов:

• ввода исходных данных в память ЭВМ;
• вычисления искомых величин по формулам;
• вывода результатов из памяти ЭВМ на внешний носитель [7; C. 15].

Пример 1. Разработать алгоритм определения площади круга по формуле S = πR². Блок-схема алгоритма дана на рис. 1 [8].

Начало

Ввод R

S=π R²

Вывод S

Конец

Рисунок 1 - Линейный алгоритм [8]

Разветвляющимся алгоритмом описывается вычислительный процесс, реализуемый по одному из нескольких заранее предусмотренных направлений - ветвей. Выбор конкретной ветви вычисления зависим от результатов проверки выполнения некого логического условия. Результатом проверки является: «истина» (да) при выполнении условия, и «ложь» (нет), если не выполняется условие [7; C. 16].

Пример 2. Разработать алгоритм определения функции

F(x) = 2x при x > 0 и

F(x) = х² при x < 0.

Блок - схему разветвляющегося алгоритма представляет рис. 2 [2; C. 10].

Начало

Начало

Ввод х

Стр. 11

11

11 1

Стр. 10

x>0

F=0

F=x*x

Конец

Вывод F

Рисунок 2 - Разветвляющийся алгоритм [7; С. 16]

Циклическим алгоритмом описывается вычислительный процесс, многократно повторяющийся. Существуют простые циклы, не содержащие внутри себя другие циклы, и сложные (вложенные), содержащие несколько вложенных циклов. Существуют циклы с известным числом повторений и циклы с неизвестным числом повторений [2; С. 8].

Цикл с известным числом повторений состоит из последовательности:

• подготовки первого выполнения цикла (присвоения счетчику цикла начального значения);
• тела цикла, состоящего из блоков, выполняемых многократно;
• изменения значения счетчика циклов и сравнения его с конечным значением.

Существуют структуры повторения «повторение ДО» (повторение до выполнения условия окончания цикла) или «повторение ПОКА» (повторение пока выполняется условие продолжения цикла). В первом случае проверка условий окончания цикла осуществляется в конце цикла (рис. 3, а), во втором - в начале цикла (рис. 3, б) [12; C. 21].