Двоичный поиск, чтобы найти n-й корень числа

Я попытался реализовать функцию с помощью бинарного поиска, чтобы решить следующее:

Реализуйте функцию root, которая вычисляет n-й корень числа. Функция принимает неотрицательное число x и целое положительное число n и возвращает положительный n-й корень x с ошибкой 0,001 (т. е. предположим, что действительный корень равен y, тогда ошибка: |y-root(x, n)| и должно удовлетворять условию |y-root(x,n)| ‹ 0,001). Ключ в том, чтобы найти корень без использования функции STL.

Мой код:

double binarysearch(double left,double right, double x, int n){
 while(left<right){
  double mid = left + (right-left)/2;
  double answer = pow(mid,n);
   if(fabs(answer - x ) <= DELTA)
    return mid;
  else if(answer > x )
      right = mid - DELTA;
  else 
     left = mid + DELTA;
 }
  return -1;
}

Это достигает состояния, когда лево>право, и возвращает -1.

Есть ли способ реализовать это с помощью бинарного поиска?


algorithm binary-search square-root
person nogeek001    schedule 27.02.2018    source источник
comment
Попробуйте отладить, например. печатая значения ваших переменных на каждом шаге.   -  person jkff    schedule 27.02.2018
comment
Обратите внимание, что бинарный поиск — неправильный термин. Вы не ищете конкретное значение в списке. Вы должны искать любой y в пределах DELTA от x^(-n), т. е. числа рядом с корнем y из y^n - x = 0, fabs(y - x^(-n) ) ‹ ДЕЛЬТА. Алгоритм для этого называется bisection. Если вы используете это в качестве условия поиска, вы получите много результатов и много примеров правильной реализации. Ответ @MattTimmermans дает тот же ответ для этой конкретной проблемы, но алгоритм деления пополам будет работать для нахождения корней x очень большого класса функций f (x) = 0.   -  person Gene    schedule 27.02.2018
comment
попробуйте/портируйте это Как получить квадратный корень для 32-битного ввода только за один такт? он использует двоичный поиск с высокой оптимизированный подход (умножение не требуется) существует множество других подобных методов, таких как как работает приближенный поиск другой ответ там описывает деление пополам которые использует этот код ... И еще есть методы аппроксимации. также см. Мощность путем возведения в квадрат отрицательных показателей для полного поиска в ячейке по сравнению с возведением в квадрат.   -  person Spektre    schedule 27.02.2018

Ответы (1)


arrow_upward
2
arrow_downward

Ваша функция не работает, потому что разница между (mid-DELTA)^n и mid^n обычно больше, чем DELTA.

Двоичный поиск с двойниками может быть сложным, и есть разные способы сделать это в зависимости от того, какой результат вы действительно хотите. В этом случае вас просят дать ответ с точностью до 0,001 от фактического корня. Необязательно, чтобы ваш ответ^n находился в пределах 0,001 от x.

Это предполагает такую ​​​​реализацию:

double binarysearch(double x, int n)
{
    double lo = 0.0;
    double hi = x;
    while(hi-lo >= 0.0019)
    {
        double test = lo+(hi-lo)*0.5;
        if (test == low || test == hi)
        {
           //I couldn't bear to leave this out.  Sometimes there are no
           //double values between lo and hi.  This will be pretty much
           //as close as we can get.  Break here to avoid an infinite loop
           break;
        }
        if (pow(test,n) < x)
        {
            lo = test;
        }
        else
        {
            hi = test;
        }
    }
    //cut the final range in half.  It's less than
    //0.0019 in size, so every number in the range, which includes
    //the root, is less than 0.001 away from this
    return lo+(hi-lo)*0.5;
}

Обратите внимание, что нет возможности вернуть «не найдено»

person Matt Timmermans    schedule 27.02.2018