 |
|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrew Starsh 2:5071/59 21 Dec 2002 16:49:18 To : Anton Kuznetsov Subject : Re^2: Ускорение поиска максимума... --------------------------------------------------------------------------------
Приветствую Вас, 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.
--- Hу очень голый GoldED+/386 1.1.5
* Origin: Страшный-бородатый... (2:5071/59)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/18823e048fc0.html, оценка из 5, голосов 10
|
|
|