Лекция: 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
+ 'Просуммировано 1+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:='';
fori:=1 toSIZE-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 – состояние после перестановок на первом проходе и перестановки на втором проходе, и т. д.
Таблица. Процесс сортировки массива
| ) | ) | ||||||
| ) | |||||||
| ) | |||||||
| ) | |||||||
Процедура сортировки, текст которой приведен в листинге ниже, запускается нажатием кнопки Сортировка (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. Метод половинного деления
Из этого рисунка видно, что процесс нахождения корня заканчивается, когда очередное значение его попадает в окрестность x0настолько близкое, что
,
где eps – априорная погрешность расчета.
Алгоритм этого метода более точно можно выразить следующим образом:
1) вычислить ;
2) если, то выполнить п. 5;
3) если, то, иначе ;
4) если, то выполнить п.1;
5) вывести значение x;
6) конец.
Листинг и окно результатов работы программы дихотомии для функции приведен ниже (рис. 24).
unit dikhot_1;