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

Глава 1. Общая характеристика алгоритмов

1.1. Понятие алгоритма

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

То есть алгоритм — это четкое указание исполнителю алгоритма выполнить определенную последовательность действий для решения поставленной задачи и получения результата.

Разработать алгоритм означает разбить задачу на определенную последовательность шагов. От разработчика алгоритма требуется знание особенностей и правил составления алгоритмов.

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

1. Наличие ввода исходных данных.

2. Наличие вывода результата выполнения алгоритма, поскольку цель выполнения алгоритма – получение результата, имеющего вполне определенное отношение к исходным данных[1].

На основании последней особенности алгоритм будет обладать свойством массовости.

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

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

Конечность – исполнение алгоритма должно закончиться за конечное число шагов.

Корректность – алгоритм должен задавать правильное решение задачи.

Массовость (общность) – алгоритм разрабатывается для решения некоторого класса задач, различающихся исходными данными [3].

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

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

Происхождение слова «алгоритм» связано с именем среднеазиатского учёного аль-Хорезми, который считается одним из величайших математиков всех времен и народов.

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

Алгоритмы могут быть представлены самыми разными способами. Форма и метод записи алгоритмов зависят от следующих параметров:

1. Исполнителя, для которого разрабатывается алгоритм
2. Разработчика алгоритма
3. Задач, которые решает алгоритм.

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

Основные формы записи алгоритмов изображены на рисунке 1.

Рисунок 1 - Основные способы записи алгоритмов

Словесное описание используется обычно для описания алгоритмов, предназначенных исполнителю – человеку. Такое описание встречается в различных учебниках, справочниках[2]. К примеру, словесная запись алгоритма Эвклида нахождения наибольшего общего делителя (НОД) на естественном языке[4]. Под естественными языками понимаются языки, которые используют люди в разговорной и письменной речи. Например, русский или английский язык.

«Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y. Запишите первое из заданных чисел в столбец Х, а второе - в столбец Y. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.

Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца Х считайте искомым результатом.»[3]

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

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

Графическая форма записи алгоритмов представляется последовательностью рисунков, структурограммой и блок-схемой[2].

Последовательности рисунков позволяют людям очень быстро и легко воспринимать алгоритм. Такой способ описания подходит при обучении детей дошкольного и младшего школьного возраста[5].

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

Рисунок 2 - Структурограмма алгоритма Евклида

Наиболее популярным способом преставления алгоритмов без использования компьютеров являются блок-схемы. Существуют специальные стандарты для построения блок-схем, где определяются графические изображения блоков. Команды алгоритмов записываются внутри блоков на обычном языке или с использованием математических формул. Блоки соединяются по определенным правилам линиями связи, которые показывают порядок выполнения команд[6].

Если алгоритм разработан для решения задачи на компьютере, то для того, чтобы он мог выполниться исполнителем – ЭВМ, его необходимо записать на языке, понятном этому исполнителю. Для этого разработано множество языков программирования для решения задач разных классов [14].

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

Глава 2. Алгоритмические структуры

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

Практически любую структурную программу можно записать с помощью основных алгоритмических конструкций. Такими конструкциями являются линейные алгоритмы, циклы и ветвлениях [4].

Линейный алгоритм — набор команд (указаний), выполняемых последовательно во времени друг за другом (рисунок 3).

Рисунок 3 - Линейный алгоритм

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

Начало

Действие 1

…

Действие 2

условие

…

Конец

Истина

Ложь

Рисунок 4 - Алгоритмическая конструкция ветвление

Для автоматических вычислений очень важно иметь возможность выполнять многократные однотипные последовательности действий. Для таких случаев применяется циклы[4].

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

Существует два вида цикла: с постусловием и с предусловием. Цикл с предусловием представлен на рисунке 5.

Начало

Тело цикла

…

условие

Да

Нет

Конец

Рисунок 5 - Алгоритмическая конструкция «цикл с предусловием»

Между двумя этими схемами существует два принципиальных отличия. Как следует из названия, в цикле с предусловием сначала идет проверка условий, затем, в случае если условие выполнено, выполняется последовательность действий из тела цикла[4]. Выполнение происходит до тех пор, пока условие истинно. Когда условие становится ложным, происходит выход из цикла. Отсюда становится ясным, что в теле цикла должны выполняются операции, приводящие к изменению значений параметров, содержащихся в условии. Иначе, цикл будет выполняться бесконечно. Такой эффект называется зацикливанием[6].

Рисунок 6 - Алгоритмическая конструкция цикл с постусловием

В цикле с постусловием сначала происходит выполнение тела цикла, а затем уже проверка условий. При этом цикл выполняется, пока условие ложно. Когда условие становится истинным, происходит выход из цикла. Цикл с постусловием будет всегда выполнен хотя бы один раз. Отметим, что в разных языках программирования используется разный тип условия для ветвей, ведущих к телу цикла и к выходу из цикла [7].

Сложная программа, как правило, содержит несколько конструкций из приведенных выше, вложенных друг в друга[3].

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

для i от i1 до i2 шаг k повторять

нц

<тело цикла>

кц

Здесь i — параметр цикла, то есть переменная, изменяющая свое значение на шаг цикла при каждой итерации. При этом параметр iпроходит все значения от i1 до i2 с шагом k.То есть каждый раз к значению i,полученному при выполнении предыдущего шага прибавляется k[4].

Это равнозначно использованию цикла с предусловием, в котором в качестве условия используется i<=i2, а в конце тела цикла выполняется оператор i:=i+k. Для полного соответствия двух схем переменная iопределяется до цикла:

i:=i+1.

2.2. Реализация основных алгоритмических структур на Pascal и Python

Рассмотрим, как записываются и реализуются алгоритмические структуры на языках программирования Pascal и Python.

Это языки программирования высокого уровня, однако концепции и назначения этих языков различны.

Язык Pascal был разработан Никлаусом Виртом для обучения программированию студентов в 70-х годах XX века. Этот язык является одним из самых известных в мире языков, служит основой для ряда других, например Object Pascal.

Конструкция ветвление (полное) реализуется с помощью условного оператора[9]:

if <условие> then<оператор1>else <оператор2>;

Неполное ветвление будет соответствовать конструкции без использования ветви else помощью условного оператора:

if <условие> then<оператор1>;

В случае, если ветвь содержит более одного оператора, то команды ветви должны быть заключены в операторные скобки begin...end:

begin

<оператор 1>;¶< оператор 2>;

<...>;¶end

Цикл с предусловием (конструкция while) имеет в языке Pascal следующий вид [9]:

while < условие> do <оператор 1>;

Цикл с постусловием (конструкция repeatuntil) имеет в языке Pascalследующий вид:

repeat

<оператор 1>;¶< оператор 2>;¶until<условие>

Реализация цикла с постусловием имеет две особенности на языке Pascal [10]:

1. конструкция не требует операторных скобок begin...end;
2. цикл выполняется до тех пор пока условие ложно, выход их цикла соответствует ложному значению условия.

Цикл с параметром записывается с помощью следующей конструкци (цикл for):

for<счетчик1>:= <значение1>to<конечное_значение>do<оператор1>;