Рекурсии Опции

[Вадим]

Помогите написать программу.
Разработать рекурсивную процедуру двоичного поиска элемента массива, равного данному числу.

Сообщение отредактировано: Вадим - 10.10.2004 21:10

[Amro]

А массив уже упорядочен чтоль, или его ещё сортировать нуно?

[Вадим]

Условие точное, но скорее всего массив надо сортировать

[godd]

что такое двоичный поиск? поиск двоичного числа? или че?
вот поиск обычного:

на С++ (на Pascale с указателями не работал и функций не писал - не приходилось)

Код

//Шаблон - при объявлении функции IndexOfArray просто определяется тип VT и подставляется где надо
//VT - VarType
template <class VT> int IndexOfArray(int max_i,VT *pointer,VT Iskomoe,int i=0)
{
if (*pointer==Iskomoe) return i;  //если элемент массива равен Нужному_Числу - функция возвращает индекс элемента массива
else
    {
     ++i;                                          //увеличиваем счетчик
     if (i>max_i) return -1;                //если прошли весь массив - возвращаем -1
     else
          {
           ++pointer;                               //перемещаем указатель на следующий элемент массива
           IndexOfArray(max_i,pointer,Iskomoe,i); //рекурсия
          }
     }
}

P.S. Сортировать ничего не надо - просто перемещаем указатель на следующий элемент массива
P.P.S. В функцию передавай 3аргумента, i - определен по умолчанию, если передашь его - собьешь счетчик (ну разве что 0 передай и фсе), max_i - последний элемент массива

Сообщение отредактировано: godd - 10.10.2004 23:23

[Amro]

Нет godd это не поиск двоичного числа это поиск элемета в упорядоченном массиве........короче берём массив и искомый элемент далее делим массив пополам и смотрим в какой части находится искомый элемент, далее берём эту часть и делим её пополам и.д пока не найдём этот элемент....... Таким образом скорость поиска увеличится на много порядков.

Вадим В инете ведь полно информации по двоичному поиску, когда-то я сам искал этот поиск......правда через рекурсию не видал, но там вроде тоже ни чего сложного нету, в общем попробуем реализовать......

[fms]

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

Код

PROGRAM prog;
FUNCTION b_search(s: STRING; a,b: INTEGER; c: CHAR): INTEGER;
    VAR i: INTEGER;
    BEGIN
 IF a>b THEN b_search:=0 ELSE
 BEGIN
 i:=(a+b) DIV 2;
 IF s[i]=c THEN b_search:=i
 ELSE  IF s[i]<c THEN b_search:=b_search(s,i+1,b,c)
 ELSE b_search:=b_search(s,a,i-1,c);
 END
 END;
    VAR
 s:STRING;
 i:INTEGER;
 c:CHAR;
    BEGIN
 WRITE('Введите строку:');
 READLN(s);
 b:= ORD(s[0]); {Длина строки}
 i:=0; {Это проверка упорядоченности символов в строке}
 REPEAT
     i:=i+1;
 UNTIL (a[i+1]<a[i]) or (i= b-1); {Конец проверки строки}
    IF a[i+1]<a[i] THEN WRITELN('Строка введена неправильно')
 ELSE BEGIN
     WRITE('Введите искомый символ:');
     READLN( c );
     i:=b_search(s,1,ORD(s[0]),c);
 IF i=0 THEN WRITELN('Искомого символа в строке нет')
 ELSE WRITELN('Искомый символ имеет номер ', i);
 END;
    END.

[godd]

скорость поиска увеличиться? ну разве что в отсортированном массиве, а ведь его еще надо будет отсортировывать - так что в итоге во времени проигрышь. разве что сортировка массива подразумевается условием самой задачи.

я тут кое-чо тоже написал
вот процедура:

Код

procedure IndexOfArray(niz,verh,iskomoe:byte)
begin
if niz<verh then
  if arr[round(verh*0.5)]>iskomoe then IndexOfArray(niz,round(verh*0.5),iskomoe)
  else IndexOfArray(round(verh*0.5),verh,iskomoe);
end

Должно работать, сам не проверял. Предполагается что массив уже отсортированный, первоначально verh:=конец_массива, niz:=начало_массива, Iskomoe:=Искомое. Предполагается что array[x..n] of byte, но в под конкретный тип переделать - просто.

P.S. Вадим, переделай эту фигню в функцию
P.P.S Я на C++ переехал, про функции - если понадобяться, то потом почитаю. Пока не надо )) => сам делай

__________
вначале по привычке trunc написал. надо - round [округление по правилам математики]

Сообщение отредактировано: godd - 11.10.2004 1:26

[godd]

посчет времени - рекурсия это вообще дело нехорошее.
она хороша только тем что упрощает текст проги, а минус - медленность работы, вывод - лучше писать обычные нерекурсивные функции забив все это дело по циклам, а рекурсию использовать тока когда это явно указано в задаче.

[Amro]

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

Код

uses crt;
const
L=1;
R=25;
var
i,Key : integer;
Mas:array[L..R] of integer;
{...........................................................}
procedure Sort(Left,Right:integer);
var
i,j,w,x:integer;
begin
i:=Left; j:=Right;
x:=Mas[(Left+Right) div 2];
repeat
while (Mas[i]<x) do
inc(i);
while (x<Mas[j]) do
dec(j);
if i<=j then
begin
W:=Mas[i]; Mas[i]:=Mas[j]; Mas[j]:=W; inc(i); dec(j);
end
until i>j;
if Left<j then Sort(Left,j); if (i<Right) then Sort(i,Right)
end;
{.............................................................}
procedure found(Left,Right:integer);
var
middle:integer;
begin
  if (Left<=Right) then
     begin
     Middle:=(Left+Right) div 2;
       if  Key < Mas[Middle] then found(Left,Middle-1);
         if Key > Mas[Middle] then found(Middle+1,Right);
           if  Key=Mas[Middle] then write('Его номер ',Middle);
     end
                          else write(key);
end;
{...........................................................}
begin
clrscr;
for i:=L to R do begin
   Mas[i]:=random(99);
write(Mas[i]:3); end;
Sort(L,R);
writeln;
for i:=L to R do
write(Mas[i]:3);
writeln;
write('Введите искомый элемент: ');
read(Key);
found(L,R);
readkey;
end.

Одно НО, прога выдаёт номер элемента сразу же после его первого вхождения....надо чёт на счёт генерации придумать, кстати я вот не помню можно ли так генерировать элементы массива чтобы одинаковых не было???
Процедура сортировки тоже рекурсивная (быстрая сортировка QuickSort или сортировка С.Хоаром)
Кстати fms эту сортировку я там надыбал именно в том архиве, на который ты мне кидала ссылку на форуме, много я тама полезного нашёл.......
godd на счёт времени рекурсии - эт ты верно подметил.................................

Сообщение отредактировано: Amro - 11.10.2004 1:30

[godd]

недоглядел в тексте Amro. Не то написал. Удалить пост незя.

Сообщение отредактировано: godd - 11.10.2004 1:39

[godd]

Amro
по поводу рекурсии - это я прочитал где-то.

[godd]

Недоглядел я. Ему ж процедура нужна была. А я вроде как функция прочитал.

[Amro]

Ты прав надо сравнивать только с крайним элементом полововины!!! У меня в проге это и реализованно.......просто в моих начальных словах я этого не досказал впопыхах, но самое главное что суть сего метода была мной сформулированна...
а она закл в делении массива надвое....... :yes:

[Amro]

Во во я также сначала функцией пытался сделать, тоже не прочитал внимательно, целый час долбился с функцией и переполнением стека, а потом решил прочитать условие заново..

[godd]

генерировать элементы массива чтобы одинаковых не было???

мона. вначале проги randomize ставишь, а элементы приравниваешь к random(z), где z - положительное число, верхний предел значений - z-1, если надо отрицательное включать, или числа с плавающей точкой воспроизводить - измываешся над random(z): random(z)-trunc(z*0.5), random(z)/random(z*0.3), ну и далее в этом духе

[Guest]

Как сделать, чтобы исходные данные вводились из текстового файла, а результаты работы программы помещались в текстовый файл. ;)

[Amro]

Создаешь текстовый файл, заносишь туда данные при помощи той же генерации
читаешь эти данные, потом заносишь их в массив и всё, делаешь сортировку поиск как в моей проге, открываешь файл снова, удаляешь всё что там было и заносишь результат!!! Прогу доделывать лень .... если нуно могу завтра щас дел по горло!!!

[Гость_Вадим]

Amro, если будет не в лом, то доделай, пожалуйста

[Amro]

Держи Вадим
Разбирайся!!!
Прога создаёт файл генерирует элементы и заносит их туда Далее файл читается из него беруться элементы и т.д и в конце в этот же файл заносится результат!!!

Код

uses crt;
const
L=1;
R=25;
var
i, Key, h : integer;
Mas : array[L..R] of integer;
ged : text;
{...........................................................}
procedure Sort(Left,Right:integer);
var
i, j, w, x:integer;
begin
i:=Left; j:=Right;
x:=Mas[(Left+Right) div 2];
repeat
 while (Mas[i]<x) do
     inc(i);
     while (x<Mas[j]) do
     dec(j);
 if i<=j then
            begin
            W:=Mas[i]; Mas[i]:=Mas[j]; Mas[j]:=W; inc(i); dec(j);
            end
until i>j;
if Left<j then Sort(Left,j);
  if (i<Right) then Sort(i,Right)
end;
{.............................................................}
Procedure found(Left,Right:integer);
var
middle:integer;
begin
 if (Left<=Right) then
    begin
    Middle:=(Left+Right) div 2;
      if  Key < Mas[Middle] then found(Left,Middle-1);
        if Key > Mas[Middle] then found(Middle+1,Right);
          if  Key=Mas[Middle] then Key:=Middle;
    end
                         else Key:=0;
end;
{...........................................................}
begin
Key:=0; randomize;
clrscr;

assign(ged,'c:\ged.txt');
rewrite(ged);
for i:=L to R do
   begin
    h:=random(99);
    write(ged,h:3);
   end;
writeln(ged);
close(ged);

reset(ged);
for i:=L to R do
   begin
    read(ged,h); mas[i]:=h; write(mas[i]:3)
   end;
writeln;
close(ged);

Sort(L,R);

append(ged);
 writeln(ged,'Отсортированный массив ');
 writeln('Отсортированный массив ');
 for i:=L to R do
   begin
   write(Mas[i]:3); write(ged,Mas[i]:3);
   end;

 writeln(ged);
 writeln;
 write('Введите искомый элемент: ');
 read(Key);
 write(ged,'Элемент ',key);
close(ged);

writeln;

found(L,R);

append(ged);
 writeln(ged);
   if key<>0 then
             begin
              write('Его номер ',Key); write(ged,'Его номер ',Key);
             end
                else
             begin
             write('Такого элемента нету!!!');
             write(ged,'Такого элемента нету!!!');
             end;
close(ged);
readkey;
end.

Тока чёт много всего написал!!! по-моему даже лишнего

Сообщение отредактировано: Amro - 22.10.2004 21:12