9. Алгоритмы численных методов и сортировки

Цель занятия – изучение алгоритмов численного расчета ряда математических функций, алгоритмов сортировки и нахождения корней уравнения, а также, реализация соответствующих программ в средеDelphi 7.

Объем занятия – 4 часа.

1. Общие сведения

Численный расчет значений функций. При использовании стандартных математических функций, «встроенных» в различные устройства и программы⁷, пользователи обычно не задумываются о происхождении «выдаваемых» значений. Вместе с тем, в этом случае используются соответствующие алгоритмы расчета, обычно основывающиеся на разложении в степенной ряд⁸, число членов которого определяется из требуемой точности вычислений. В учебном плане в этом смысле наиболее показательны алгоритмы вычисления т.н. «замечательных чисел», а именно: числа «пи» и основания натурального логарифма.

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

Рассмотрим разложение функции в степенной ряд:

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

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

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

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

Сортировка массивов данных. Под сортировкой массива подразумевается процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке.¹⁰Например, если имеется массив целых чисел а, то после выполнения сортировки по возрастанию должно выполняться условие:

а [1] < а [2] < . . .< a [SIZE]

где size – верхняя граница индекса массива.

Несмотря на обилие вариантов уже существующих алгоритмов сортировки, по-прежнему, реализуются попытки разработки все более быстродействующих вариантов. Эта ситуация обусловлена сильным трендом роста числа создаваемых информационных систем и, соответственно, баз данных, вмещающих в себя все бóльшие объемы последних.

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

2. Пример 1: Вычисление числа π с заданной точностью. Использование оператора while.

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

1 – 1/3 + 1/5 – 1/7 + 1/9 – ...

приближается к значению π/4 при достаточно большом количестве членов ряда. Каждый член ряда с номером п  вычисляется по формуле: 1 / (2 ● п – 1) и умножается на минус один, если п  четное (определить, является ли п четным, можно проверкой остатка от деления п  на 2). Вычисление заканчивается тогда, когда значение очередного члена ряда становится меньше, чем заданная точность вычисления.

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

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

while условие do begin

// здесь инструкции, которые надо выполнить несколько раз

end

где условие – выражение логического типа, определяющее условие выполнения инструкций цикла.

1. Инструкция while выполняется следующим образом:

2. Сначала вычисляется значение выражения условие.

3. Если значение выражения условие равно False (условие не выполняется), то на этом выполнение инструкции while завершается. Если значение выражения условие равно True (условие выполняется), то выполняются расположенные между begin и end инструкции тела цикла. После этого снова проверяется выполнение условия. Если условие выполняется, то инструкции цикла выполняются еще раз. И так до тех пор, пока условие не станет ложным (False).

20. Алгоритм оператора while

Для того чтобы цикл завершился, нужно, чтобы последовательность инструкций между begin и end влияла на значение выражения условие (изменяла значения переменных, входящих в выражение условие). Вид диалогового окна программы во время ее работы приведен на рис. 21. Точность вычисления вводится в поле ввода (Edit1). После щелчка на командной кнопке Вычислить (Button1) программа вычисляет значение числа π и выводит результат в поле метки (Label2).

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

Листинг программы, соответствующий инструкции while, приведен ниже. Как и в предыдущих примерах, основную работу выполняет процедура обработки событияOnClick.

unit pi_;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;

type

Editl: TEdit; // точность вычисления

Buttonl: TButton; // кнопка Вычислить

Labell: TLabel; // метка «Точность»

Label2: TLabel; // поле вывода результата

procedure ButtonlClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Forml: TForml;

implementation

{$R *.DFM}

procedure TForml.ButtonlClick(Sender: TObject);

var

pi:real; // вычисляемое значение ПИ

t:real; // точность вычисления

n:integer; // номер члена ряда

elem:real; // значение члена ряда

begin

pi := 0;

n := 1;

t := StrToFloat(editl.text);

elem := 1; // чтобы начать цикл

while elem >= t do

begin

elem := 1 / (2*n – 1);

if n MOD 2 = 0

then pi := pi – elem

else pi := pi + elem;

n := n + 1;

end;

pi: = pi * 4;

label2.caption:= 'ПИ равно '+ FloatToStr(pi) + #13

+ 'Просуммировано ¹+IntTostr(n)+' членов ряда.';

end;

end.

3. Пример 2: Сортировка массива

Существует много методов (алгоритмов) сортировки массивов. Рассмотрим два из них:

• метод прямого выбора;

• метод прямого обмена (метод «пузырька»).

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый – на место минимального.

2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй – на место минимального.

3. И так далее до предпоследнего элемента.

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

Процедура сортировки запускается нажатием кнопки Сортировка(Buttonl). Значения элементов массива вводятся из ячеек компонентаStringGrid1.После выполнения очередного цикла поиска минимального элемента в части массива процедура выводит массив в поле метки (Label2).

procedure TForml.ButtonlClick(Sender: TObject);

const

SIZE=10;

var

a: array[l..SIZE] of integer;

min: integer; { номер минимального элемента в части массива от 1 до верхней границы массива }

j: integer; { номер элемента, сравниваемого с минимальным }

buf: integer; { буфер, используемый при обмене элементов массива }

i,k: integer;

begin

// ввод массива

for i:=l to SIZE do

a[i]:= StrToInt(StringGridl.Cells[i-1,0]);

label2.caption:='';

for i:=1 to SIZE-1 do

begin

{ поиск минимального элемента в части массива от а[1] до a[SIZE]}

min:=i;

for j:=i+l to SIZE do

if a[j] < a[min] then min:= j;

{ поменяем местами a [min] и a [i] }

buf:= a[i];

a[i]:= a[min];

a[min]:= buf;

{ вывод массива }

for k:=l to SIZE do

Label2.caption:= label2.caption+' '+IntTostr(a[k]);

Labe12.caption:= label2.caption+#13;

end;

Label2.caption:= label2.caption+#13+'Массив отсортирован.';

end;

22. Результат работы программы сортировки

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

В таблице ниже цифрой 1 обозначено исходное состояние массива и перестановки на первом проходе, цифрой 2– состояние после перестановок на первом проходе и перестановки на втором проходе, и т. д.

Таблица. Процесс сортировки массива

3	)		2			2			2	)		1
2			3			3	)		1			2
4			4	)		1			3			3
5	)		1			4			4			4
1			5			5			5			5

Процедура сортировки, текст которой приведен в листинге ниже, запускается нажатием кнопки Сортировка(Button1). Значения элементов массива вводятся из ячеек компонентаStringGrid1. Во время сортировки, после выполнения очередного цикла обменов элементов массива, программа выводит массив в поле меткиLabel3.

procedure TForml.ButtonlClick(Sender: TObject);

const

SIZE=5;

var

a:array[l..SIZE] of integer; k:integer; // текущий элемент массива

i: integer; // индекс для ввода и вывода массива

changed: boolean; // TRUE, если в текущем цикле были обмены

buf: integer; // буфер для обмена элементами массива

begin

// ввод массива

for i:=l to SIZE do

a[i] := StrToInt(StringGridi.Cells[i-1, 0] ) ;

Label3.caption:='';

// сортировка массива

repeat

changed:=FALSE; // пусть в текущем цикле нет обменов

for k:=l to SIZE-1 do

if a[k] > a[k+l] then

begin

// обменяем k-й и к+1-й элементы

buf := а[k ] ;

a[k] := a[k+1] ;

а[k+1] := buf;

changed := TRUE;

end;

// вывод массива

for i:=l to SIZE do

Label3.caption:= Label3.caption+' '+IntTostr(a[i]);

Label3.caption:= Label3.caption+#13;

until not changed;

// если не было обменов, значит массив отсортирован

Label3.caption:= Label3.caption+#13+'Массив отсортирован. ';

end;

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем, возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значениеfalse. Процесс сортировки (циклrepeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (циклfor) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

Вид окна программы практически совпадает с предыдущим вариантом сортировки.

4. Пример 3: Решение уравнений численными методами

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

23. Метод половинного деления

Из этого рисунка видно, что процесс нахождения корня заканчивается, когда очередное значение его попадает в окрестностьx₀настолько близкое, что

,

где eps– априорная погрешность расчета.

Алгоритм этого метода более точно можно выразить следующим образом:

1. вычислить ;

2. если , то выполнить п. 5;

3. если , то, иначе;

4. если , то выполнить п.1;

5. вывести значение x;

6. конец.

Листинг и окно результатов работы программы дихотомии для функции приведен ниже (рис. 24).

unit dikhot_1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Math;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Button1: TButton;

Button2: TButton;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Edit3: TEdit;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

a,b,x,y,eps: real;

i: integer;

label

m1,m2;

function f(x:real): real;

begin

f:= IntPower((x -1),3);

end;

begin

eps:= StrToFloat(Edit3.text);

m1: x:= (a + b)/2;

if (f(x)=0) then goto m2;

if (f(x)*f(a)<0)

then b:= x

else

a:= x;

if (abs(a-b)>eps) then goto m1;

m2:

label4.caption:= FloatToStr(x);

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

Close;

end;

end.

24. Результаты расчета по методу дихотомии

6. Содержание работы

Запустить программную среду Delphi 7. Ознакомиться с подходами в использовании численных методов различного типа задач. Воспроизвести примеры, приведенные выше. По указанию преподавателя выбрать вариант из Приложения И. По завершении работы результаты сохранить в файл.

7. Требования к отчету

Отчет должен содержать:

• название работы, постановку задачи и сведения о последовательности её выполнения;

• скриншот работающей программы (результаты работы);

• ответы на контрольные вопросы из Приложения Б, указанные преподавателем.