IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Бинарный (двоичный) поиск, только для отсортированного массива
сообщение
Сообщение #1


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


value - искомое значение
right и left - сдвигающиеся границы массива.


Код

procedure bin_s;
var
  value:integer{array type};
  x:array[1..n] of integer;
  i,nn,nfind,right,left:integer;
begin
  writeln('value=');readln(value);
  left:=1;
  right:=n;
  while ((right-left)>1) do
   begin
      nn:=(right+left) div 2;
      if value<=x[nn] then
       right:=nn
        else left:=nn;
   end;
   if value=x[left] then
    nfind:=left
     else if value=x[right] then
      nfind:=right;
  writeln('nfind=',nfind);
  readln;
end;


Скорость :
1000 элементов - 10 итераций цикла.

Процедура не срабатывает с такими исходными данными (возвращается результат "nfind = 2"):
const
n = 20;
x: array[1 .. n] of integer =
( 4, 5, 6, 15, 18, 21, 28, 32, 34, 38,
43, 44, 49, 50, 59, 60, 63, 73, 77, 85);
{ Значение для поиска: value = 34 }

Volvo


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 12)
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


НЕ знаю почему, я с этим уже сталкивался и объяснить не могу, но вот так работает :

Код
const n = 20;

const
x: array[1 .. n] of integer =
  ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
   43, 44, 49, 50, 59, 60, 63, 73, 77, 85);

{ задай для поиска value = 34 }

procedure bin_s;
var
value:integer{array type};
 { тут не надо объявлять массив ! ! !}
i,nn,nfind,right,left:integer;
begin
writeln('value=');readln(value);
left:=1;
right:=n;
while ((right-left)>1) do
  begin
    nn:=(right+left) div 2;
    if value<=x[nn] then
      right:=nn
    else left:=nn;
  end;

if value=x[left] then
  nfind:=left
else if value=x[right] then
       nfind:=right;
writeln('nfind=',nfind);
readln;
end;

var i: integer;
begin
for i := 1 to n do
  write(x[i]:4);
writeln;

bin_s
end.


Теперь все просто отлично работает, но почему!!!!?? не работало до этого ??
ИМХО это баги паскаля, связанные с глобальными и локальными переменными...

Сообщение отредактировано: klem4 -


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата(klem4 @ 25.02.05 7:06)
ИМХО это баги паскаля, связанные с глобальными и локальными переменными...

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

Кстати, еще вопрос:
Допустим, у тебя 3 массива: X, X1, X2.
Код

Var x, x1, x2: array[1 .. n] Of integer;
Procedure bin_s;
Begin ... End;

{ Вот тут тебе надо найти номер элемента из массива X1 }
...
{ тут - элемента из массива X2 }
...
{ а вот тут - номер элемента из массива X }

Твои действия?

Или еще более коварный вариант - если все 3 массива имеют разную размерность...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Вот :low:

Код
uses crt;
const n=15;
type mass=array[1..n] of integer;
var x:mass;
   i:integer;
function bin_s(x:mass):integer;
var right,left:integer;
   nn,value:integer;
   nfind:integer;
begin
  write('Value=');readln(value);
  left:=1;
  right:=n;
  while (right-left>1) do
   begin
      nn:=(right+left) div 2;
      if value>x[nn] then
       left:=nn
        else right:=nn;
   end;
   if x[left]=value then
    nfind:=left
     else if x[right]=value then
      nfind:=right
       else nfind:=0;
   writeln;
   writeln('Nfind=',nfind);
end;
Begin
  for i:=1 to n do
   readln(x[i]);
  bin_s(x);
  readln;
end.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата(volvo @ 25.02.05 9:41)
Или еще более коварный вариант - если все 3 массива имеют разную размерность...

Я так понимаю, этот вариант не рассматривался? smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Щас сделаем smile.gif...


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Не могу найти ошибку sad.gif

Код
uses crt;
type

  arrT=array[1..1000] of integer;

var
   x:arrT;
   y:arrT;
   z:arrT;
   i:integer;
   m,n:integer;

function f(z:arrT;p:integer):integer;
var
  value:integer;
  left,right:integer;
  nn:integer;
  nfind:integer;
begin
 write('Value=');readln(value);
 left:=1;
 right:=p;
 while (right-left>1) do
  begin
     nn:=(right+left) div 2;
     if value>z[nn] then
      left:=nn
       else right:=nn;
  end;
  if z[left]=value then
   nfind:=left
    else if z[right]=value then
     nfind:=right
      else nfind:=0;
  writeln;
  writeln('Nfind=',nfind);
end;
Begin
  clrscr;
  write('n=');
  readln(n);
  for i:=1 to n do
   readln(x[i]);
  writeln;
  f(x,n);
  readln;
end.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






А в чем, собственно, ошибка? Эта программа отрабатывает.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


например 1,2,3,0,5 если искать 0 то возвращает nfind=0.
Или тока у меня ??))


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






А как же упорядоченность? "Бинарный (двоичный) поиск, только для отсортированного массива"... Массив <1, 2, 3, 0, 5> не является отсортированным
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


так точно!) ну значит теперь все в поряде smile.gif


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата(klem4 @ 27.02.05 11:10)
ну значит теперь все в поряде smile.gif

Правда? А у меня еще несколько вопросов...
1. Описана функция... А что, собственно, она возвращает?
2. При работе с бОльшими массивами - проблемы... Попробуй, например, описать вот так:
Код
type
 arrT=array[1..10000] of integer;

и запустить программу. Что произойдет? А ведь этот метод по определению желательно использовать для больших объемов данных... Так что еще не все..
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Проверь вот это:
Код
Type
 TType = Integer;

Function bin_search(Var x: Array Of TType;
        Const n: Integer; Value: TType): Integer;
Var
 nn, nFind, Right, Left: Integer;
Begin
 Left := 0; Right := Pred(n);
 While (Right - Left) > 1 Do
   Begin
     nn := (Right + Left) div 2;
     If Value <= x[nn] Then Right := nn
     Else Left := nn
   End;

 If Value = x[Left] Then nFind := Left
 Else
   If Value = x[Right] Then nFind := Right
   Else nFind := -2;

 bin_search := nFind + 1;
End;


Const
 n_1 = 20;
 x: array[1 .. n_1] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85);

 n_2 = 25;
 x1: array[1 .. n_2] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85,
    86, 87, 88, 89, 90);

 n_3 = 30;
 x2: array[1 .. n_3] of TType =
   ( 4,  5,  6, 15, 18, 21, 28, 32, 34, 38,
    43, 44, 49, 50, 59, 60, 63, 73, 77, 85,
    86, 87, 88, 89, 90, 91, 92, 93, 94, 95);

var
 i: integer;

begin
 writeln( bin_search(x, n_1, 18) );
 writeln( bin_search(x1, n_2, 38) );
 writeln( bin_search(x2, n_3, 94) );
end.
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 16:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name