| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Мин. и макс. значения [D6, D7]
MaxInside © (2007-01-20 18:37:00)У меня есть массив, например ar1: array [0..1234] of Integer; = 100, 101, 103, 105, 108, ...
И есть некоторое число допустим: 107, как мне быстрее и корректнее всего оперделить либо наличие этого числа в массиве или если его нет в массиве, то найти минимальный и максимальный элемент, между которыми это число должно присутствовать. В моём примере, это 108 и 105.
?
Palladin (2007-01-20 21:44:00) [1]Это всего лишь реализация бинарного поиска.
Virgo_Style (2007-01-20 21:43:00) [2]Palladin © (20.01.07 21:13) [9]
Проще, полагаю, что и оптимальнее, но насчет понятности я, наверное, позволил бы себе поспорить. Впрочем, дело вкуса.
Так или иначе, спасибо за науку %-)
Palladin (2007-01-20 21:13:00) [3]в случае отсортированного массива
var
A:array[0..9] of integer=(0,7,10,57,84,93,105,120,133,144);
Function Find(n:Integer;var rp_nIndex:Integer):Boolean;
Var
L,R,M,C:Integer;
Begin
Result:=False;
L:=0;
R:=Length(A)-1;
While L<=R Do
Begin
M:=(L+R) shr 1;
C:=A[M]-N;
If C<0 Then L:=M+1 Else
Begin
R:=M-1;
If C=0 Then
Begin
Result:=True;
L:=M;
End;
End;
End;
rp_nIndex:=L;
End;
procedure TForm1.Button1Click(Sender: TObject);
Var
n:Integer;
begin
If Find(95,n) Then ShowMessage('Founded at '+IntToStr(n)) Else
If n=0 Then ShowMessage('Right[0]='+IntToStr(A[0])) Else
If n=(Length(A)-1) Then ShowMessage('Left['+IntToStr(n)+']='+IntToStr(A[n]))
Else ShowMessage('Left['+IntToStr(n-1)+']='+IntToStr(A[n-1])+' Right['+IntToStr(n)+']='+IntToStr(A[n]));
end;
проще не правда ли?
Virgo_Style (2007-01-20 20:38:00) [4]Palladin © (20.01.07 19:49) [7]
заинтригован
Palladin (2007-01-20 19:49:00) [5]
> [6] Virgo_Style ©
ужас
Virgo_Style (2007-01-20 19:43:00) [6]еще не проснулся, если брежу - прошу прощения. Но как будто бы работает.
массив упорядочен? тогда:
var Arr:array[1..10] of integer=(0,7,10,57,84,93,105,120,133,144);
procedure TForm1.Button1Click(Sender: TObject);
var LowBorder, HighBorder, i, SearchFor:Integer;
Found:boolean;
FoundAt:Integer;
S:String;
begin
found:=false; //"нашли точное значение"
FoundAt:=-1; //где нашли
SearchFor:=StrToInt(Edit1.Text);//кого ищем
//инициализация границ поиска
LowBorder:=Low(Arr);
HighBorder:=High(Arr);
//находится ли искомое в пределах массива?
if SearchFor<Arr[LowBorder] then
raise Exception.Create('Это под землей');
if SearchFor>Arr[HighBorder] then
raise Exception.Create('Это в космосе');
//А может, оно на границах?
if SearchFor = Arr[ LowBorder ] then begin
found:=true;
FoundAt:=LowBorder;
end else
if SearchFor = Arr[ HighBorder ] then begin
found:=true;
FoundAt:=HighBorder;
end else
//вот теперь ищем
repeat
//бьем отрезок пополам
i:=(LowBorder+HighBorder) div 2;
//и проверяем значение в центре
if Arr[i]>SearchFor then HighBorder:=i else
if Arr[i]<SearchFor then LowBorder:=i else
if Arr[i]=SearchFor then begin
//проверка на равенство после двух проверок на больше-меньше -
// - это из разряда "безобразно, зато единообразно".
found:=true;
FoundAt:=i;
end;
//Границы уперлись друг в друга
if (HighBorder-LowBorder<=1) then begin
FoundAt:=HighBorder;
break;
end;
until found;
// теперь отображаем, что у нас получилось.
S:='';
for i:=Low(Arr) to High(Arr) do
if i=FoundAt then begin
if found then
S:=S+' ['+IntToStr(Arr[i])+'] '
else
S:=S+' (тут) '+IntToStr(Arr[i])+' '
end else S:=S+' '+IntToStr(Arr[i])+' ';
Memo1.Lines.Add(S);
end;
т.е. массив делится на две части и проверяется, в какой из них может быть искомое. Эта часть делится еще на две, и т.д., пока либо число не найдется, либо границы не сожмутся.
Anatoly Podgoretsky (2007-01-20 19:35:00) [7]Ипользуй цикл и сравнение.
Цикл нужен один, а не кучу.
MaxInside (2007-01-20 19:18:00) [8]Хмм.. ну я придумал видимо полный бред.
var
ar1: array [0..11 - 1] of Integer =
(100, 101, 102, 104, 105, 108, 111, 112, 114, 119, 121);
procedure TForm1.Button1Click(Sender: TObject);
const
u1: Integer = 106;
var
i: Integer;
MaxAr, MinAr: array of Integer;
begin
for i := Low(ar1) to High(ar1) do
if ar1[i] = u1 then Break;
if i < High(ar1) then
begin
ShowMessageFmt('Position: %d', [i]);
Exit;
end;
for i := Low(ar1) to High(ar1) do
if ar1[i] < u1 then
begin
SetLength(MinAr, Length(MinAr) + 1);
MinAr[Length(MinAr)] := ar1[i];
end;
for i := Low(ar1) to High(ar1) do
if ar1[i] > u1 then
begin
SetLength(MaxAr, Length(MaxAr) + 1);
MaxAr[Length(MaxAr)] := ar1[i];
end;
И что теперь найти макс и мин элементы в полученных двух массивах соответственно? Хотя это бред полный...
Джо (2007-01-20 18:49:00) [9]> но вот как найти макс и мин элементы -- увы.
используй операторы сравнения и оператор присваивания.
MaxInside (2007-01-20 18:48:00) [10]Нет ну про то, что требуется организовать цикл, я догадался :-) Но моё решение в лоб я думаю будет слишком долго выполняться по времени, поэтому и сперашиваю про оптимальный способ... Просто проверить наличие элемента в массиве -- это понимаю, как реализовать; но вот как найти макс и мин элементы -- увы.
Джо (2007-01-20 18:40:00) [11]используй
forи операторы сравнения.
| |
