Практикум по программированию Обработка числовых данных

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

program Extremum;

{

Вычисление наибольшего(наименьшего) значения функции y=2x3 +10x2 +6x-20 в интервале [a,b] с заданной точностью eps и начальным шагом изменения аргумента h.

y'=6x2 +20x+6 - первая производная функции, y''=12x+20 - вторая производная

}

{$APPTYPE CONSOLE} uses

SysUtils; var

X,A,B,Aa,Bb,H,Y,Ymax,Ya,Yb,Ysr:Real;

Eps,Xmax,Dx,Xn,Xsr:Real;

I,N1,N2,K,Mon:Integer; begin

WriteLn('Введите a,b,eps,h'); ReadLn(A,B,Eps,H);

//Признак монотонности: //0 – немонотонная, //1 - монотонная. Mon:=0;

//Определение точки на заданном интервале, //в которой первая производная функции //обращается в нуль (уточнение корня //уравнения методом деления отрезка пополам). Ya:= 6*A*A+20*A+6;

if Ya=0 then Xmax:=A

else begin

Yb:=6*B*B+20*B+6; if Yb=0 then

Xmax:=B

else if Ya*Yb>0 then begin

WriteLn ('Функция на заданном интервале ' +'изменяется монотонно');

142 ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ

WriteLn ('Для нахождения наибольшего значения' ,' введите 1, для наименьшего - -1');

ReadLn(K);

Mon:=1; end

else begin

Aa:=A;

Bb:=B;

Xsr:=(Aa+Bb)/2;

Ysr:= 6*Xsr*Xsr+20*Xsr+6;

while (Abs(Bb-Aa)>Eps)and(Ysr*Ya<>0) do begin

if Ya*Ysr>0 then Aa:=Xsr else Bb:=Xsr; Xsr:=(Aa+Bb)/2;

Ysr:= 6*Xsr*Xsr+20*Xsr+6; end;

Xmax:=Xsr;

end;

end;

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

if Mon=0 then begin

if 12*Xmax+20<0 then K:=1

else

//Поиск минимума сводится к поиску //максимума функции –f(x)

K:=-1;

//Вычисление значения функции в критической точке Ymax:=K*((2*Xmax+10)*Xmax+6)*Xmax-20;

case k of

1: WriteLn('ymax=',k*ymax:10:5 ,' xmax=',xmax:10:5); -1: WriteLn('ymin=',k*ymax:10:5 ,' xmin=',xmax:10:5);

end;

ReadLn;

end;

//Поиск максимума функции с использованием //табулирования значений функции при шаге //изменения аргумента, равном требуемой точности.

N1:=Trunc((B-A)/Eps)+1;

//Установка начального значения для максимума Ymax:=((2*A+10)*A+6)*A-20;

Xmax:=A;

Dx:=Eps;

for I:=1 to N1-1 do begin

X:=A+I*Dx;

Y:= K*(((2*X+10)*X+6)*X-20); if Y>Ymax then

begin Ymax:=Y; Xmax:=X;

end;

end;

case k of 1: WriteLn('ymax=',k*ymax:10:5 ,' xmax=',xmax:10:5);

-1: WriteLn('ymin=',k*ymax:10:5 ,' xmin=',xmax:10:5);

end;

WriteLn('n1=',n1);

ReadLn;

//Вычисление наибольшего значения функции с //использованием итерационного (вложенного) цикла. N2:=0; //Количество вычислений значения функции Xn:=A;

while H>Eps do begin

//Установка начального значения //для наибольшего значения Ymax:=K*((2*Xn+10)*Xn+6)*Xn-20; Xmax:=Xn;

I:=0;

//Цикл определения наибольшего значения функции //на очередном интервале изменения аргумента repeat

I:=I+1;

//Вычисление текущего значения аргумента. X:=Xn+(I-1)*H;

//Вычисление значения функции в очередной точке. Y:=K*(((2*X+10)*X+6)*X-20);

N2:=N2+1;

if Y>Ymax then

//Определение нового наибольшего значения и //соответствующего значения аргумента.

144 ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ

begin Ymax:=Y; Xmax:=X;

end;

until (Y<Ymax)or(X>=B);

//Определение левой границы нового интервала //вычисления наибольшего значения.

Xn:= Xmax-H;

//Проверка выхода аргумента за пределы интервала if Xn<A then

Xn:=A;

//Уменьшение шага изменения аргумента в два раза H:=H/2;

end; case k of

1: WriteLn('ymax=',k*ymax:10:5 ,' xmax=',xmax:10:5); -1: WriteLn('ymin=',k*ymax:10:5 ,' xmin=',xmax:10:5);

end;

WriteLn('n1=',n1);

ReadLn;

end.

5.4. Задания для самостоятельной работы

Составить программу для вычисления экстремума функции на заданном интервале с заданной точностью.

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

âнуль. Вычислить значение функции в полученной точке. С по - мощью второй производной определить вид экстремума (макс и- мум или минимум).

2.Найти с помощью итерационного алгоритма экстремум той же функции и значение аргумента, при котором он достигает ся.

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

146 ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ

5.5. Обработка матриц

Матрицы представляют собой один из наиболее удобных математических объектов, обработка которых ведет к необходимости программирования вложенных циклов. При программной р е- ализации обработки матриц будем использовать двумерные массивы (элементы которых имеют два индекса), считая, что элем енты Хij матрицы Х, i = 1, 2, ..., m, j = 1, 2, ...…,n размещаются в ячейках соответствующего массива с такими же индексами. Это позво лит сделать текст программы удобным для понимания процесса о б- работки и уменьшить в некоторых случаях объем вычислений . Первый индекс массива будем называть номером строки, а вт о- рой — номером столбца.

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

При постановке задач в целях обеспечения применимости программ для обработки матриц, например матрицы Х, размеры которых не должны превосходить заданных значений (m ≤ 12 è n ≤ 14), будем использовать сокращенное обозначение Х(m, n), m ≤ 12, n ≤ 14. Указанные максимальные значения индексов матрицы будем использовать в объявлении типа соответствующего двумерного массива, а сами максимальные значения индексов желательно объявить в виде именованных констант. Если учест ь, что двумерный массив можно рассматривать и объявлять как одномерный массив с базовым типом массив, то объявление типа массива для хранения матриц с размерами, не превышающими 12×14, будет таким:

const

mMax=12; nMax=14; type

//Объявление типа строки двумерного массива типа tM tV=array[1..nMax] of Real;

//Объявление типа двумерного массива tM=array[1..mMax] of tV;

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

Двухэтапное объявление типа двумерного массива удобно т ем, что строка массива будет совместима по присваиванию с одн о- мерным массивом того же типа tV.

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

Переменная — двумерный массив — объявляется в разделе объявления переменных

var X:tM;

Менее предпочтительными, но допустимыми будут объявлени я типа

type

tM=array[1..mMax, 1..nMax] of Real;

èëè

type

tM=array[1..12, 1..14] of Real;

и объявление массива одной строкой

var

X:array[1.. mMax, 1..nMax] of Real;

èëè

var

X:array[1..12, 1..14] of Real;

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

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

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

Фрагмент программы, обеспечивающей ввод и вывод матрицы Х(m, n), m ≤ 12, n ≤ 14, имеет следующий вид:

WriteLn('Введите количество строк и столбцов матрицы'); ReadLn(M,N);

WriteLn('Введите элементы матрицы по строкам'); for I:=1 to M do //Цикл ввода всех строк матрицы begin

//Цикл ввода очередной строки матрицы for J:=1 to N do

Read(X[I,J]);

//Переход в начало новой строки файла ввода ReadLn;

end;

WriteLn('Введенная матрица'); //Цикл вывода всех строк матрицы for I:=1 to M do

begin

//Цикл вывода очередной строки матрицы for J:=1 to N do

Write(X[I,J]:6:1, ' ');

//Переход в начало новой строки файла вывода WriteLn;

end;

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

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

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

S:=0; Pr:=1; for I:=1 to M do

for J:=1 to N do begin

S:=S+A[I,J];

Pr:=Pr*A[I,J];

end;

WriteLn('s=',S:8:2, ' pr=',Pr:8:2);

При изменении места расположения операторов присваиван ия S:=0; Pr:=1; смысл вычислений меняется:

for I:=1 to M do begin

S:=0; Pr:=1; for J:=1 to N do begin

S:=S+A[I,J];

Pr:=Pr*A[I,J];

end;

WriteLn('s=',S:8:2, ' pr=',Pr:8:2); end;

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

При вычислении максимального и минимального элементов матрицы надо правильно устанавливать начальные значени я вы- числяемых переменных, а также правильно задавать пределы изменения параметров циклов:

Amax:=A[1,1]; Imax:=1; Jmax:=1;

Amin:=A[1,1]; Imin:=1; Jmin:=1; for I:=1 to M do

for J:=1 to N do

if A[I,J]>Amax then begin

Amax:=A[I,J];

Imax:=I;

Jmax:=J; end

else if A[I,J]<Amin then begin

Amin:=A[I,J];

Imin:=I;

Jmin:=J;

end;

WriteLn('amax=',Amax:8:2, ' imax=',Imax:2 ,' jmax=',Jmax:2, ' amin=',Amin:8:2 ,' imin=',Imin:2, ' jmin=',Jmin:2,);

В приведенном фрагменте программы нельзя опускать опера торы присваивания начальных значений индексам минимального и максимального элементов (Imax:=1; Jmax:=1; Imin:=1; Jmin:=1;). В

случае отсутствия указанных операторов индексы искомых элементов будут не определены, если первый элемент A[1,1] является максимальным (минимальным).

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

max:=A[1,1]; Imax:=1; Jmax:=1; min:=A[1,1]; Imin:=1; Jmin:=1; for I:=2 to M do

for J:=1 to N do

.....................

Рассмотрим примеры обработки матриц.

5.6. Примеры выполнения задания на обработку матриц

1. В матрице A(m, n), m ≤ 12, n ≤ 10 поменять местами строки с наибольшей и наименьшей суммами элементов.

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

После нахождения номеров строк, подлежащих обмену местами, выполняется собственно обмен. Поскольку строка матр ицы представляет собой одномерный массив (первый индекс имее т фиксированное значение), то эта операция выполняется с ис - пользованием обычного (не вложенного) цикла, а обмен места - ми — с промежуточной простой переменной b:

program Matr1; {$APPTYPE CONSOLE} uses

SysUtils; const

Mm=12; Nn=10;