Pers.narod.ru. Обучение. Учебник по Паскалю. Глава 12

12. Типовые алгоритмы поиска максимума и минимума

 

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

Рассмотрим алгоритм в общем виде:

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.

Рейтинг@Mail.ru
вверх гостевая; E-mail
Hosted by uCoz