平方根（Java）を計算するためのバイナリ検索
https://stackoverflow.com/questions/3766020
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
バイナリ検索を使用して、入力の非陰性整数の平方根（最も近い整数に丸められた）を再帰的に計算するプログラムを作成するのに役立ちます。
これは私がこれまでに持っているものです：
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;
}
}
バイナリ検索を使用して平方根を計算しなければならないという事実は、私を混乱させている部分です。誰かがこれを行う方法について何か提案を持っているなら、それは大歓迎です。ありがとうございました
解決
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
それを理解するには、ループの不変、つまり：
低いlow <= n <high高い
このコードを理解している場合、再帰バージョンを書くことは些細なことです。
他のヒント
この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は現在の「境界」です。これらの2つのエンドポイントを二等分して、中間点を取得します。7。次に、候補として7を試みます - 7の正方形が14を超える場合、新しい境界（0,7）があります。それ以外の場合は、新しい境界（7,14）があります。
答えに「十分に近い」ようになるまで、この二分を繰り返し続けます。たとえば、その数字は14-0.01および14+0.01以内にあります。その後、答えとしてそれを宣言します。
OK、そのヒントはHWにとって十分であるはずです。 Stackoverflowを引用することを忘れないでください。
私はこれが宿題だと思っているので、ヒントを与えるだけです。
バイナリ検索を実施するには、可能な正しい値の中央値をできるだけ近いポイントを選択します。したがって、問題は、平方根の典型的な中央値の値であるものになります。これは一定か、乗算によって計算できます。明らかに、任意の定数を使用しても、ほとんどの入力では機能しないため、入力に定数を掛けることで推測に到達する必要があります。
その定数cが何をするべきかについては、それは入力として期待される値に基づいて選択する必要があります。たとえば、入力が約250,000になると予想される場合は、
C * 250,000 ~= sqrt(250,000)
C = sqrt(250,000) / 250,000
C = 500 / 250,000
C = 1 / 500
私はあなたの質問に2つの重要なコンピューティングの概念を見ています。 1つ目はバイナリ検索で、2つ目は再帰です。これは宿題であるため、バイナリ検索、再帰、およびそれらについて考える方法を理解するための貢献があります。
バイナリ検索は、ソリューションの「スペース」を半分に分割すると考えて、解決策の半分を維持し、プロセスがソリューションに収束するようにそれを連続して行います。これを行うための重要な概念は、次のプロパティを持つソリューション「スペース」を設計する必要があることです。
1）通常は半分または少なくとも2つのピースで細分化できます
2）区画後の2つの部分のうち、どの半分が解決策を持っているかを判断して、プロセスを半分だけで繰り返すことができるようにする方法があります。
再帰には、それ自体を呼び出す関数（OO話す方法）が含まれます。再帰は、結論に収束するプロセスに非常に適しています。それは永遠に再発するか、あなたがいくつかのリソース、通常は記憶を使い果たすまで再び繰り返され、致命的に停止します。再帰の2つの重要な概念は次のとおりです。
1）いくつかの不変性による収束（以下の不変性の詳細）。
2）終了条件（十分な収束を認識する条件）。
さて、あなたの平方根のルーチンのために。ルーチンの要件は次のとおりです。
1）整数入力。
2）実際の平方根に最も近い床整数を与える整数平方根近似。
3）再帰を使用します。
4）バイナリ検索を使用します。
これのための平方根についての数学を知るのに役立ちます。基本的な計算と分析幾何学の概念も役立ちます。何らかの推論をしましょう。
任意の正の整数xがあります。そのルートyが必要です。 yのテスト値を選択すると、y * y = xの場合、それがxのルートであるかどうかを確認できます。 yが大きすぎる場合、y * y> x。 yが小さすぎる場合、y * y <x。また、0 <= root <= xであり、0と1の平方根が些細なゼロと1であることもわかっています。それも説明します。
ここに助けてくれる数学的な推論があります。 x = y * yここで、yはxの平方根であることがわかります。つまり、y = x/y。
うーん... yがxの平方根になるとyが大きい場合はどうなりますか？次に：x <y * yおよび：x/y <yは、x/yもxの平方根になるには小さすぎることを意味します。したがって、yが大きすぎると、x/y <x <yの正方形のルートがあることがわかっています。したがって、新しいテスト値として、x/yとyの間の新しいy、たとえばy1を見つけましょう。 x/yとyの平均は行います。 y1 =（x/y0 + y0）/2は、y0が大きすぎる場合、y0よりもxの平方根に近いy1を与えます。
これは収束しますか？まあ、正の実数を使用した数学では、平均は常に値を上回りますが、それぞれの反復が近づきます。これは、ソリューション「スペース」を2つの部分に連続的に分割し、どれが保持するかを知っているという条件を満たします。この場合、以前の値以下の新しい値以下の新しい値を連続して計算します。この値はまだあります。答えの上に新しい値が存在しない状態に達すると停止します。ただし、コンピューターを使用すると、実数のバイナリ近似が生じます。整数では、分裂に切り捨てられます。これは、収束に有益または悪に影響する可能性があります。さらに、あなたの答えは、平方根以下の最大の整数であると考えられています。私たちが得るような収束を見てみるのが賢明です。
整数分割のターンカチオンのため、y1 =（x/y0 + y0）/2は、整数のルートまたはルートのフロアルート（すなわち最大の整数未満）に到達するまで収束します。これは理想的です。ルートよりも大きくなければならないルートの提案された値から始める場合、X自体はX自体、Yn * yn <= xが望ましい結果です。
簡単な答えは、y0> yから始めると、y以下の最初の新しいyn、y -yn <1は、ynが私たちが探している床値であるということです。そして、必要な答えの条件を正確に満たす終了条件があります。
以下は、基本的な反復的および再帰的なソリューションを紹介します。ソリューションは、負の値がxの入力でないことを確認するための安全機能を蓄積しません。 1つの主要な懸念は、誰かが0の平方根を見つけたい場合にゼロで割らないようにすることです。それは些細な答えであるため、再帰的な方法と反復方法の両方がゼロで分割される前に0を返すことができます。再帰的なソリューションと反復溶液の両方は、些細なケースと連携して、0以下の正方形の根を見つけるために機能します。
JavaのINTおよびLONG ARITHMETICで常に行う必要がある別の分析があります。 JavaはIntまたは長いオーバーフローについて何もしていないため、主な懸念は整数のオーバーフローです。オーバーフロー結果は、偽物の結果につながる可能性のある2つの補完値（他の場所を調べてください）で結果をもたらし、JavaはINTまたは長いオーバーフローで例外を投げません。
この場合、xの値が大きい内部オーバーフローをもたらす可能性のある算術を回避するのは簡単です。 y0 * y0 <xなどの終端条件を作成する場合、xがinteger.max_valueの平方根よりも大きい場合にxがオーバーフローを危険にさらします。ただし、終了条件をy0 <x / y0に再配置できます。計算にはまだ問題があります：（（x / y0） + y0） / 2）xとy0がinteger.max_valueである場合、integer.max_value + 1を試みるので、いつでも値が少ない値から始めることができます。 x> yが保証されています。 x / 2はx> 1のすべての値に対して機能します。xの平方根xは0または1のいずれかが単にxであるため、それらの値を簡単にテストし、正しい値と些細な値を単純に返すことができます。コードを構築して、値<0または値> integer.max_valueを使用して防止できます。 INTの代わりにLONGを使用する場合、同じことを適用できます。現実の世界のコンピューティングへようこそ！
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;
}
EDSTソリューションは良いですが、11行目には間違いがあります。
mid = (high - low) / 2;
あるべきです
mid = low + (high - low) / 2;
