Двоичный поиск для вычисления квадратного корня (Java)
Мне нужна помощь в написании программы, которая использует двоичный поиск для рекурсивного вычисления квадратного корня (округленного до ближайшего целого числа) входного неотрицательного целого числа.
Вот что у меня есть до сих пор:
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;
}
}
8 ответов:
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Низкий низкий высокий
Если вы понимаете этот код, написание рекурсивной версии должно быть тривиальным.
Вы можете использовать этот метод 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; } }Вы можете управлять своим собственным рекурсивным методом
По сути, идея заключается в том, что вы можете использовать двоичный поиск, чтобы приблизиться к ответу.
Например, предположим, что вам дано 14 в качестве входных данных. Тогда вы уверены, что квадратный корень из 14 находится между 0 и 14. Итак, 0 и 14 - это ваши текущие "границы". Вы делите пополам эти две конечные точки и получаете среднюю точку: 7. Затем вы пробуете 7 в качестве кандидата - если квадрат 7 больше 14, то у вас есть новая граница (0,7); в противном случае у вас была бы новая граница (7,14).
Ты продолжайте повторять это деление до тех пор, пока вы не окажетесь "достаточно близко" к ответу, например, у вас есть квадрат числа, который находится в пределах 14-0.01 и 14+0.01 - тогда вы объявите это ответом.
Хорошо, этого намека должно быть достаточно для HW. Не забудьте процитировать StackOverflow.
Я предполагаю, что это домашнее задание, поэтому я только дам подсказку.
Для проведения бинарного поиска необходимо выбрать точку, максимально приближенную к медиане возможных правильных значений. Таким образом, возникает вопрос, что является типичным медианным значением для квадратного корня, который либо постоянен, либо может быть вычислен с помощью умножения. Очевидно, что использование произвольной константы не будет работать для большинства входных данных, поэтому вам нужно прийти к своей догадке, умножив входные данные на константу.
Что же касается того, что константа C для умножения должна быть, что должно быть выбрано на основе того, какие значения вы ожидаете в качестве входных данных. Например, если вы ожидаете, что ваши входные данные будут около 250 000, то:
C * 250,000 ~= sqrt(250,000) C = sqrt(250,000) / 250,000 C = 500 / 250,000 C = 1 / 500
Я вижу в вашем вопросе две важные вычислительные концепции. Первый-бинарный поиск, второй-рекурсия. Поскольку это домашнее задание, вот вклад в понимание бинарного поиска, рекурсии и того, как думать о них.
Подумайте о двоичном поиске, как о разделении "пространства" решения пополам, сохранении половины решения и выполнении этого последовательно, чтобы процесс сходился к решению. Ключевые понятия для этого заключаются в том, что вам необходимо разработать решение "пространства", обладающего следующими свойствами:1) может быть разделен, как правило, пополам или, по крайней мере, на две части
2) из двух частей после разбиения существует способ определить, какая половина имеет решение, так что процесс может быть повторен только на одной половине. Рекурсия включает в себя функцию (метод в o-O speak), вызывающую саму себя. Рекурсия очень хорошо работает для процесса, который сходится к выводу. Он либо повторяется вечно или пока вы бежите из некоторых ресурс, как правило, память, и она фатально останавливается. Два ключевых понятия для рекурсии: 1) сходимость через некоторую инвариантность (подробнее об инвариантности ниже). 2) условие завершения (то, которое признает достаточную сходимость).Теперь, для вашей процедуры квадратного корня. Требования к этой процедуре следующие:
1) целочисленный ввод.
2) целочисленное приближение квадратного корня, которое дает целое число пола, наиболее близкое к фактическому квадратному корню.
3) Использовать рекурсия.
4) Используйте двоичный поиск.Для этого полезно знать некоторую математику о квадратных корнях. Полезны также понятия элементарного исчисления и аналитической геометрии. Давайте сделаем некоторые рассуждения.
У нас есть произвольное положительное целое число x. нам нужен его корень y. если мы выберем некоторое тестовое значение для y, мы сможем увидеть, является ли оно корнем x, если y * y = x. если y слишком велик, y * y > x. если y слишком мал, y * y
Вот некоторые математические рассуждения, чтобы помочь. Мы знаем, что x = y * y, где y-квадратный корень из x. это означает: y = x/y.
Хммм... что произойдет, если y слишком велик, чтобы быть квадратным корнем из x? Тогда: x
Сходится ли это? Ну, в математике, использующей положительные вещественные числа, среднее всегда будет выше значения, но приближается с каждой итерацией. Это удовлетворяет условию, что мы последовательно делим "пространство" решения на две части и знаем, какую из них сохранить. В в этом случае мы последовательно вычисляем новые значения ниже предыдущих и ниже которых все еще лежит ответ, что позволяет нам отбросить все значения выше нового. Мы останавливаемся, когда достигаем состояния, когда больше не существует новых значений выше ответа. Однако использование компьютеров приводит к двоичным приближениям действительных чисел. С целыми числами происходит усечение в делении. Это может оказать положительное или отрицательное влияние на конвергенцию. Кроме того, ваш ответ должен быть самым большим целым числом меньше чем или равно квадратному корню. Разумно взглянуть на тип конвергенции, которую мы получим.
Из-за поворота целочисленного деления y1 = (x/y0 + y0)/2 будет сходиться до тех пор, пока последовательные итерации не достигнут целого корня или значения пола Для (т. е. самого большого целого меньше) корня. Это идеальный вариант. Если мы начнем с предложенного значения для корня, которое должно быть больше, чем сам корень, скажем x, первое значение для yn, где yn * yn
Простой ответ состоит в том, что, когда мы начинаем с y0 > y, первый новый yn, который меньше или равен y, то y - yn Здесь приведены основные итерационные и рекурсивные решения. Решения не включают в себя функции безопасности, чтобы гарантировать, что отрицательные значения не вводятся для x. одна из главных проблем заключается в том, чтобы избежать деления на ноль в случае, если кто-то хочет найти квадратный корень из 0. Поскольку это тривиальный ответ, как рекурсивный, так и итерационный методы возвращают 0 до деления на ноль. Как рекурсивные, так и итерационные решения работают с тривиальными случаями нахождения квадратных корней 0 и 1.
Есть еще один анализ, который всегда приходится делать с помощью int и long арифметики в Java. Основной проблемой является переполнение целых чисел, так как Java ничего не делает с переполнением int или long. Переполнение приводит к двойки-дополняют значения (посмотрите, что в другом месте), которые могут привести к поддельным результатам, и Java не бросает исключения с int или long переполнением.
В этом случае легко избежать арифметики, которая может привести к внутреннему переполнению с большими значениями x. Если мы создадим условие завершения, такое как y0 * y0 y. x / 2 работает для всех значений x > 1. Поскольку квадратный корень из x, где x равно 0 или 1, является просто x, мы можем легко проверить эти значения и просто вернуть правильное и тривиальное значение. Вы можете построить код, чтобы не используйте значения Integer.МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ. То же самое может быть применено, если мы используем 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
Вот рекурсивное решение в 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); } } }
Итерационное бинарное решение:
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; }