Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц, летом дешевле!

Ответ
 
Опции темы Поиск в этой теме
Старый 27.05.2010, 15:26   #1
Driver_09
Пользователь
 
Регистрация: 11.10.2009
Сообщений: 61
По умолчанию Бинарный поиск в массиве

У меня почему-то неправильно работает бинарный поиск, конкретно выводит "-1" - якобы нет этого элемента...
l - первый элемент массива
r - последний элемент массива
cr- среднее значение
ну я думаю бинарный поиск многие знают, но на всякий случайт напишу:
Цитата:
1)делим массив пополам cr=(r+l)/2
2)если искомый элемент наход правее середины, то делим ещё правую часть пополам и так пока не найдём элемент
3)если искомый элемент левее середины, то делим левую часть пополам, затем ещё пополам пока не найдём элемент.
может быть у меня неправильно условия после нахождения середины массива или результат не там стоит? вот код:
Цитата:
Function poisk_bin(var m:mas; NMAX,v:integer):integer;
var l,r,cr:integer;
begin
l:=1;
r:=NMAX;
while(l<>r) do
begin
cr:=(l+r) div 2;
if (v=m[cr]) then
begin
Result:=cr;
break;
end
else if (v>m[cr]) then
l:=(cr+r) div 2
else
r:=(cr-l) div 2;
result:=-1;
end;

end;

Последний раз редактировалось Driver_09; 27.05.2010 в 15:29.
Driver_09 вне форума Ответить с цитированием
Старый 27.05.2010, 18:23   #2
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Код:
Function poisk_bin(var m:mas; NMAX,v:integer):integer;
var l,r,cr:integer;
begin
l:=1;
r:=NMAX;
while(l<>r) do
begin
 cr:=(l+r) div 2;
 if (v=m[cr]) then
  begin
  Result:=cr;
  break;
  end
 else if (v>m[cr]) then
  l:=cr+1; //l:=(cr+r) div 2
 else
  r:=cr-1; //r:=(cr-l) div 2;
result:=-1;
end;

end;
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 27.05.2010, 21:09   #3
Driver_09
Пользователь
 
Регистрация: 11.10.2009
Сообщений: 61
По умолчанию

почему-то ошибка...
Цитата:
if (v=m[cr]) then
begin
Result:=cr;
break;
end
else if (v>m[cr]) then
l:=cr+1; //l:=(cr+r) div 2
else
r:=cr-1; //r:=(cr-l) div 2;
ему не нравится else, который я выделил жирным шрифтом
Driver_09 вне форума Ответить с цитированием
Старый 27.05.2010, 21:56   #4
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Убери точку с запятой перед else
Код:
if (v=m[cr]) then
begin
Result:=cr;
break;
end
else if (v>m[cr]) then
 l:=cr+1
else
 r:=cr-1;
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 28.05.2010, 08:47   #5
Driver_09
Пользователь
 
Регистрация: 11.10.2009
Сообщений: 61
По умолчанию

нашёл ошибку, почему компилятор ругался...
но всё равно не правильно...результат -1 или ничего не выводит
Driver_09 вне форума Ответить с цитированием
Старый 28.05.2010, 10:05   #6
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

скинь полный код.
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 28.05.2010, 13:08   #7
Driver_09
Пользователь
 
Регистрация: 11.10.2009
Сообщений: 61
По умолчанию

ну если полный код, то вот и полное задание:
нужно произв. массив осортировать, и сделать в нём 2 вида поиска: бинарный и интерполяционный.
Второй поиск ещё как-то через раз работает, а вот бинарный нет

Цитата:
program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

const NMAX=10;
type mas=array[1..NMAX] of integer;

procedure generate(var m:mas);
var i:integer;
begin
Randomize;
for i:= 1 to NMAX do
m[i]:=Random(99);
end;

procedure show(m:mas);
var i:integer;
begin
for i:=1 to NMAX do
write(m[i],' ');
writeln;
end;


procedure gnome_sort(var m:mas);
var i,tmp:integer;
begin
i:= 1;
repeat
if m[i]<m[i+1] then
begin
tmp:=m[i];
m[i]:=m[i+1];
m[i+1]:=tmp;
if i=1 then i:=i+1
else i:=i-1;
end
else
i :=i+1;
until ( i=NMAX )

end;

Function poisk_bin(var m:mas; NMAX,v:integer):integer;
var l,r,cr:integer;
begin
l:=1;
r:=NMAX;
while(l<>r) do
begin
cr:=(l+r) div 2;
if (v=m[cr]) then
begin
Result:=cr;
break;
end
else if (v>m[cr]) then
l:=cr+1 //l:=(cr+r) div 2
else
r:=cr-1; //r:=(cr-l) div 2;
result:=-1;
end;

end;


Function poisk_inter(var m:mas; NMAX,v:integer):integer;
var L,R,i:integer;
begin
R:=NMAX;
l:=1;
result:=-1;
while (R<>L) do
begin
i:=L+((v-m[L])*(R-L))div(m[R]-m[L]);
if v>m[i] then
L:=i+1
else if v<m[i] then
R:=i-1
else
begin
Result:=i;
break;
end;
end;

end;

var m:mas; v:integer;
begin
generate(m);
write('massiv:');
show(m);
gnome_sort(m);
write('sortirovka:');
show(m);
write('vv chislo:' ); readln(v);
writeln('inter N=',poisk_inter(m,NMAX,v));
writeln('binar N=',poisk_bin(m,NMAX,v));
readln;
end.
Driver_09 вне форума Ответить с цитированием
Старый 28.05.2010, 15:50   #8
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Код:
Function poisk_bin(var m:mas; NMAX,v:integer):integer;
var l,r,cr:integer;
begin
l:=1;
r:=NMAX;
repeat
  cr:=(l+r) div 2;
  if (v=m[cr]) then
    begin
    Result:=cr;
    Exit;
    end
  else if (v>m[cr]) then
   r:=cr-1
  else
   l:=cr+1;
until ( l=r );
if m[l] = v then result := l else result:=-1;
end;
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 28.05.2010, 15:53   #9
Driver_09
Пользователь
 
Регистрация: 11.10.2009
Сообщений: 61
По умолчанию

работает прога теперь
Driver_09 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц, летом дешевле!

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Бинарный поиск CraZZZy-GameRRR Общие вопросы Delphi 8 25.05.2010 14:57
Нужен совет(бинарный поиск в 2-d массиве) sergey31 Помощь студентам 2 27.04.2008 13:49
Бинарный поиск в 1мерном массиве, ошибка в программе из книги ILDAR@GIZmo Помощь студентам 4 02.12.2007 22:22