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

[Вадим]

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

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

[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 5:30