Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (СПОСОБЫ ОПИСАНИЕ АЛГОРИТМОВ).pdf

ВВЕДЕНИЕ

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

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

Теория алгоритмов оказала влияние на теоретическое программирование. В частности, большую роль в теоретическом программировании играют модели вычислительных автоматов, которые, по существу, являются ограничениями тех представительных вычислительных моделей, которые были созданы ранее в теории алгоритмов. Трактовка программ, как объектов вычисления, операторы, используемые для составления структурированных программ (последовательное выполнение, разветвление, повторение) пришли в программирование из теории алгоритмов. Обратное влияние выразилось, например, в том, что возникла потребность в создании и развитии теории вычислительной сложности алгоритмов. Таким образом, можно сказать, что теория алгоритмов применяется не только в информатике, но и в других областях знаний.

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

ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий.

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

Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

---

Основными свойствами алгоритма являются:

Детерминированность (определенность).

Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

Результативность

Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;

Массовость

Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

Дискретность

Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

Понятность

Свойство алгоритма, при котором каждое из этих элементарных действий (шагов) являются законченными и понятными.

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

Алгоритм может быть записан различными способами: на естественном языке в виде описания; в виде графических блок-схем; на специальном алгоритмическом языке. В школе на уроках информатики для записи алгоритмов используется, так называемый, "школьный алгоритмический язык". Этот язык по существу является “мёртвым" языком” так как на нём не работают компьютеры, и мы не будем им пользоваться. Запись алгоритмов на родном языке доступна и удобна. Примеров таких записей множество, хотя бы книга кулинарных рецептов есть не что иное, как сборник алгоритмов, написанных на родном языке. Существенным недостатком такой записи является недостаточная наглядность, что особенно сказывается, когда алгоритм имеет много ветвлений. Поэтому, мы будем записывать наши алгоритмы в виде блок-схемы.

СПОСОБЫ ОПИСАНИЕ АЛГОРИТМОВ

Существуют различные способы описания алгоритмов. Приведем основные из них: словесный (пошаговое описание); табличный и в виде формул; графический (в виде схем); с использованием псевдокода (алгоритмического языка).

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

---

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

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

ЭЛЕМЕНТЫ БЛОК-СХЕМ АЛГОРИТМОВ

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

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

Таблица 1 – Основные обозначения для блок-схемы

Терминатор начала и конца работы функции	Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора.
Операции ввода и вывода данных	Определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.
Выполнение операций над данными	В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций.
Блок, иллюстрирующий ветвление алгоритма	Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения — «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах — значения этой переменной.
Вызов внешней процедуры	Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями.
Начало и конец цикла	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня — оператор с предусловием (while) или постусловием (do … while).
Подготовка данных	Символ «подготовка данных» в произвольной форме, задает входные значения. Используется обычно для задания циклов со счетчиком.
Соединитель	В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно.
Комментарий	Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией.

---

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

ЛИНЕЙНАЯ АЛГОРИТМИЧЕСКАЯ СТРУКТУРА

Линейные алгоритмы предполагают последовательное выполнение действий в порядке, заданном схемой, без их повторения или пропуска некоторых действий. Алгоритм линейной структуры изображается линейной последовательностью связанных друг с другом блоков (рис.2.1). Такой порядок выполнения действий называется естественным. Поэтому в схемах алгоритмов линейной структуры нет блока «Решение».

Рисунок 2.1 – Алгоритм линейной структуры

РАЗВЕТВЛЯЮЩАЯСЯ АЛГОРЕТМИЧЕСКАЯ СТРУКТУРА

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

Таким образом, алгоритм ветвящейся структуры содержит только структуры «Следование» и «Ветвление».

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

Для реализации процесса выбора одного из двух вариантов решения используется логический блок (блок проверки условия), приведенный на рисунке 3.1. При входе в этот блок выполняется проверка логического условия (обычно математического неравенства). Если результат проверки условия «Истина», т.е. условие выполняется, то происходит переход к выполнению блоков, стоящих по ветви «+». В противном случае, т.е. когда проверяемое условие не выполняется, происходит переход к выполнению блоков, стоящих по ветви «–».

Рисунок 3.1 – Логический блок

Визуальное представление алгоритма в виде блок-схемы представлено на рисунке 2.2.

---

Рисунок 2.2 – Алгоритм разветвляющейся структуры

АЛГОРЕТМИЧЕСКАЯ СТРУКТУРА «ЦИКЛ»

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

1-й этап – подготовка к выполнению цикла. На этом этапе задаются начальные значения для параметра цикла и переменных, использующихся для хранения накапливающихся величин (сумма, количество или произведение вычисляемых величин). Параметр цикла – это переменная, на основе которой строится цикл. Она должна удовлетворять трем условиям: являться исходной величиной для выполнения вычислений; изменяться по определенному закону (чаще всего это закон арифметической прогрессии); оказывать влияние на условие завершения повторяющихся вычислений.

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

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

Пример.

Вычислить значение функции y(x) = x²+ 1,5 при изменении аргумента x в диапазоне x_n ≤ x ≤ x_k с шагом Dx. Вывести таблицу значений x и y.

Блок-схема, описывающая этапы организации цикла изображена на рисунке 4.1. Такая организация циклического вычислительного процесса называется циклом с постусловием. В этом случае, после каждого выполнения тела цикла, проверяется условие выхода из этого цикла. Если оно не выполняется, то происходит возврат в начало тела цикла и повторение вычислений. Когда условие выхода будет выполнено, произойдет завершение работы и выход из цикла. Наличие линии возврата в блок-схеме является основным признаком циклического вычислительного процесса.

Рисунок 4.1 – Алгоритм цикла с постусловием

Представим данную схему циклического алгоритма с помощью цикла типа «ДЛЯ», или цикла с параметром, который является модификацией цикла «ПОКА» для ситуации, когда заранее известно количество повторений некоторых действий. В этом случае все три необходимых блока – блок 4, блок 5 и блок 8 – собираются в один блок – блок 4, в котором указываются начальное и конечное значения параметра и шаг изменения.

---