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

Рисунок 5 - Блок-схема поиска максимального числа из трех заданных

Описание алгоритма решения задачи. На первом этапе работы алгоритма вводятся три числа. Так как количество чисел больше двух, а операция сравнения чисел предусматривает только два варианта, то на втором этапе работы алгоритма для анализа всех возможных вариантов используются последовательно один за другим два условных перехода. Сначала сравниваются между собой два числа: a и b. Если величина числа a больше b, то в промежуточной переменой z сохранятся число a (z=a). Если условие (a>b) нарушается, то в промежуточной переменой z сохранятся число b (z=b). Таким образом, в результате выполнения первой операции сравнения будет найдено наибольшее из двух чисел a или b. Затем выполняется еще одна операция сравнения, где производится сопоставление переменной z с величиной числа с. Если условие (c>z) выполняется, то число c больше чисел a или b, и в этом случае за наибольшее принимается число c. В противном случае за наибольшую принимается величина, записанная в переменную z.

Программа, реализующая этот алгоритм на языке Паскаль, имеет вид.

Program maximum;

Var

a, b, с, z : real;

Begin

{Ввод исходных данных}

ReadLn(a);

ReadLn (b);

ReadLn(c);

{Сравнение чисел a и b}

if a > b then

z := a

else

z := b;

{Проверка числа с}

if c>z then z := c;

WriteLn(z:8:2);

End.

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

2.2. Сложное ветвление

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

Пример алгоритма, включающего сложное ветвление. Заданы переменные х и у. Необходимо выполнить три различных действия в зависимости от условий. При х = у необходимо вывести на экран значения этих переменных без изменения. Когда х > у, величины переменных необходимо уменьшить в 3 раза. При условии х < у величины х и у увеличиваются на 12. Блок-схема алгоритма для решения поставленной задачи имеет вид, приведенный на рисунке 6.

Рисунок 6 - Блок-схема алгоритма, предусматривающего сложенное ветвление

Словесное описание алгоритма. Алгоритм начинается с ввода исходных данных - чисел x и y. На первом этапе выполняется проверка внешнего логического условия. Если оно ложно, то на экран монитора выводятся числа x и y без изменений.

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

Если же логическое условие x>y нарушается, то в этом случае значения x и y увеличиваются на постоянное число 12. После выполнения вложенного условия на экран выводятся полученные результаты.

Реализация сложного ветвления на языке Паскаль представлено следующим программным кодом.

program usvovoperat;

Var

х, у : real;

Begin

{ Ввод исходных данных}

ReadLn (х, у);

{ Проверяем внешнее условие}

if х < > у then

{Проверяем вложенное условие}

if х > у then

begin

х : = х/3;

y : = у/3;

end

else

begin

х := х+12;

у : = у+12

end;

WriteLn ('x= ', х:8:4, 'у= ', у:8:4) ;

End.

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

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

2.3. Ветвление с выбором варианта

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

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

Пример. Определить остаток от деления на 4 следующего выражения c=k*(a+b) и в зависимости от полученного результата выполнить следующие действия. Если остаток от деления равен нулю, то число с увеличить на 1, если остаток равен 1, то значение a увеличить на 4, а если остаток равен 2 или 3, то b увеличить на 2.

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

Рисунок 7 - Блок-схема алгоритма, использующая конструкцию с оператором
варианта

Алгоритм начинается с ввода переменных a, b, k. Далее вычисляется значение переменной c. На следующем шаге определяется значение селектора и в зависимости от полученного результата дальнейшая последовательность действий определяется одной из трех веток. Если остаток от деления равен нулю, то вычисляется значение с по формуле c:=c+1, и результат выводится на экран. При значении селектора равном единице выполняется другая ветвь, которая предусматривает совсем иную операцию a:=a+4, а затем вывод на экран переменной a. Для случая, когда значение селектора равно двум или трем, выполняется один и тот же оператор b:=b+2 с последующим выводом на экран переменной b. После выполнения последовательностей действий из выбранной ветки алгоритм завершает свою работу.

Реализация конструкции с выбором варианта на языке Паскаль представлена следующим кодом.

Program variantr;

Var

a, b, k, c : longint;

Begin

{Ввод исходных данных}

ReadLn(a,b,k);

{Вычисление значения переменной с}

c:=k*(a+b);

{Реализация оператора выбора варианта}

case c mod 4 of

0: begin

c:=c+1;

writeln(c:8)

end;

1: begin

a:=a+4;

writeln( a:8 )

end;

2, 3: begin

b:=b+2;

writeln( b:8)

end

end;

end.

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

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

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

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

Для реализации последовательности действий, которая повторяется многократно, применяются специальные алгоритмические конструкции - циклы [2]. Они обеспечивают управляемый итерационный процесс и различаются между собой способом его организации. Циклические конструкции бывают трех видов: цикл с параметром, цикл с постусловием и цикл с предусловием. Каждая из этих алгоритмических конструкций имеет свои отличительные особенности, влияющие на способ их применения при решении практических задач.

3.1 Цикл с параметром

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

Блок-схема, определяющая цикл с параметром в общей структуре алгоритма представлена на рисунке 8.

Рисунок 8 - Алгоритмическая конструкция, определяющая цикл с параметром

Структура оператора цикл с параметром на языке Паскаль записывается следующим образом [2]:

For <имя > := <нач. значение> to (или downto) <конечное значение> do

begin

<тело цикла, состоящее из нескольких операторов >

end;

Служебное слово For однозначно определяет цикл с параметром. Служебные слова to или downto задают прямой или обратный отсчет параметра цикла. Если тело цикла содержит только один оператор, то операторные скобки begin и end можно не применять, их присутствие для одного оператора только загромождает программу, но логику алгоритма не нарушает.

Типичный пример применения цикла с параметром - это решение задачи табулирования функции.

Пример. Вычислить значение функции y(x)=5*x+4 при изменении аргумента на заданном отрезке [1..20] c шагом 1.

Решение. Блок-схема алгоритма решения поставленной задачи приведена на рисунке 9.

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

Рисунок 9 - Блок-схема алгоритма табулирования функции y(x)=5*x+4

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

На первой итерации значение переменной цикла равно единице, которая подставляется в функцию и вычисляется значение у равное 9. Затем 9 выводится на экран, и проверятся такое условие: значение переменной цикла меньше либо равно 20. Если условие истинно, то значение переменной цикла автоматически увеличивается на шаг, равный единице, и тело цикла выполняется снова. Итерационный процесс повторяется до тех пор, пока значение переменной цикла не превысит n=20. Тогда происходит выход из цикла, и алгоритм завершает свою работу.