77
правок
Изменения
Нет описания правки
== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
== Выбор границы ==
Для начала найдем правую границу. Выберем произвольную положительную точку (например 1). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку. Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.
== Способы закончить поиск ==
# Итеративный способ. В этом способе выполниться только конечное число число итераций.
#* Плюсом этого способа является фиксированная погрешность.
== Псевдокод ==
double find_left(double c) {
double x = -1;
while (f(x) > c) {
x *= 2;
}
return x;
}
double find_right(double c) {
double x = 1;
while (f(x) < c) {
x *= 2;
}
return x;
}
double bin_search(double c) {
double left = find_left();
double right = find_right();
while (left < right - eps) { //Здесь можно поставить другое условие выхода
double m = (left + right) / 2;
if (f(m) < c)
l = m;
else
r = m;
}
return l;
}
