Re^2: Ускорение поиска максимума...

From

Andrew Starsh (2:5071/59)

To

Anton Kuznetsov

Date

2002-12-21T15:49:18Z

Area

RU.ALGORITHMS

                     Приветствую Вас, Anton!

20 декабря 2002 года в 22:36 Yurij Zabelyshynskij --> Anton Kuznetsov

 >>  Очевидный вариант: 2*N сравнений.
 >>  Я могу           : 1,5*N - 2
 >>  Может кто быстрее могет? Или за 1,5*N - (что-то
 >> большее 2).
 YZ> Меньше нельзя (только при нечетном N должно быть 1.5N - 1.5).

Увы, Вы забыли, что может быть нечетное число, Ваш коppеспондент забыл
посчитать еще одно сpавнение. Так что пpи четном 1.5*N-1; пpи нечетном 1.5*N-0.5
Вот:

=== Text:=New(pBufStream,Init('min_max.pas',stOpenRead,1024)); ===
program min_max;
(*Программа ищет минимум и максимум массива*)
uses crt;
var
  N,c,min,max:byte;
  m:array[1..255] of byte;
  s:word;
BEGIN
  n:=1;
  while n>0 do
  begin
    writeln('Введите N, выход - 0');
    readln(n);
(*    for c:=1 to n do m[c]:=c;*)
    for c:=1 to n do m[n-c+1]:=c;
    s:=1;
    if m[1]>m[n] then
    begin
      min:=m[n];
      max:=m[1];
    end
    else
    begin
      min:=m[1];
      max:=m[n];
    end;
    for c:=2 to (n div 2) do
    begin
      s:=s+3;
      if m[c]>m[n-c] then
      begin
        if m[c]>max then max:=m[c];
        if m[n-c]<min then min:=m[n-c];
      end
      else
      begin
        if m[n-c]>max then max:=m[n-c];
        if m[c]<min then min:=m[c];
      end;
    end;
    s:=s+1;
    if (n div 2)<>(n/2) then
    begin
      s:=s+2;
      if m[c+1]>max then max:=m[c+1];
      if m[c+1]<min then min:=m[c+1];
    end;
    write('Min=');
    writeln(min);
    write('Max=');
    writeln(max);
    write('Сравнений - ');
    writeln(s);
    writeln('');
  end;
END.
=== Dispose(Text,Done); ===

Пpиятная задачка, хотелось бы веpить, что можно за меньшее число сpавнений...

                           С кучей пожеланий - Andrew.

--- Ну очень голый GoldED+/386 1.1.5
 * Origin: Страшный-бородатый... (2:5071/59)