Файл: Основные структуры алгоритмов.pdf

На языке блок-схем каждый шаг алгоритма описывается с помощью соответствующей фигуры, а последовательность выполнения шагов определяется линиями-связями. Блок схемы необходимо читать сверху вниз и слева направо [9, C.27].

Блок-схемы полезны и удобны тем, что обеспечивают легкую «читаемость» алгоритма. Однако это применимо не ко всем ситуациям: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она начнет разрастаться до невероятных размеров и потеряет все свое наглядное преимущество. Поэтому блок-схемы полезны в структурном программировании для описания коротких алгоритмов [13, C.11].

Язык блок-схем прост (хотя существуют его более расширенные варианты):

– Прямоугольник – выполнение действия (для примера, c = a + b)

– Ромб – проверка условия (для примера, a > b). Если условие выполняется, то алгоритм идет по линии «да», если не выполняется – то по линии «нет».

– Скругленный прямоугольник – начало и конец алгоритма

– Скошенный прямоугольник – ввод-вывод данных (например, получение значения переменной, вывод результата на экран монитора компьютера). Это не полное описание языка блок-схем [12, C.23].

Основные элементы блок-схем представлены в Приложении 1.

Символы, из которых состоит блок-схема алгоритма, определяются по ГОСТ 19.701-90. Этот ГОСТ соответствует международному стандарту оформления алгоритмов, поэтому блок-схемы алгоритмов, оформленные согласно ГОСТ 19.701-90, в разных странах понимаются однозначно и не имеют двойного толкования [13, C.15].

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

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

В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя [7, C.22].

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

Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций [7, C.23].

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

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

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

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

Разветвляющийся алгоритм – это алгоритм, в котором последовательность выполнения операций зависит от определенных условий [14].

Если в алгоритме присутствует «действие1» и «действие2» (то есть ветвь 1 и ветвь 2), то это разветвляющийся алгоритм с полной альтернативой. Если же вместо «действия2» предусмотрен переход к выполнению операции «n», которая находится в общей (основной) ветви, то такая форма записи называется неполной альтернативой.

Циклический алгоритм – это алгоритм, в котором многократно выполняются одни и те же действия, например с целью многократного выполнения вычислений по одним и тем же зависимостям при различных значениях входящих в них переменных [14].

Использование циклов существенно сокращает объем алгоритма.
Можно выделить три основных типа циклических алгоритмов:

– цикл с параметром (арифметический цикл или цикл со счетчиком);

– цикл с предусловием;

– цикл с постусловием.

1.3.1 Линейный алгоритм

Линейный алгоритм (следование) – состоит из последовательности операций, выполняющихся только один раз в порядке их следования и считается самым простым в информатике. Подразумевая под собой конкретную последовательность выполнения действий, он не позволяет создавать разветвленную систему параметров и отлично служит в тех случаях, где необходимо конкретно и четко описать представленную задачу [12, C.24].

Графически линейный алгоритм представлен на рис.1.4.

Начало

Объявление переменной

Ввод данных

Действия

Вывод данных

Конец

Рис. 1.4 Линейный алгоритм [14]

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

1.3.2 Разветвляющийся алгоритм

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

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

Графически разветвляющийся алгоритм представлен в Приложении 2.

1.3.3 Циклический алгоритм

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

В цикле с параметром определённая последовательность операций выполняется несколько раз в зависимости от заданной величины, которая называется параметром цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг.

Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием. В циклах с предусловием условие проверяется на входе (до операций, выполняемых в цикле). В циклах с постусловием условие проверяется после выполнения всех операций внутри цикла. В этом случае операторы тела цикла будут реализованы хотя бы один раз или до тех пор, пока не станет возможным условие выхода из цикла [9, C.83].

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

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

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

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

В цикле с параметром определенная последовательность операций выполняется несколько раз в зависимости от заданной величины, которая называется параметром цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг [9, C.83].

Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием.

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

В циклах с постусловием сначала выполняются все операции, включенные в цикл, и только после этого проверяется заданное условие. В зависимости от результата проверки осуществляется выход из цикла или его повторение [8, C.32].

Цикл с условием называют также итерационным циклом.

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

Глава 2. Сравнительный анализ структур алгоритмов

2.1 Анализ сложности и эффективности алгоритмов

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

Одной из них является необходимость выяснения оценок или границ для занимаемого объема памяти и затраченного времени работы, потребных алгоритму для эффективной обработки входящих данных [9, C.143].

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

Необходимо заранее (еще в начальной стадии разработки алгоритма) на бумаге и с помощью карандаша верно оценить объем памяти и время, нужные алгоритму, находящемуся в разработке, а затем модернизировать его (или написать новый, более эффективный в использовании) [12, C.49].

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

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

1) быть легким для понимания, перевода в программный код и отладки программы;

2) результативно и эффективно использовать доступные вычислительные ресурсы и выполняться по возможности быстро [11].

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