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

From

Yurij Zabelyshynskij ()

To

Andrew Starsh

Date

2002-12-23T22:17:47Z

Area

RU.ALGORITHMS

From: "Yurij Zabelyshynskij" <ergo@sky.net.ua>

Hi, Andrew.
Andrew Starsh wrote
>> Меньше нельзя (только при нечетном N должно
>> быть 1.5N - 1.5).

> Увы, Вы забыли, что может быть нечетное число,

Судя по моей фразе, как раз не забыл.

> Ваш коppеспондент забыл посчитать еще одно сpавнение.

Т.к. "мой корреспондент" не написал свой алгоритм, то мы не можем
говорить, что он забыл, а что нет.

> 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;

И что же будет, если пользователь введет n=300?

>     s:=1;
>     if m[1]>m[n] then

Это лишнее: ведь только что мы присвоили
m[1] := n, m[n] := 1

>     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;

А как же m[n-1]? Оно вообще ни с чем не сравнивается?

>     s:=s+1;
>     if (n div 2)<>(n/2) then

Т.е. Вы считаете еще проверку n на четность? Это лежит несколько в
стороне от задачи, потому что имеются в виду сравнения элементов
массива. Иначе надо еще учитывать, например, проверку выхода из цикла.

> [...]

В остальном идея правильная, но если уж писать код, то его проверять
нужно.

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

Вы, видимо, плохо читали мое сообщение. Я в нем написал, что за
меньшее количество сравнений это невозможно сделать.
--
WBR, Yura.

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)