Помощь - Поиск - Пользователи - Календарь
Полная версия: бинарный поиск. поля с рекурсией.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
lopata
19.01.2010 21:14
Бинарный поиск может быть применим на одно поле, в которое элемент сортировочно внесен.
Идея бинарного поиска состоит в том, чтобы сначала рассматривать средний элемент. Если он Искомый, тогда с успехом прерываете. Если не искомый, тогда можно через сравнение искомого элемента со средним установить, нужно ли в нижней или в верхней половине поля дальше искать. При каждом неудачном шаге поиска длина исследоваемой области (досягаемости) поля делится пополам.Это ведет к логарифмеческому Run-time:
при n элементах имеется 0(ld n) Шагов поиска.
Осуществите основе типа
TYPE
IntArray = array [...] of integer
рекурсивный алгоритм:
FUNCTION Contains (a :IntArray ; left,right : integer; x : integer) :BooLean;

который в сотрированном поле а внутри области [left...right] бинарно после значения х ищет и результат TRUE возвращает, когда х в поле оказывается.
Вышеуказанная фунукция использует call by value.

не совсем понимаю задания. очень туго доходит. хотя уверена что когда 2 строчки.
lopata
19.01.2010 21:46
сам бинарные деревья в принципе понимани.
но непонятно что это за параметры левый и правый целового типа
Archon
19.01.2010 22:18
Не следует путать простой бинарный поиск и бинарное дерево поиска. В твоем случае дерево строить не надо. Достаточно приведенной рекурсивной функции.

Параметры left и right - это начало и конец участка, внутри которого производится поиск. То есть сперва на место этих параметров подставляются начало и конец массива. Если элемент в середине отрезка не найден, функция должна вызвать саму себя (рекурсия), подставив на место left и right новые значения (а именно начало и конец той половины начального участка, в которой следует искать дальше).

PS Кстати, странно: в функции не предусмотрена возможность вернуть в программу найденный элемент. secret.gif
volvo
19.01.2010 22:30
Цитата
сам бинарные деревья в принципе понимани.
А причем тут бинарные деревья? Они к бинарному поиску никакого отношения не имеют...

Задача твоя - в том, чтобы получить массив (для бинарного поиска нужно, чтобы этот массив был упорядоченным, т.е., отсортированным, иначе этот метод не работает), и в этом массиве найти заданный элемент (или не найти его, это уж как повезет). Как это делается:

1. Поскольку решение тебе надо рекурсивное - то начинаем с условия окончания (странно, правда? Но так оно и делается, с этого начинается разработка любой рекурсивной подпрограммы, иначе зациклишь ее, и даже не заметишь). Итак. Что будет условием окончания? Когда поиск должен закончиться? Все просто: Когда Right + 1 = Left, то есть, между Right и Left нет других элементов. Тогда можно считать, что мы дошли до конца, и больше рекурсия продолжаться не будет.

Если это условие: 
if Right = Left + 1 then
выполняется, то остается проверить, равен ли элемент A[ Left ] или A[ Right ] заданному. Если равен - вернуть True, если нет - вернуть False.

2. Если между индексами Left и Right есть еще элементы, то надо найти середину (среднее арифметическое), и вызывать функцию рекурсивно, вместо Right или Left подставляя значение этой середины.

Вот и все, собственно. Попробуй по написанному здесь объяснению написать код. Хотя бы его начало. Что не понятно, или не получается - говори. Задача действительно решается в несколько строк.

P.S. Поиском, значит, опять не пользуемся. Ну-ну... Потом расскажу, откуда я узнал об этом... smile.gif
lopata
19.01.2010 22:51
Все, товарищи, спасибо. Дико ступила. стыдно
lopata
20.01.2010 1:08
Ошибка использования BB кодов форума. Возможно вы неправильно использовали какой-то из тэгов, как, например, тэг [TAG], тогда как он должен использоваться в виде [TAG=] или наоборот.
//
Не хочет код писать/

Добавлено через 13 мин. 

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR m: integer;
BEGIN
IF (R+1)= L
   THEN
       BEGIN
       IF (x=a[r])or (x=a[l])THEN Contains := TRUE
          ELSE
              BEGIN
              m := r+(l-r)div 2;
              IF x=a[m] THEN Contains := TRUE
                 ELSE
                     IF x> a[m] THEN BEGIN
                        r := m+1;
                        Contains := Contains(a,l,r,x)
                     END
                     ELSE BEGIN
                          l := middle-1;
                          Contains := Contains(a,l,r,x)
                     END;
END;
END;



Добавлено через 52 сек.
пришлось сократить\
lopata
20.01.2010 22:35
Не. не правильно..
вот кое-что изменила:

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
IF (R+1)= L THEN
   BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
           ELSE Contains := FALSE
END
   ELSE
       BEGIN
       m := r+(l-r)div 2;
       IF x=a[m] THEN Contains := TRUE
          ELSE BEGIN
               IF x> a[m] THEN BEGIN
                  r := m+1;
                  Contains := Contains(a,l,r,x)
               END
                  ELSE BEGIN
                       l := m-1;
                       Contains := Contains(a,l,r,x)
                  END;

       END;
END;


l = left
r = right
m = middle
И еще почему в dev pascal ругается что overloaded identifier Contains isn't a function
Archon
20.01.2010 22:55
И все-таки неправильно. Покажи целиком программу, в которой ты тестируешь эту функцию. Заодно будет проще понять, почему dev pascal ругается =)

Добавлено через 4 мин.
Первое, что бросилось в глаза: 
IF (R+1)= L THEN
Путаешь право и лево. Так ты никогда из рекурсии не выйдешь.

Добавлено через 15 мин.
Ух, да у тебя по всей программе так. Но даже если поменять их местами, твой алгоритм порой выходит за границы исходного интервала. Например, на следующих исходных данных: 
. . .
var
	Arr: array[1..3] of Integer = (1, 2, 4);
begin
	Contains(Arr, 1, 3, 6);
end.
lopata
20.01.2010 23:49
Archon, честно говоря не совсем понимаю о чем ты unsure.gif
Archon
21.01.2010 0:20
Ну смотри:
L - это же Left (левая граница интервала), верно?
R - тогда соответственно Right (правая граница).
То есть L < R. Тогда как R + 1 может равняться L?
lopata
21.01.2010 0:24
аха, это поняла...наоборот

Добавлено через 1 мин.
поняла. счас исправлю..действительно по всей программе то же самое

Добавлено через 2 мин.
А с остальным что не так? unsure.gif
Archon
21.01.2010 0:43
А ты проверь с приведенным выше массивом. Там всего 3 элемента - можно и в уме сделать.
lopata
21.01.2010 1:39
все равно не понимаю/
Archon
21.01.2010 2:53
На приведенных мной исходных данных функция из рекурсии никогда не выйдет. Если в уме не получается, запусти программу и убедись.

Добавлено через 4 мин.
И вообще будет выход за границы массива.
lopata
21.01.2010 3:16
это я уже поняла...
тогда нужно поставить условие 

while left<= right do


вроде
я запуталась/

Добавлено через 7 мин.
и нифига это тогда не рекурсия получется
lopata
21.01.2010 3:49
алилуя...
или очередное заблуждение или просвет :

FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
IF l <> r THEN
   BEGIN
       m := l+(r-l)div 2;
       IF x=a[m] THEN Contains := TRUE
          ELSE BEGIN
               IF x> a[m] THEN BEGIN
                  l := m+1;
                  Contains := Contains(a,l,r,x)
               END
                  ELSE BEGIN
                       r := m-1;
                       Contains := Contains(a,l,r,x)
                  END;
          END;
   END
ELSE
   BEGIN
        IF (x=a[r])or (x=a[l])THEN contains := TRUE ELSE   contains := FALSE
   END

END;

Archon
21.01.2010 10:55
Ну, не совсем =) Лучше было бы так сделать: 
FUNCTION Contains (a :IntArray;l,r:integer ;x : integer) :BooLean;
VAR M: integer;
BEGIN
    IF (l+1) = r THEN
    BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
        ELSE Contains := FALSE;
    END
    ELSE
    BEGIN
        m := l+(r-l)div 2;
        { Проверку x=a[m] тоже убрал, так как на следющем шаге рекурсии этот }
        { элемент станет границей и все равно проверится                     }
        IF x> a[m] THEN BEGIN
            l := m; { Тут убрал "+1" }
            Contains := Contains(a,l,r,x)
        END
        ELSE BEGIN
            r := m; { Тут убрал "-1" }
            Contains := Contains(a,l,r,x)
        END;
    END
END;
Сравни со своей старой версией.

Но это один из вариантов решения: тот, который описал volvo. Если брать строго тот алгоритм, что приведен в задании, получится так: 
function Contains (a: IntArray; l, r: Integer; x: Integer): Boolean;
var
	m: Integer;
begin
	if l > r then
		Contains := False
	else begin
		m := l + (r - l) div 2;
		if x = a[m] then
			Contains := True
		else if x < a[m] then
			Contains := Contains(a, l, m - 1, x)
		else
			Contains := Contains(a, m + 1, r, x);
	end;
end;
Ищи отличия smile.gif
volvo
21.01.2010 19:50
Цитата
    IF (l+1) = r THEN
    BEGIN
        IF (x=a[r])or (x=a[l])THEN Contains := TRUE
        ELSE Contains := FALSE;
    END
лучше заменить на
if L + 1 = R then
  Contains := (x=a[R]) or (x=a[L])
, вместо включения еще одного условия...

Цитата
И еще почему в dev pascal ругается что overloaded identifier Contains isn't a function
Dev-Pascal это оболочка. Компилятор, который там используется (если я не ошибаюсь, давно его использовал) - FPC. В каком режиме совместимости ты компилируешь программу, что у тебя возникает такая ошибка (и заодно - какая версия компилятора? Вполне возможно, что тебе надо ее просто обновить)? Ты часом не пытаешься эту функцию в модуле (в Unit-е, в смысле) описывать?
lopata
21.01.2010 21:06
Цитата(volvo @ 21.01.2010 19:50) *

Dev-Pascal это оболочка. Компилятор, который там используется (если я не ошибаюсь, давно его использовал) - FPC. В каком режиме совместимости ты компилируешь программу, что у тебя возникает такая ошибка (и заодно - какая версия компилятора? Вполне возможно, что тебе надо ее просто обновить)? Ты часом не пытаешься эту функцию в модуле (в Unit-е, в смысле) описывать?

1.9.2.
неа. не в модуле.


Добавлено через 4 мин.
а по поводу совместимости не знаю что сказать/
volvo
21.01.2010 21:12
Цитата
1.9.2.
blink.gif Уже 2.2.4 на дворе... Ты б скачала новую версию FPC, и прямо там бы работала, зачем тебе этот DevPascal нужен?
lopata
21.01.2010 21:16
ну как..если в DevPascal не работает, я в FPC проверяю.
мне в DevPasca приятней)
lopata
22.01.2010 5:04
Всем спасибо. smile.gif
Жаль , что до меня все туго доходит.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.