метод равномерного и дихотомического поиска |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
метод равномерного и дихотомического поиска |
Catty |
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
Нигде не могу в сети найти алгоритмы этих методов, если у кого то есть алгоритмы киньте сюда пожалуйста или дайте ссылку! :flowers: :flowers:
-------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
klem4 |
Сообщение
#2
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата 2.3. Дихотомический (бинарный) поиск Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован. Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны. На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска. Запишем все сказанное в виде программы: l := 1; r := n; while (l<>r) do begin m := (l+r) div 2; if Key>A[m] then l := m+1 else r := m; end; if A[l]=Key then <элемент найден> else <элемент не найден>; Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)). Особого внимания здесь заслуживают операции добавления и удаления. Они должны сохранять массив отсортированным (лучше написать операции так, чтобы они не нарушали отсортированности массива, чем каждый раз сортировать его). Рассмотрим сначала добавление. Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива: i := n; while (i>=1)and(A[i]>Key) do begin A[i+1] := A[i]; {сдвигаем} Dec(i); end; A[i+1] := Key; Inc(n); Такая операция добавления имеет сложность T(n). Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным. -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
klem4 |
Сообщение
#3
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Такое впечатление что просто хотят запудрить народу мозг Метод дихотомического поиска - он же метод бинарного поиска, ну а метод равномерного поиска - это судя по всему :
i:=1;
while( i<=n and x[i] <> key ) do
inc(i);
if i>n then
writeln('Not found')
else writeln('pos=',i);
вполне равномерно ... :D Сообщение отредактировано: klem4 - -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Catty |
Сообщение
#4
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
я имела ввиду методы оптимизации:
нам задано функцию например y=sin(x) и нужно найти минимум этой функции на заданом интервале напримео от 0 до 8 при таком то шаге и с такой то точностью!! -------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
klem4 |
Сообщение
#5
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
конкретно то что ты написала можно сделать так :
uses crt;
var
left, right : single;
step, t, min : single;
function f( x : single) : single;
begin
f := sin(x);
end;
Begin
clrscr;
write('Left='); readln(left);
write('Right='); readln(right);
write('Step='); readln(step);
min := left;
t := min;
while (t<=right) do begin
writeln('t = ',t:2:2,' f( ',t:2:2,' )= ', f(t)
2);
if f(t) < f(min) then
min := t;
t := t + step;
end;
writeln;
writeln('MIN : ');
writeln('t = ', min:2:2, ' f(' ,min:2:2,' ) = ', f(min)
2);
readln;
end.
если использовать методы поиска, то надо просто забить значения ф-и в массив, в такомже цикле, ну а затем просто воспользоваться методом поиска. -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Catty |
Сообщение
#6
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
Это прямой перебор, а мне надо равномерный поиск! И дихотомичкский метод должен осуществляться с заданой функцией без масива и без сортировки!!
-------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
virt |
Сообщение
#7
|
Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
дихотомия ::
Код const _eps = 1E-7; ................... v := up - down; {8 - 0} x1 := v / 2; step := v / 4; whili (step >= _eps) and (abs(f(x1 - step) - f(x1 + step)) >= _eps) do begin if f(x1 - step) < f(x1 + step) then x1 := x1 - step else x1 := x1 + step; step := step / 2; end; оба метода выдают точные результаты при наличии строго одного минимума. При наличии двух и более на некоторых тестах неверные результаты. Сообщение отредактировано: virt - -------------------- |
volvo |
Сообщение
#8
|
Гость |
Catty, это все конечно хорошо, но функция Sin(x) - периодическая, а следовательно - может иметь на заданном интервале не один min/max, какой из них будем искать?
P.S. Virt, опередил :D Сообщение отредактировано: volvo - |
virt |
Сообщение
#9
|
Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
если я правильно догадываюсь то дихотомия это частный случай равномерного поиска.
ЗЫ volvo стараемся. Сообщение отредактировано: virt - -------------------- |
Catty |
Сообщение
#10
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
Volvo
нужно искать глобальный минимум, тоесть самый минимумистый минимум! :D -------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
Catty |
Сообщение
#11
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
по идее оба метода должны находить самый минимальный минимум!
и это можно пару слов к прогам а то что-то я не совсем понимаю почему именно так ... -------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
volvo |
Сообщение
#12
|
Гость |
Ну, а как быть, если (опять же берем для примера y = Sin(x)) у функции несколько одинаковых минимумов? У синуса минимальное значение = -1, и именно оно будет встречаться на заданном интервале неоднократно (хотя если X измеряется в радианах - то минимум будет всего один <_< )
|
Catty |
Сообщение
#13
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
Volvo забуть про sin(x) это я взяла для примера! но если даже минимумов несколько и они все равны -1, то программа должна выдать -1, тоесть это самый минимальный минимум, а сколько их это уже не важно!
-------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
virt |
Сообщение
#14
|
Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
1) берется середина отрезка в котором ищется минимум ,смотрится справа или слева от него меньшее значение ,где меньше там следующая середина. Смотрится справа или слева от середины опять ,... До тех пор пока не будет нужная точность (1E-7 до 7го знака после запятой)
-------------------- |
Catty |
Сообщение
#15
|
Бывалый Группа: Пользователи Сообщений: 239 Пол: Женский Реальное имя: Юлия Репутация: 3 |
спасибо рыбки! я уже во всем разобралась!
Сообщение отредактировано: Catty - -------------------- For every evil under the sun
There is a remedy or there is none If there is one - try to find it If there is none - never mind it! |
Текстовая версия | 13.01.2025 10:18 |