Форум: "Начинающим";
Текущий архив: 2007.02.04;
Скачать: [xml.tar.bz2];

Вниз

Мин. и макс. значения   Найти похожие ветки 

← →
MaxInside   (2007-01-20 18:37) [0]

У меня есть массив, например  ar1: array [0..1234] of Integer; = 100, 101, 103, 105, 108, ...

И есть некоторое число допустим: 107, как мне быстрее и корректнее всего оперделить либо наличие этого числа в массиве или если его нет в массиве, то найти минимальный и максимальный элемент, между которыми это число должно присутствовать. В моём примере, это 108 и 105.

?

---

← →
Джо ©   (2007-01-20 18:40) [1]

используй for и операторы сравнения.

---

← →
MaxInside   (2007-01-20 18:48) [2]

Нет ну про то, что требуется организовать цикл, я догадался :-) Но моё решение в лоб я думаю будет слишком долго выполняться по времени, поэтому и сперашиваю про оптимальный способ... Просто проверить наличие элемента в массиве -- это понимаю, как реализовать; но вот как найти макс и мин элементы -- увы.

---

← →
Джо ©   (2007-01-20 18:49) [3]

> но вот как найти макс и мин элементы -- увы.

используй операторы сравнения и оператор присваивания.

---

← →
MaxInside   (2007-01-20 19:18) [4]

Хмм.. ну я придумал видимо полный бред.

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;


И что теперь найти макс и мин элементы в полученных двух массивах соответственно? Хотя это бред полный...

---

← →
Anatoly Podgoretsky ©   (2007-01-20 19:35) [5]

Ипользуй цикл и сравнение.
Цикл нужен один, а не кучу.

---

← →
Virgo_Style ©   (2007-01-20 19:43) [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;


т.е. массив делится на две части и проверяется, в какой из них может быть искомое. Эта часть делится еще на две, и т.д., пока либо число не найдется, либо границы не сожмутся.

---

← →
Palladin ©   (2007-01-20 19:49) [7]

> [6] Virgo_Style ©

ужас

---

← →
Virgo_Style ©   (2007-01-20 20:38) [8]

Palladin ©   (20.01.07 19:49) [7]
заинтригован

---

← →
Palladin ©   (2007-01-20 21:13) [9]

в случае отсортированного массива

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 21:43) [10]

Palladin ©   (20.01.07 21:13) [9]
Проще, полагаю, что и оптимальнее, но насчет понятности я, наверное, позволил бы себе поспорить. Впрочем, дело вкуса.

Так или иначе, спасибо за науку %-)

---

← →
Palladin ©   (2007-01-20 21:44) [11]

Это всего лишь реализация бинарного поиска.

---

Страницы: 1 вся ветка

Форум: "Начинающим";
Текущий архив: 2007.02.04;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.48 MB
Время: 0.047 c