Версия для печати темы
Форум «Всё о Паскале» _ Задачи _ Рекурсии
Автор: Вадим 11.10.2004 1:09
Помогите написать программу.
Разработать рекурсивную процедуру двоичного поиска элемента массива, равного данному числу.
Автор: Amro 11.10.2004 1:31
А массив уже упорядочен чтоль, или его ещё сортировать нуно?
Автор: Вадим 11.10.2004 1:43
Условие точное, но скорее всего массив надо сортировать
Автор: godd 11.10.2004 2:32
что такое двоичный поиск? поиск двоичного числа? или че?
вот поиск обычного:
на С++ (на 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 - последний элемент массива
Автор: Amro 11.10.2004 3:27
Нет godd это не поиск двоичного числа это поиск элемета в упорядоченном массиве........короче берём массив и искомый элемент далее делим массив пополам и смотрим в какой части находится искомый элемент, далее берём эту часть и делим её пополам и.д пока не найдём этот элемент....... Таким образом скорость поиска увеличится на много порядков.
Вадим В инете ведь полно информации по двоичному поиску, когда-то я сам искал этот поиск......правда через рекурсию не видал, но там вроде тоже ни чего сложного нету, в общем попробуем реализовать......
Автор: fms 11.10.2004 4:07
двоичный т.е. бинарный?
со строками.. ну можно ведь и для чесел переделать..
Код
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 11.10.2004 4:17
скорость поиска увеличиться? ну разве что в отсортированном массиве, а ведь его еще надо будет отсортировывать - так что в итоге во времени проигрышь. разве что сортировка массива подразумевается условием самой задачи.
я тут кое-чо тоже написал
вот процедура:
Код
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 5:18
посчет времени - рекурсия это вообще дело нехорошее.
она хороша только тем что упрощает текст проги, а минус - медленность работы, вывод - лучше писать обычные нерекурсивные функции забив все это дело по циклам, а рекурсию использовать тока когда это явно указано в задаче.
Автор: Amro 11.10.2004 5:27
Я в общем тоже времени не терял, написал тут одну басягу, долго я её долбил, жалко что у рекурсии есть предел, я с этой проблемой переполнения стека целый час провозился, зато результат на лицо......
Код
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 на счёт времени рекурсии - эт ты верно подметил.................................
Автор: godd 11.10.2004 5:35
недоглядел в тексте Amro. Не то написал. Удалить пост незя.
Автор: godd 11.10.2004 5:36
Amro
по поводу рекурсии - это я прочитал где-то.
Автор: godd 11.10.2004 5:46
Недоглядел я. Ему ж процедура нужна была. А я вроде как функция прочитал.
Автор: Amro 11.10.2004 5:49
Ты прав надо сравнивать только с крайним элементом полововины!!! У меня в проге это и реализованно.......просто в моих начальных словах я этого не досказал впопыхах, но самое главное что суть сего метода была мной сформулированна...
а она закл в делении массива надвое....... :yes:
Автор: Amro 11.10.2004 5:52
Во во я также сначала функцией пытался сделать, тоже не прочитал внимательно, целый час долбился с функцией и переполнением стека, а потом решил прочитать условие заново..
Автор: godd 11.10.2004 13:14
Цитата
генерировать элементы массива чтобы одинаковых не было???
мона. вначале проги randomize ставишь, а элементы приравниваешь к random(z), где z - положительное число, верхний предел значений - z-1, если надо отрицательное включать, или числа с плавающей точкой воспроизводить - измываешся над random(z): random(z)-trunc(z*0.5), random(z)/random(z*0.3), ну и далее в этом духе
Автор: Guest 22.10.2004 0:54
Как сделать, чтобы исходные данные вводились из текстового файла, а результаты работы программы помещались в текстовый файл. ;)
Автор: Amro 22.10.2004 1:23
Создаешь текстовый файл, заносишь туда данные при помощи той же генерации
читаешь эти данные, потом заносишь их в массив и всё, делаешь сортировку поиск как в моей проге, открываешь файл снова, удаляешь всё что там было и заносишь результат!!! Прогу доделывать лень .... если нуно могу завтра щас дел по горло!!!
Автор: Гость_Вадим 22.10.2004 1:34
Amro, если будет не в лом, то доделай, пожалуйста
Автор: Amro 23.10.2004 1:03
Держи Вадим
Разбирайся!!!
Прога создаёт файл генерирует элементы и заносит их туда Далее файл читается из него беруться элементы и т.д и в конце в этот же файл заносится результат!!!
Код
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.
Тока чёт много всего написал!!! по-моему даже лишнего