Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: СРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ (АЛГОРИТМЫ).pdf

Алгоритмы могут быть представлены в виде структур отдельных элементов. В зависимости от особенностей построения алгоритмы делятся на следующие группы (см. рисунок 12):

Рисунок 12 – Виды алгоритмов

• линейные (последовательные);
• разветвляющиеся;
• циклические;
• рекурсивные.

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

• точность решения задачи;
• временные затраты;
• число этапов;
• простота этапов и т. д [3].

Рассмотрим последовательно все виды алгоритмов.

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

Элементарным действием любого вычислительного алгоритма является операция присваивания.

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

• при помощи операции присваивания;
• при помощи операции ввода.

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

• числитель первой дроби умножить на знаменатель второй дроби;
• знаменатель первой дроби умножить на числитель второй дроби;
• результатом деления является дробь, числитель которой был получен на шаге 1, а знаменатель – на шаге 2.

Алгебраическая форма записи данного алгоритма приведена на рисунке 13.

Рисунок 13 – Алгебраическая форма записи алгоритма деления дробей

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

Блок-схема описанного алгоритма приведена на рисунке 14.

В данном алгоритме команда присваивания («:=») реализует следующие действия:

• вычисление выражения;
• запись получившегося значения в переменную [18].

Рисунок 14 – Блок-схема алгоритма деления дробей

2.2. Разветвляющиеся алгоритмы

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

Существует два варианта оператора ветвления – полный и укороченный (см. рисунок 15), где:

• S – логическое выражение;
• A – набор операторов, которые выполняются в том случае, если значение S – истина;
• B – набор операторов, которые выполняются в том случае, если значение S – ложь.

Рисунок 15 – Блок-схема разветвляющегося алгоритма

а) – полный; б) – укороченный

Полное ветвление предполагает наличие каких-либо действий по каждой из ветвей алгоритма. Укороченное ветвление реализует действия только по одной ветви [15].

Частным случаем ветвления является оператор с несколькими ветвями (больше, чем 2). В этом случае на блок-схеме отражаются все возможные варианты.

2.3. Циклические алгоритмы

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

Классификация циклических алгоритмов приведена на рисунке 16.

Циклы с известным числом повторений применяются в тех случаях, когда можно вычислить или заранее известно количество повторов операторов в теле цикла. Другое название данных циклов – циклы со счетчиком (параметром) или циклы с заданным шагом. Подобные циклы могут быть реализованы при помощи блока «решение» (см. рисунок 17), где:

• i – параметр цикла;
• i_n – начальное значение параметра цикла;
• i_k – конечное значение параметра цикла;
• h_i – шаг изменения параметра цикла.

Рисунок 16 – Классификация циклических алгоритмов

Рисунок 17 – Организация цикла с известным числом повторений при помощи блока «Решение»

Кроме того, для реализации цикла с заранее известным числом повторений может быть использован специальный блок «модификация» (см. рисунок 18).

Рисунок 18 - Организация цикла с известным числом повторений при помощи блока «Модификация»

Данный блок в разные моменты времени способен выполнять три функции. В случае первого исполнения (при входе в данный блок) выполняется операция i := i_n. При возврате в блок (вход слева) – i := i+1. Кроме того, данный блок содержит два выхода. В том случае, когда i ≤ i_k, процесс попадает в тело цикла, иначе – выходит из него.

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

• цикл с предусловием (см. рисунок 19);

Рисунок 19 – Блок-схема цикла с предусловием

• цикл с постусловием (см. рисунок 20).

Рисунок 20 – Блок-схема цикла с постусловием

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

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

2.4. Рекурсивные алгоритмы

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

Любая рекурсивная функция может быть описана при помощи циклической конструкции, и наоборот. Однозначного ответа на вопрос какое из этих описаний лучше нет, так как рекурсивное описание в большинстве случаев сокращает объем кода, однако усложняет его читаемость. Кроме того, рекурсивные функции обычно вычисляются дольше циклических, поэтому при выборе алгоритма важно заранее определить, что важнее в данной задаче – объем кода или скорость его выполнения [13].

2.5. Краткие выводы

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

3. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ РАЗЛИЧНЫХ СТРУКТУР АЛГОРИТМОВ

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

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

В качестве примера использования линейных алгоритмов напишем решение задачи «Рубли и копейки»: дана исходная денежная сумма в копейках. Требуется перевести данную сумму в рубли и копейки [16]. Исходный код данной задачи на языке Паскаль:

uses crt;

var

sum,rub,kop:integer;

begin

write('Исходная сумма: ');

readln(sum);

rub:=sum div 100;

kop:=sum mod 100;

writeln(sum,' коп. = ',rub,' руб. ',kop,' коп.');

readln;

end.

Результат выполнения данного кода приведен на рисунке 21.

Рисунок 21 – Пример реализации линейного алгоритма

При решении данной задачи все действия выполняются последовательно друг за другом. Следовательно, алгоритм решения – линейный.

3.2. Разветвляющиеся алгоритмы

Для примера программы, реализующей алгоритм ветвления, составим программу, которая ищет корни квадратного уравнения [8]:

uses crt;

var

a, b, c, d, x1, x2: real;

begin

write('Коэффициент при х^2 = ');

readln(a);

write('Коэффициент при х = ');

readln(b);

write('Свободный коэффициент = ');

readln(c);

d:=b*b*-4*a*c;

if d<0 then writeln('Корней нет!')

else if d = 0 then writeln('x1 = x2 = ',-b/(2*a))

else

begin

x1:=(-b+sqrt(d))/(2*a);

x2:=(-b-sqrt(d))/(2*a);

writeln('x1 = ',x1:3:1,'; x2 = ',x2:3:1);

end;

readln;

end.

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

Рисунок 22 – Пример реализации разветвляющегося алгоритма

3.3. Циклические алгоритмы

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

Код программы, реализующей цикл с предусловием:

uses crt;

var

i,BeginTIme:integer;

a,s,e:real;

begin

write('e = ');

readln(e);

BeginTime := Milliseconds;

s:=0; a:=1; i:=1;

while abs(a)>e do

begin

s:=s+a;

i:=i+1;

a:=1/(i*i);

end;

writeln('s = ',s:1:5);

writeln('Время выполнения = ',Milliseconds - BeginTime);

readln();

end.

Результат выполнения данной программы приведен на рисунке 23.

Рисунок 23 – Пример реализации циклического алгоритма с предусловием

Запишем решение этой же задачи при помощи цикла с постусловием:

uses crt;

var

i,BeginTIme:integer;

a,s,e:real;

begin

write('e = ');

readln(e);

BeginTime := Milliseconds;

s:=0; a:=1; i:=1;

repeat

s:=s+a;

i:=i+1;

a:=1/(i*i);

until abs(a)<e;

writeln('s = ',s:1:5);

writeln('Время выполнения = ',Milliseconds - BeginTime);

readln();

end.

Результат выполнения данной программы приведен на рисунке 24.

Рисунок 24 – Пример реализации циклического алгоритма с постусловием

Как видно из результатов, цикл с предусловием отработал быстрее, чем цикл с постусловием.

Для примера реализации цикла с параметром составим программу, которая будет выводить на экран таблицу температур по Цельсию от -270° С до 200°С с шагом 10°С и соответствующие им температуры по Кельвину [11].

Исходный код данной программы:

uses crt;

var

i,C,K:integer;

begin

writeln(' C K');

for i:=-27 to 20 do

begin

C:=i*10;

K:=C+273;

writeln(C:4,K:4);

end;

readln();

end.

Результат выполнения данной программы приведен на рисунке 25.

Рисунок 25 – Пример реализации циклического алгоритма с параметром

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

uses crt;

var