4.3. Алгоритмы

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

1. Ввести исходные данные.

2. Преобразовать исходные данные в результаты (выходные данные).

3. Вывести результаты.

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

Приведем примеры алгоритмов из обыденной жизни:

а) поездка в институт;

б) ремонт телевизора (по инструкции);

в) поиск пропавшей вещи;

г) выращивание растений на участке и т.п.

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

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

Любой алгоритм обладает следующими свойствами: детер­минированностью, массовостью, результативностью и дискретностью.

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

Массовость алгоритма предполагает возможность варьирования исходных данных в некоторых пределах. Это свойство определяет пригодность использования алгоритма для решения множества кон­кретных задач определенного класса.

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

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

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

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

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

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

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

Для облегчения процесса разработки и восприятия графического изображения алгоритмов их составление осуществляется в соответст­вии с требованиями ГОСТ 19701—90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения» и ГОСТ 19.003—80 «Схемы алгоритмов и программ. Обозначения ус­ловно- графические».

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

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

С целью повышения наглядности графические схемы алгоритмов могут сопровождаться кратким формально-словесным описанием внутри условного изображения блоков, раскрывающим содержание выполняемой операции. Для обозначения условной передачи управ­ления от блоков логических операций над соответствующими линия­ми потока могут записываться специальные знаки операций отноше­ния (<, >, = и другие) или слова «Да» либо «Нет».

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

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

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

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

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

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

В зависимости от способа организации числа повторений цикла различают: циклы с заранее заданным количеством повторений; цик­лы с заранее неизвестным числом повторений (итерационные циклы). По способу организации порядка исполнения проверки условия окончания цикла различают две разновидности циклических структур: проверкой условия окончания цикла до и после реализации цикла.

Рис. 1.7. Основные графические обозначения блоков и программ (а) и пример записи схемы алгоритма (6}