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

Конец

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

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

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

Начало

Тело цикла

…

условие

Да

Нет

Конец

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

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

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

Начало

Тело цикла

…

условие

Конец

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

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

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

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

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

нц

<тело цикла>

кц

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

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

---

i:=i1

Таким образом, можно записать блок-схему цикла с параметром с помощью следующей схемы, использующей цикл с предусловием (рисунок.

Рисунок — Цикл с параметром

Рисунок 6 — Блок-схема цикла с параметром

Начало

Операторы тела цикла

i:=i1+k

…

i<=i2

Да

Нет

i:=i1

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

В начале рассмотрим реализации основных алгоритмических структур на языке программирования Pascal [8]. Язык был разработандля обучения программированию и до сих пор активно используется в этом качестве.

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

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 [9]:

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

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

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

В данном варианте происходит увеличение значения счетчика на 1 в каждой итерации. Язык имеет также реализацию с уменьшением значения параметра счетчик1 на единицу.

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

Отметим, что в реализации цикла со счетчиком на Pascal нет возможности указать шаг не равный единице [1].

Далее рассмотрим реализацию основных алгоритмических конструкций на одном из самых популярных универсальных языков программирования C++. Этот язык широко используется для написанияпрограмм самого разного назначения, в том числе мобильных и веб-приложений [15].

---

В языке С++ для цикла со счетчиком существует конструкция for, которая выглядит следующим образом [2]:

for<выражение1>; <выражение2>; <выражение3> )

{

<операторы>;

}

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

i= 0 или inti=0

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

Выражение 2 содержит условие выполнение цикла, то есть цикл будет выполняться, пока Выражение 2истинно.Например, Выражение 2 может содержать условие i<=5.Выражение 3 указывает изменение значения переменной, например i++ — увеличивает занчение переменной на единицу.

Оператор i--увеличивает занчение переменной на единицу.

Цикл с предусловием представлен конструкцией while [12]:

while (<Условие>) { <Тело цикла>; }

Цикл с постусловием реализуется с помощью конструкции do...while [14,15]

do

{ <Тело цикла>; }

while (<Условие>);

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

Примеры использования программ

Программы с использования ветвления

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

В качестве иллюстрации рассмотрим решение следующей задачи на языке C++: программа реализует вычисление квадрата большего из двух действительных чисел[16].

Листинг программы.

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_ALL, "Russian"); //Русский язык в консоли

float x,y;

cout << "Программа вычисляет квадрат большего числа\nВведите два числа" << endl;

cin>>x>>y;

if (x>=y){cout<<x*x;} else {cout<<y*y;}

return 0;

}

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

Далее, рассмотрим решение такой типичной задачи.

---

Вводится точка с координатами X,Y. Определить, принадлежит введенная точка фигуре или нет. Фигуры изображены на рисунке 7.

Рисунок 7 — Условие задачи в графическом виде

Для решения задачи будем использовать язык Pascal.

varx,y,a:real;

begin

write('Введите координаты точки через пробел');

readln(x,y);

if (y>=8-8*x) and (y>=-2.5*x+5) and (y>=x-2) and (y<=-0.25*x+8) and (sqr(x-5.5)+sqr(y-2.5)>=sqr(2.5)) then

writeln ('Точка входит в область') else

writeln('Точка не входит в область');

end.

Результат.

Вводим 2 ; 3 Выводится: Точка входит в область

Вводим 5 ;2 Выводится: Точка не входит в область'

Программы с использования циклов

В начале продемонстрируем решение простой задачи с помощью цикла на языке С++. Пускай программа реализует вычисление первых n четных чисел.

Листинг программы:

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_ALL, "Russian"); //Русский язык в консоли

cout<<"Введите n"<<endl;

int n;

cin>>n;

int s=0;

for (int i=0; i<n;i++)

{int k=2*i; s=s+k;}

cout<<s;

return 0;

}

Результат работы программы:

Если вводим 3, программа выдает 6 (то есть 0+2+4).

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

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

на отрезке [1;3]

Один из самых известных методов решения данной задачи называется методом Ньютона.

Метод Ньютона (метод касательных) состоит в том, что приближенным значением корня считается точка пересечения касательной к кривой f (x) и оси 0X.

Рабочая формула метода

позволяет найти последовательность x₀, x₁, x₂, …, x_n, сходящуюся к точному значению корня ξ уравнения (1.1). Критерием окончания вычислительного процесса является выполнение условия:

|x _n+1 - x _n| < ε (2)

Была разработана программа на языке Pascal в среде разработки PascalABC.Net.

Листингпрограммы:

usescrt;

varx,a,b,e: real;

function f1(z: real): real; {Основнаяфункция}

---

begin

f1:= 3*sqr(ln(z))+6*ln(z)-5;

end;

function f2(z:real): real; {Производная от основной функции}

begin

f2:=6*(ln(z))/z+6/z;

end;

begin

Clrscr;

a:=1;b:=3;

e:=0.00001;

clrscr;

if f1(a)*f2(a)>0 then x:=a

else x:=b;

while abs(f1(x)/f2(x))>e do

begin

x:=x-f1(x)/f2(x);

end;

Writeln (' В интервале от ',a:0:0,' до ',b:0:0,' с погрешностью ',e:0:5);

Writeln ('x=',x:0:5,' f(x)=',f1(x):0:5);

end.

Программа выдает результаты, представленные на рисунке 8.

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

Рисунок — Результаты решения уравнения методом Ньютона

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

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

Метод заключается в разбиении рассматриваемого промежутка на прямоугольники и выборе середины стороны прямоугольника для расчета площади под графиком (геометрический смысл интеграла)[17,18].

Листингпрограммы:

uses crt;

varx,a,b,h, s: double; i,pow:integer;

function f(z: real): double; {Основная функция}

begin

f:=exp(z)*sqr(cos(z));

end;

begin

Clrscr;

a:=0; b:=Pi;

h:=(b-a)/60;

for i:=0 to 59 do begin {метод прямоугольников}

x:=a+i*h;

s:=s+h*(f(x+h/2)) end;

writeln('Метод центральных прямоугольников. Значение интеграла exp(x)*sqr(cos(x))dx от 0 до pi равно ',s:0:5);

end.

Результаты работы программы представлен на рисунке 9:

Рисунок — Результат работы программы

Продемонстрируем вычисление данного интеграла с точностью 10^-5 итеративным методом (увеличением количества отрезков разбиения на каждом шаге в два раза до достижения необходимой точности). При вычислении интеграла используется метод Симпсона. Этот пример наглядно демонстрирует применение цикла с постусловием [19].

const

a=0;b=Pi; e=0.00001;

functionF(z:real):real;

begin

f:=exp(z)*sqr(cos(z));

end;

varn,i:integer;

h,k,s1,s2: real;

begin

n:=2;

---