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

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

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

 
 Ответить  Открыть новую тему 
> Рекурсии
сообщение
Сообщение #1





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

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


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

Сообщение отредактировано: Вадим -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





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

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


Условие точное, но скорее всего массив надо сортировать
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


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

на С++ (на 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


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

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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

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


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


Код
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.



--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


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

я тут кое-чо тоже написал
вот процедура:
Код
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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


посчет времени - рекурсия это вообще дело нехорошее.
она хороша только тем что упрощает текст проги, а минус - медленность работы, вывод - лучше писать обычные нерекурсивные функции забив все это дело по циклам, а рекурсию использовать тока когда это явно указано в задаче.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


Я в общем тоже времени не терял, написал тут одну басягу, долго я её долбил, жалко что у рекурсии есть предел, я с этой проблемой переполнения стека целый час провозился, зато результат на лицо......
Код
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 -


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


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

Сообщение отредактировано: godd -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


Amro
по поводу рекурсии - это я прочитал где-то.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


Недоглядел я. Ему ж процедура нужна была. А я вроде как функция прочитал.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 40
Пол: Мужской

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


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

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


Гость






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


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гость






Amro, если будет не в лом, то доделай, пожалуйста
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

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


Держи Вадим
Разбирайся!!!
Прога создаёт файл генерирует элементы и заносит их туда Далее файл читается из него беруться элементы и т.д и в конце в этот же файл заносится результат!!!
Код
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.

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

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


--------------------
Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь.
Закон программиста: Семь раз отрежь, ошибся, отмерь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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