Рекурсии |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Рекурсии |
Вадим |
Сообщение
#1
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Помогите написать программу.
Разработать рекурсивную процедуру двоичного поиска элемента массива, равного данному числу. Сообщение отредактировано: Вадим - |
Amro |
Сообщение
#2
|
Пионер Группа: Пользователи Сообщений: 146 Пол: Мужской Репутация: 2 |
А массив уже упорядочен чтоль, или его ещё сортировать нуно?
-------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
Вадим |
Сообщение
#3
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Условие точное, но скорее всего массив надо сортировать
|
godd |
Сообщение
#4
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
что такое двоичный поиск? поиск двоичного числа? или че?
вот поиск обычного: на С++ (на Pascale с указателями не работал и функций не писал - не приходилось) Код //Шаблон - при объявлении функции IndexOfArray просто определяется тип VT и подставляется где надо P.S. Сортировать ничего не надо - просто перемещаем указатель на следующий элемент массива//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.P.S. В функцию передавай 3аргумента, i - определен по умолчанию, если передашь его - собьешь счетчик (ну разве что 0 передай и фсе), max_i - последний элемент массива Сообщение отредактировано: godd - |
Amro |
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 146 Пол: Мужской Репутация: 2 |
Нет godd это не поиск двоичного числа это поиск элемета в упорядоченном массиве........короче берём массив и искомый элемент далее делим массив пополам и смотрим в какой части находится искомый элемент, далее берём эту часть и делим её пополам и.д пока не найдём этот элемент....... Таким образом скорость поиска увеличится на много порядков.
Вадим В инете ведь полно информации по двоичному поиску, когда-то я сам искал этот поиск......правда через рекурсию не видал, но там вроде тоже ни чего сложного нету, в общем попробуем реализовать...... -------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
fms |
Сообщение
#6
|
Бывалый Группа: Пользователи Сообщений: 195 Пол: Женский Репутация: 0 |
двоичный т.е. бинарный?
со строками.. ну можно ведь и для чесел переделать.. Код 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 |
Сообщение
#7
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
скорость поиска увеличиться? ну разве что в отсортированном массиве, а ведь его еще надо будет отсортировывать - так что в итоге во времени проигрышь. разве что сортировка массива подразумевается условием самой задачи.
я тут кое-чо тоже написал вот процедура: Код procedure IndexOfArray(niz,verh,iskomoe:byte) Должно работать, сам не проверял. Предполагается что массив уже отсортированный, первоначально verh:=конец_массива, niz:=начало_массива, Iskomoe:=Искомое. Предполагается что array[x..n] of 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 P.S. Вадим, переделай эту фигню в функцию P.P.S Я на C++ переехал, про функции - если понадобяться, то потом почитаю. Пока не надо )) => сам делай __________ вначале по привычке trunc написал. надо - round [округление по правилам математики] Сообщение отредактировано: godd - |
godd |
Сообщение
#8
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
посчет времени - рекурсия это вообще дело нехорошее.
она хороша только тем что упрощает текст проги, а минус - медленность работы, вывод - лучше писать обычные нерекурсивные функции забив все это дело по циклам, а рекурсию использовать тока когда это явно указано в задаче. |
Amro |
Сообщение
#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 - -------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
godd |
Сообщение
#10
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
недоглядел в тексте Amro. Не то написал. Удалить пост незя.
Сообщение отредактировано: godd - |
godd |
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
Amro
по поводу рекурсии - это я прочитал где-то. |
godd |
Сообщение
#12
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
Недоглядел я. Ему ж процедура нужна была. А я вроде как функция прочитал.
|
Amro |
Сообщение
#13
|
Пионер Группа: Пользователи Сообщений: 146 Пол: Мужской Репутация: 2 |
Ты прав надо сравнивать только с крайним элементом полововины!!! У меня в проге это и реализованно.......просто в моих начальных словах я этого не досказал впопыхах, но самое главное что суть сего метода была мной сформулированна...
а она закл в делении массива надвое....... :yes: -------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
Amro |
Сообщение
#14
|
Пионер Группа: Пользователи Сообщений: 146 Пол: Мужской Репутация: 2 |
Во во я также сначала функцией пытался сделать, тоже не прочитал внимательно, целый час долбился с функцией и переполнением стека, а потом решил прочитать условие заново..
-------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
godd |
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 40 Пол: Мужской Репутация: 0 |
Цитата генерировать элементы массива чтобы одинаковых не было??? мона. вначале проги randomize ставишь, а элементы приравниваешь к random(z), где z - положительное число, верхний предел значений - z-1, если надо отрицательное включать, или числа с плавающей точкой воспроизводить - измываешся над random(z): random(z)-trunc(z*0.5), random(z)/random(z*0.3), ну и далее в этом духе |
Guest |
Сообщение
#16
|
Гость |
Как сделать, чтобы исходные данные вводились из текстового файла, а результаты работы программы помещались в текстовый файл. ;)
|
Amro |
Сообщение
#17
|
Пионер Группа: Пользователи Сообщений: 146 Пол: Мужской Репутация: 2 |
Создаешь текстовый файл, заносишь туда данные при помощи той же генерации
читаешь эти данные, потом заносишь их в массив и всё, делаешь сортировку поиск как в моей проге, открываешь файл снова, удаляешь всё что там было и заносишь результат!!! Прогу доделывать лень .... если нуно могу завтра щас дел по горло!!! -------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
Гость_Вадим |
Сообщение
#18
|
Гость |
Amro, если будет не в лом, то доделай, пожалуйста
|
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. Тока чёт много всего написал!!! по-моему даже лишнего Сообщение отредактировано: Amro - -------------------- Закон иудеев: Семь раз отмерь, один отрежь.
Закон экономии: Семь раз отмерь, семь раз отрежь. Закон программиста: Семь раз отрежь, ошибся, отмерь. |
Текстовая версия | 21.12.2024 23:10 |