|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 23 Dec 2002 23:17:47
To : Andrew Starsh
Subject : Re: Ускорение поиска максимума...
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
