Бинарный поиск для вычисления квадратного корня (Java)

Question

Мне нужна помощь в написании программы, использующей бинарный поиск для рекурсивного вычисления квадратного корня (с округлением до ближайшего целого числа) входного неотрицательного целого числа.

Это то, что я до сих пор:1003 *

import java.util.Scanner;

public class Sqrt {

  public static void main(String[] args) {

    Scanner console = new Scanner(System.in);

    System.out.print("Enter A Valid Integer: ");

    int value = console.nextInt();

    calculateSquareRoot(value);

  }

    public static int calculateSquareRoot(int value) {
      while (value > 0) {
      double sqrt = (int) Math.sqrt(value);
      System.out.println(sqrt);
    }
    return -1;
    }
}

Тот факт, что он должен использовать бинарный поиск для вычисления квадратного корня, является частью, которая смущает меня.Если у кого-то есть какие-либо предложения о том, как это сделать, это будет с благодарностью.Спасибо

Answer 1

Код:

def sqrt(n):
  low = 0
  high = n+1
  while high-low > 1:
    mid = (low+high) / 2
    if mid*mid <= n:
      low = mid
    else:
      high = mid
  return low

Чтобы понять это, просто подумайте об инварианте цикла, а именно:

низкий низкий <= n <высокий </em>high

Если вы понимаете этот код, написание рекурсивной версии должно быть тривиальным.

Answer 2

Вы можете использовать этот метод Java (итеративный)

public class Solution {
    // basic idea is using binary search
    public int sqrt(int x) {
        if(x == 0 || x == 1) {
            return x;
        }
        int start = 1, end = x / 2;
        while(start <= end) {
            int mid = start + (end - start) / 2;
            if(mid == x / mid) {
                return mid;
            }
            if(mid < x / mid) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return start - 1;
    }
}

Вы можете использовать свой собственный рекурсивный метод

Answer 3

По сути, идея заключается в том, что вы можете использовать бинарный поиск, чтобы приблизиться к ответу.

Например, скажем, вам дают 14 в качестве ввода. Тогда вы уверены, что квадратный корень из 14 находится между 0 и 14. Итак, 0 и 14 - ваши текущие «границы». Вы делите пополам эти две конечные точки и получаете среднюю точку: 7. Затем вы пробуете 7 в качестве кандидата - если квадрат 7 больше 14, то у вас есть новая граница (0,7); в противном случае у вас будет новая граница (7,14).

Вы продолжаете повторять эту бисекцию до тех пор, пока не будете «достаточно близки» к ответу, например, у вас есть числовой квадрат, который находится в пределах 14–0,01 и 14 + 0,01 - тогда вы объявляете это как ответ.

Ладно, такой подсказки должно быть достаточно для HW. Не забывайте цитировать StackOverflow.

Answer 4

Я вижу две важные вычислительные концепции в вашем вопросе.Первый - бинарный поиск, второй - рекурсия.Так как это домашнее задание, вот вклад в понимание бинарного поиска, рекурсии и того, как думать о них.

Думайте о бинарном поиске как о делении «пространства» решения пополам, сохраняя половину решения, и делайте это последовательно, чтобы процесс сходился к решению.Ключевыми концепциями для этого являются то, что вам необходимо разработать «пространство» решения, которое имеет следующие свойства:

1) может быть подразделено, обычно пополам или как минимум двумя частями

2) из двух частей после подразделения есть способ определить, какая половина имеет решение, так что процесс может быть повторен только на одной половине.

Рекурсия включает в себя функцию (метод на языке OO), вызывающую себя.Рекурсия работает очень хорошо для процесса, который сходится к заключению.Он либо повторяется навсегда, либо до тех пор, пока у вас не закончатся какие-то ресурсы, обычно память, и он смертельно остановится.Два ключевых понятия для рекурсии:

1) сходимость через некоторую инвариантность (подробнее об инвариантности ниже).

2) условие завершения (то, которое распознает достаточную сходимость).

Теперь, для вашей рутины квадратного корня.Требования к процедуре:

1) Целочисленный ввод.

2) Приближение целочисленного квадратного корня, которое дает целочисленное значение пола, наиболее близкое к фактическому квадратному корню.

3) Использовать рекурсию.

4) Использовать бинарный поиск.

Для этого полезно знать некоторую математику о квадратных корнях.Элементарные исчисления и понятия аналитической геометрии также полезны.Давайте рассмотрим немного.

У нас есть произвольное положительное целое число x.Мы хотим, чтобы его корень у.Если мы выберем некоторое тестовое значение для y, мы увидим, является ли оно корнем x, если y * y = x.Если у слишком большой, у * у> х.если у слишком мало, у * у <х.Мы также знаем, что 0 <= root <= x и что квадратные корни из 0 и 1 тривиально равны нулю и 1. Так как мы ищем наибольшее целое число, где y * y <= x (то есть значение пола), мы будем иметьучитывать это тоже.</p>

Вот некоторые математические соображения, чтобы помочь.Мы знаем, что x = y * y, где y - квадратный корень из x.Это означает: у = х / у.

Хммм ... что произойдет, если у слишком большой, чтобы быть квадратным корнем из х?Тогда: x

Это сходится?Ну, в математике, использующей положительные действительные числа, среднее значение всегда будет выше значения, но становится ближе к каждой итерации.Это удовлетворяет условию, что мы последовательно разделяем «пространство» решения на две части и знаем, какую из двух оставить.В этом случае мы последовательно вычисляем новые значения ниже предыдущих и ниже которых ответ все еще лежит, что позволяет нам отбросить все значения выше нового.Мы останавливаемся, когда достигаем условия, при котором больше нет новых значений над ответом.Использование компьютеров, однако, приводит к двоичным приближениям действительных чисел.С целыми числами происходит усечение в делении.Это может повлиять на конвергенцию как положительно, так и отрицательно.Кроме того, ваш ответ должен быть самым большим целым числом, меньшим или равным квадратному корню.Целесообразно взглянуть на то, какое сближение мы получим.

Из-за поворота с целочисленным делением y1 = (x / y0 + y0) / 2 будет сходиться до тех пор, пока последовательные итерации не достигнут целочисленного корня или минимального значения (то есть наибольшее целое число меньше) корня.Это идеально.Если мы начнем с предложенного значения для корня, которое должно быть больше, чем сам корень, скажем, самого x, первое значение для yn, где yn * yn <= x, является желаемым результатом.</p>

Простой ответ состоит в том, что, когда мы начинаем с y0> y, первый новый yn, который меньше или равен y, тогда y - yn <1. То есть, yn теперь является минимальным значением, для которого мы 'Мы искали, и теперь у нас есть условие завершения, которое точно удовлетворяет условиям для требуемого ответа. </p>

Вот основные итерационные и рекурсивные решения.Решения не включают в себя функции безопасности, чтобы гарантировать, что отрицательные значения не вводятся для х.Одна из основных проблем состоит в том, чтобы избежать деления на ноль в случае, если кто-то хочет найти квадратный корень из 0. Поскольку это тривиальный ответ, и рекурсивный, и итерационный методы возвращают 0 до того, как может произойти деление на ноль.Как рекурсивное, так и итеративное решения работают с тривиальными случаями нахождения квадратных корней от 0 до 1.

Существует еще один анализ, который всегда должен выполняться с помощью int и long arithmetic в Java.Основная проблема - целочисленное переполнение, поскольку Java ничего не делает с int или long переполнением.Переполнение приводит к значениям, дополняющим два (смотрите это в другом месте), которые могут привести к фиктивным результатам, и Java не генерирует исключения с int или long переполнением.

В этом случае легко избежать арифметики, которая может привести к внутреннему переполнению с большими значениями x.Если мы создаем условие завершения, такое как y0 * y0 у.x / 2 работает для всех значений x> 1. Поскольку корень квадратный из x, где x равен 0 или 1, является просто x, мы можем легко проверить эти значения и просто вернуть правильное и тривиальное значение.Вы можете создать код для предотвращения использования значений <0 или значений> Integer.MAX_VALUE.То же самое можно применить, если мы используем long вместо int.Добро пожаловать в вычисления в реальном мире!

public static int intSqRootRecursive (int x) {
    // square roots of 0 and 1 are trivial and x / 2 for
    // the y0 parameter will cause a divide-by-zero exception
    if (x == 0 || x == 1) {
        return x;
    }
    // starting with x / 2 avoids overflow issues
    return intSqRootRecursive (x, x / 2);
} // end intSqRootRecursive

private static int intSqRootRecursive(int x, int y0) {
    // square roots of 0 and 1 are trivial
    // y0 == 0 will cause a divide-by-zero exception
    if (x == 0 || x == 1) {
        return x;
    } // end if
    if (y0 > x / y0) {
        int y1 = ((x / y0) + y0) / 2;
        return intSqRootRecursive(x, y1);
    } else {
        return y0;
    } // end if...else
} // end intSqRootRecursive

public static int intSqRootIterative(int x) {
    // square roots of 0 and 1 are trivial and
    // y == 0 will cause a divide-by-zero exception
    if (x == 0 || x == 1) {
        return x;
    } // end if
    int y;
    // starting with y = x / 2 avoids overflow issues
    for (y = x / 2; y > x / y; y = ((x / y) + y) / 2);
    return y;
} // end intSqRootIterative

Вы можете протестировать рекурсивное решение, чтобы выяснить, сколько экземпляров будет получено в стеке кадров, но вы увидите, что оно сходится очень быстро.Интересно видеть, что итеративное решение намного меньше и быстрее рекурсивного, что часто бывает не так, и именно поэтому рекурсия используется там, где можно предсказать, что стековых ресурсов достаточно для глубины рекурсии.

Answer 5

Я предполагаю, что это домашнее задание, поэтому я лишь дам подсказку.

Чтобы выполнить бинарный поиск, вы выбираете точку, максимально приближенную к медиане возможных правильных значений.Таким образом, возникает вопрос, что является типичным медианным значением для квадратного корня, которое является либо постоянным, либо может быть вычислено с помощью умножения.Очевидно, что использование произвольной константы не будет работать для большинства входных данных, поэтому вам нужно прийти к своему предположению, умножив входное значение на постоянную.в зависимости от того, какие значения вы ожидаете в качестве входных данных.Например, если вы ожидаете, что ваши входные данные составят около 250 000, то:

C * 250,000 ~= sqrt(250,000)
C = sqrt(250,000) / 250,000
C = 500 / 250,000
C = 1 / 500

Answer 6

Вот рекурсивное решение в Java с использованием бинарного поиска:

public class FindSquareRoot {

    public static void main(String[] args) {
        int inputNumber = 50;
        System.out.println(findSquareRoot(1, inputNumber, inputNumber));
    }

    public static int findSquareRoot(int left, int right, int inputNumber){

        // base condition
        if (inputNumber ==0 || inputNumber == 1){
            return inputNumber;
        }

        int mid = (left + right)/2;

        // if square of mid value is less or equal to input value and 
        // square of mid+1 is less than input value. We found the answer. 
        if (mid*mid <= inputNumber && (mid+1)*(mid+1) > inputNumber){
            return mid;
        }

        // if input number is greater than square of mid, we need 
        // to find in right hand side of mid else in left hand side.
        if (mid*mid < inputNumber){
            return findSquareRoot(mid+1, right, inputNumber);
        }
        else{
            return findSquareRoot(left, mid-1, inputNumber);
        }

    }
}

Answer 7

edst решение хорошо, но в строке 11 есть ошибка:

mid = (high - low) / 2;

должно быть

mid = low + (high - low) / 2;

Answer 8

Итеративное двоичное решение:

public static double sqrt(int n) {

    double low = 0;
    double high = n;
    double mid = (high - low) / 2;

    while (Math.abs((mid * mid) - n) > 0.000000000001) {
        if ((mid * mid) > n) {

            high = mid;
            mid = (high - low) / 2;

        } else{

            low = mid;
            mid = mid + ((high - low) / 2);

        }
    }
    return mid;
}