Вещественнозначный бинарный поиск (реализация на языке Java)

Java   8 июля 2012  Автор статьи:  

Приведенный ниже код описывает функцию, которая находит решение уравнения f(x) = C на отрезке [l,r] с заданной точностью е:

public static double fixedAccuracyRealBinarySearch(double l, double r, double C, double e) {
while (r - l > e){
double med = (l+r)/2;
if (f(med) < C){ // это условие позволяет установить точно первое значение х, для которого // f(x) = C l = med; }else { r = med; } } //так как отрезок имеет длину не более е, то любое значение х, взятое из этого отрезка не будет отличаться //от точного решения уравнения f(x) = C не более, чем на е return (l+r)/2; }

В коде f(x) - это непрерывная неубывающая функция одного параметра, которая принимает в качестве значений тип данных double и возвращает значения такого же типа. В зависимости от целей, можно изменять тип входного и выходного параметра для этой функции, главное чтобы сама функция сохраняла непрерывность и неубываемость.

А эта функция вычисляет максимально точное решение уравнения f(x) = C:

public static double maxAccuracyRealBinarySearch(double l, double r, double C){
//так как тип данных double может содержать не более 2^64 значений, то после 100 делений
//отрезока [l,r] пополам можно с 99% точночтью утверждать, что l = r или они будут максимально близки
//друг к другу
for (int i = 0; i < 100; i++){ double med = (l+r)/2; if (f(med) < C){ // это условие позволяет установить точно первое значение х, для которого // f(x) = C l = med; }else { r = med; } } return (l+r)/2; }

В заключение отмечу, что данный метод решения уравнения f(x) = C в математике называется дихотомией.

Научиться программировать

  • на Delphi

  • на Java

  • на C++