 |
Типовые алгоритмы поиска максимума и минимума
|
|
|
|
В этой главе мы изучим простейшие статистические алгоритмы, главный из которых -- определение максимального и минимального значений на множестве данных.
Рассмотрим алгоритм в общем виде:
1. описать для каждого максимума и минимума по одной переменной того же типа, что анализируемые данные;
2. до цикла максимуму присваивается либо заведомо малое для анализируемых данных значение, либо первый элемент данных; минимуму присваивается либо заведомо большое для анализируемых данных значение, либо первый элемент данных;
3. в теле цикла каждый подходящий для поиска элемент данных t обрабатывается операторами вида:
if t>max then max:=t; -- для максимума;
if t<min then min:=t; -- для минимума,
где max и min -- переменные, введенные для величин максимума и минимума соответственно.
Шаг 2 этого алгоритма требует комментариев, которые мы сделаем на примере поиска максимума. Очевидно, что сам алгоритм несложен -- каждый элемент данных t последовательно сравнивается с ячейкой памяти max и, если обнаружено значение t, большее текущего значения max, оно заносится в max оператором max:=t;. Как мы помним, после описания на шаге 1 переменной max, ее значение еще не определено, и может оказаться любым, откуда следует необходимость задания начального значения. Представим, что после выбора начального значения max, равного нулю, при анализе встретились только отрицательные значения элементов t. В этом случае условие t>max не выполнится ни разу и ответом будет max, равное нулю, что неправильно. Выбор заведомо малого начального значения max (например, значение -1E30, т. е., -1030, вряд ли встретится в любых реальных данных) гарантирует, что условие t>max выполнится хотя бы раз и максимум будет найден. Альтернативный способ -- присвоить переменной max значение отдельно вычисленного первого элемента последовательности данных. В этом случае ответ либо уже найден, если первый элемент и есть максимальный, либо будет найден в цикле.
|
|
|
Аналогичные рассуждения помогают понять, почему минимуму следует присваивать в качестве начального значения заведомо большое число.
Перейдем к примерам. Для функции y(x)=sin2(x), 
найти минимальное среди положительных и максимальное значения.
Обозначив искомые значения min и max соответственно, напишем следующую программу:
var x,y,max,min:real;
begin
x:=-pi/3;
max:=-2;
min:=2; {эти начальные значения
- заведомо малое и большое для синуса}
while x<=pi/3+1e-6 do begin
y:=sqr(sin(x));
if y>0 then
{ищем min только среди положительных!}
if y<min then min:=y;
if y>max then max:=y;
x:=x+pi/24;
end;
writeln ('Минимум =',min:8:2);
writeln ('Максимум=',max:8:2);
reset (input); readln;
end.
В следующем примере дополнительно сохраним значения аргументов функции, для которых найдены минимум и максимум.
Последовательность T(k) задана соотношениями T(k)=max(sin k, cos k), k=1, 2,...,31. Найти номера максимального и минимального элементов последовательности.
Поиск номеров не избавит нас от необходимости поиска значений. Поэтому, кроме переменных min и max, нам понадобятся две целочисленные переменные для хранения номеров минимального и максимального значений, обозначим их kmin и kmax соответственно. Обратите также внимание, что на каждом шаге цикла дополнительно потребуется находить максимальное из значений sin(k) и cos(k), для занесения его в переменную t.
var t,max,min:real;
k,kmin,kmax:integer;
begin
min:=1e30;
max:=-1e30;
{задаем "надежные" значения,
близкие к плюс и минус бесконечности}
for k:=1 to 31 do begin
if sin(k)>cos(k) then t:=sin(k)
else t:=cos(k);
if t<min then begin
{по условию нужны 2 оператора –
сохранение нового мин. значения
и сохранение номера элемента,
отсюда операторные скобки!}
min:=t; kmin:=k;
end;
if t>max then begin
max:=t; kmax:=k;
end;
end;
writeln ('Номер мин. элемента =',kmin);
writeln ('Номер макс. элемента=',kmax);
reset (input); readln;
end.
|
|
|
II. Типовые задачи.
X. Алгоритмы мотивации пациента к приобретению стоматологических услуг.
Алгебраические алгоритмы реконструкции
Алгоритмы и структуры данных. Языки прграммирования
Алгоритмы имитационного моделирования для пошагового управления модельным временем.
Алгоритмы имитационного моделирования для событийного управления модельным временем.
Алгоритмы маршрутизации
Алгоритмы накопления суммы и произведения
АЛГОРИТМЫ ПРИГОТОВЛЕНИЯ ДЕЗИНФИЦИРУЮЩИХ РАСТВОРОВ
Алгоритмы решения задач выборочного метода
