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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 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++