Основные сведения
Алгоритмом называется точное и понятное предписание исполнителю совершать последовательность действий, направленных на решение поставленной задачи.
Или:
Алгоритм – это описание способа решения задачи, в котором предусматривается разбиения процесса решения на конечную по времени последовательность действий, представленных в виде элементарных операций.
Под элементарной операцией понимается простое действие, которое уже не имеет смысла детализировать.
Алгоритм может использоваться как инструкция для работы, системы управления, автоматического регулятора или другого устройства, выполняющего определённые автоматические действия или операции. Алгоритм может использоваться также в качестве схемы решения определённой задачи.
Алгоритм является основой для составления программы, которую пишет программист на каком-либо языке программирования с тем, чтобы реализовать процесс обработки данных на компьютере.
Алгоритм разбивает весь процесс преобразования информации, связанной с решением определённой задачи, на отдельные, взаимосвязанные между собой этапы. Алгоритм должен точно определять совокупность действий, которые необходимо выполнять на каждом этапе и порядок выполнения этих действий.
Решение задач на ЭВМ представляет собой сложный процесс, состоящий из нескольких этапов (рис.1). Разработка алгоритма – это один из этих этапов
Рисунок 1 - Схема процесса решения задачи на ЭВМ
Постановка задачи – предполагает подробное описание самой задачи, описание входной и выходной информации, формулируется конечная цель, которую необходимо достигнуть при решении задачи. Постановка задачи иногда связана с построением математической модели изучаемого процесса и часто представляет собой довольно сложный этап в решении задачи.
Математическая формулировка – заключается в записи условия задачи помощью математических обозначений, формул, зависимостей, в определении исходных данных и формы выдачи результатов вычислений.
Выбор метода решения задачи на ЭВМ. После построения математической модели необходимо выбрать метод решения задачи на ЭВМ. Выбранный метод является основой построения алгоритма решения задачи.
Разработка алгоритма решения задачи заключается в установлении необходимой последовательности арифметических и логических действий, строгое выполнение которых приводит к решению задачи.
Составление программы – заключается в записи программы на языке программирования.
Отладка программы – этап, необходимый для выявления и устранения ошибок в программе.
Решение задачи на ЭВМ – производится по отлаженной программе для всего множества исходных данных.
Свойства алгоритма
Алгоритм обладает следующими основными свойствами:
- дискретностью;
- определенностью (детерминированностью, точностью);
- массовостью;
- результативностью;
- формальностью.
Дискретность – свойство алгоритма, которое характеризует его структуру. Любой алгоритм состоит из отдельных операций (этапов, действий), которые выполняются дискретно (по шагам). Это означает, что алгоритм обладает свойством дискретности.
Детерминированность – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не может допускать различных толкований. Также строго должен быть определен порядок выполнения отдельных шагов, то есть исполнитель должен точно знать последовательность выполнения операций. Любой алгоритм должен быть представлен таким образом, чтобы он мог быть однозначно (точно) реализован исполнителем. Это свойство алгоритма называют также определенностью, однозначностью или точностью.
Массовость ( универсальность ) – применимость алгоритма ко всем задачам рассматриваемого типа при любых допустимых множествах исходных данных. Здесь важно подчеркнуть, что массовость означает применимость алгоритма ко всем задачам рассматриваемого типа, то есть ко всем задачам, для решения которых он предназначен. Кроме того, здесь необходимо иметь в виду, что реализация алгоритма возможна при любых, но допустимых множествах исходных данных.
Результативность (конечность) - способность получения определенного результата для допустимых исходных данных за конечное число шагов. То есть способность завершать процесс за конечное число итераций или формировать сообщение о невозможности дальнейшей обработки данных (например, в связи с тем, что к имеющимся исходным данным этот алгоритм не применим).
Формальность – свойство означающее, что любой исполнитель, выполняющий алгоритм (например, компьютер), действует формально, то есть строго выполняет инструкции предусмотренные разработчиком алгоритма.
Способы описания алгоритмов
Существуют следующие способы описания (представления) алгоритмов:
- словесное описание;
- описание алгоритма с помощью математических формул;
- графическое описание алгоритма в виде блок-схемы;
- описание алгоритма с помощью псевдокода;
- комбинированный способ изображения алгоритма с использованием словесного, графического и др. способов.
Словесное описание алгоритма представляет собой описание структуры алгоритма на естественном языке. Например, к приборам бытовой техники, как правило, прилагается инструкция по эксплуатации, т.е. словесное описание алгоритма, в соответствии с которым данный прибор должен использоваться.
Графическое описание алгоритма в виде блок-схемы – это описание структуры алгоритма с помощью геометрических фигур с линиями связи.
Блок схема алгоритма – это графическое представление метода решения задачи, в котором используются специальные символы для отображения операций.
Символы, из которых состоит блок-схема алгоритма, определяет ГОСТ 19.701-90. Этот ГОСТ соответствует международному стандарту оформления алгоритмов, поэтому блок-схемы алгоритмов, оформленные согласно ГОСТ 19.701-90, в разных странах понимаются однозначно.
Псевдокод – описание структуры алгоритма на естественном, но частично формализованном языке. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не предусмотрено.
Рассмотрим простейший пример. Пусть необходимо описать алгоритм вывода на экран монитора наибольшего значения из двух чисел.
Рисунок 1 - Пример описания алгоритма в виде блок-схемы
Описание этого же алгоритма на псевдокоде:
- Начало
- Ввод чисел: Z, X
- Если Z > X то Вывод Z
- Иначе вывод Х
- Конец
Каждый из перечисленных способов изображения алгоритмов имеет и достоинства и недостатки. Например, словесный способ отличается многословностью и отсутствием наглядности, но дает возможность лучше описать отдельные операции. Графический способ более наглядный, но часто возникает необходимость описать некоторые операции в словесной форме. Поэтому при разработке сложных алгоритмов лучше использовать комбинированный способ.
Структуры алгоритмов
По характеру связей между символами различают алгоритмы линейной, разветвляющейся и циклической структуры.
Линейный алгоритм – это алгоритм, в котором операции выполняются последовательно.
Разветвляющийся алгоритм – это алгоритм, в котором последовательность выполнения операций зависит от определенных условий.
Если в алгоритме присутствует «действие1» и «действие2» (то есть ветвь 1 и ветвь 2), то это разветвляющийся алгоритм с полной альтернативой. Если же вместо «действия2» предусмотрен переход к выполнению операции «n», которая находится в общей (основной) ветви, то такая форма записи называется неполной альтернативой.
Циклический алгоритм – это алгоритм, в котором многократно выполняются одни и те же действия, например с целью многократного выполнения вычислений по одним и тем же зависимостям при различных значениях входящих в них переменных.
Использование циклов существенно сокращает объем алгоритма.
Можно выделить три основных типа циклических алгоритмов:
- цикл с параметром (арифметический цикл или цикл со счетчиком);
- цикл с предусловием;
- цикл с постусловием.
По способу определения числа повторений различают циклы с заранее неизвестным количеством повторений и заранее известным количеством повторений (циклы с параметром).
Цикл с параметром
В цикле с параметром определенная последовательность операций выполняется несколько раз в зависимости от заданной величины, которая называется параметром цикла. Цикл выполняется, пока параметр цикла принимает значения в заданном диапазоне с заданным шагом. Оператор цикла включает имя переменной, конечное значение и шаг.
Цикл с условием
Выделяют два типа циклов с условием: цикл с предусловием и цикл с постусловием.
В циклах с предусловием условие проверяется на входе (до операций, выполняемых в цикле). В циклах с постусловием условие проверяется после выполнения всех операций внутри цикла. В этом случае операторы тела цикла будут реализованы хотя бы один раз или до тех пор, пока не станет возможным условие выхода из цикла.
В ц иклах с постусловием сначала выполняются все операции, включенные в цикл, и только после этого проверяется заданное условие. В зависимости от результата проверки осуществляется выход из цикла или его повторение.
Цикл с условием называют также итерационным циклом.
Внутри алгоритма циклической структуры может быть помещен другой цикл – вложенный цикл, при этом вложенный (внутренний) цикл должен полностью находиться в области внешнего цикла.
Вложенные циклы
Внутри алгоритма циклической структуры может быть помещен другой цикл – вложенный (внутренний) цикл. Вложенный цикл должен полностью находиться в области внешнего цикла. Вложенный цикл может быть один, но может быть и несколько вложенных циклов. Второй вложен в первый, третий – во второй и т.д. Ниже с помощью псевдокода представлена структура циклического алгоритма, содержащего несколько вложенных циклов:
Начало цикла 1
Начало цикла 2
Начало цикла 3
Тело цикла 3
Конец цикла 3
Конец цикла 2
Конец цикла 1
Для организации и внутреннего, и внешнего циклов могут использоваться разные типы алгоритмических структур (цикл с параметром, цикл с предусловием, цикл с постусловием).
На рис. 1 представлена блок-схема алгоритма с внутренним циклом.
В данном случае и внешний и внутренний циклы организованы на базе алгоритмической структуры «цикл с параметром».
Рисунок 1 – Блок-схема алгоритма с внутренним циклом на базе алгоритмической структуры "цикл с параметром"
На каждом шаге по внешнему циклу внутренний цикл выполняется несколько раз. Количество внутренних циклов на каждом внешнем цикле зависит от параметра внутреннего цикла.
Пусть, например, задано, что параметр внешнего цикла меняется от 1 до 5 с шагом 1, а параметр внутреннего цикла – от 1 до 10 с шагом 1.
Это означает, что на каждом шаге по внешнему циклу внутренний цикл будет выполняться 10 раз. Так как внешний цикл должен выполниться 5 раз, то внутренний цикл выполнится при этом 50 раз.