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

Question

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

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

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

Teh codez:

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 

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

низкого низкого < = п < высокой высокой

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

Answer 2

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

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

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

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

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) двух штук после деления, есть способ определить, какая половина имеет решение, чтобы процесс можно было повторить только на одну половину.

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

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

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

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

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

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

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

4) Используйте двоичный поиск.

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

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

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

Хммм ... что произойдет, если y будет большим, чтобы быть квадратным корнем из x? Затем: x < y * y и: x/y < y, что означает, что x/y также слишком мал, чтобы быть квадратным корнем из x. Таким образом, мы знаем, что при y слишком большом x/y < квадратный корень x < y. Итак, давайте найдем новый y, скажем y1, между x/y и y в качестве нового тестового значения. Среднее значение x/y и y будет выполнено. y1 = (x/y0 + y0)/2 даст y1, который ближе к квадратному корню из x, чем y0, если y0 слишком велико.

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

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

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

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

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

В этом случае легко избежать арифметики, которая может привести к внутреннему переполнению с большими значениями x. Если мы создадим условие завершения, такое как y0 * y0 < x, мы рискуем переполнить, если x больше квадратного корня Integer.MAX_VALUE, так как y0 * y0, промежуточное значение, немедленно превысит максимальное значение int. Однако мы можем изменить условие завершения на y0 < x/y0. У нас все еще есть проблема с вычислениями: ((x/y0) + y0)/2) если x и y0 являются Integer.MAX_VALUE, так как он будет пытаться Integer.MAX_VALUE + 1. Однако мы всегда можем начинать со значения, меньшего х, что гарантировано> у. 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

Итерационный бинарное решение:

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; 
} 

Answer 6

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

mid = (high - low)/2; 

должен быть

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

Answer 7

Вы можете использовать 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 8

Вот рекурсивное решение в 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); 
     } 

    } 
}