あなたの質問には、コンピューティングの重要な概念が 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 の平方根は自明に 0 と 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 であることがわかります。では、新しいテスト値として x/y と y の間の新しい y、たとえば y1 を見つけてみましょう。x/y と y の平均で十分です。y1 = (x/y0 + y0)/2 は、y0 が大きすぎる場合、y0 よりも x の平方根に近い y1 を返します。
これは収束しますか？まあ、正の実数を使用する数学では、平均は常に値を上回りますが、反復ごとに近づきます。これは、解「空間」を連続して 2 つの部分に分割し、どちらを保持するかを知るという条件を満たします。この場合、以前の値よりも下に新しい値を計算し、それより下にはまだ答えがあるため、新しい値よりも上のすべての値を破棄できます。答えを超える新しい値が存在しない状態に到達すると停止します。ただし、コンピューターを使用すると、実数のバイナリ近似が得られます。整数では、除算で切り捨てがあります。これは、収束に有利または不利に影響する可能性があります。さらに、答えは平方根以下の最大の整数になるはずです。これ'
整数除算のターンケーションのため、y1 = (x/y0 + y0)/2 は、連続する反復が整数ルートまたはルートの下限値 (つまり、ルートより小さい最大の整数) に到達するまで収束します。これが理想です。根よりも大きくなければならない根の提案された値、たとえば x 自体から始めると、yn * yn <= x である yn の最初の値が望ましい結果になります。
簡単な答えは、y0 > y から始めると、y 以下の最初の新しい yn であり、次に y - yn < 1 になります。これで、必要な回答の条件を正確に満たす終了条件が得られました。
ここでは、基本的な反復および再帰ソリューションを示します。ソリューションには、x に負の値が入力されないようにするための安全機能は含まれていません。1 つの大きな懸念事項は、誰かが 0 の平方根を見つけたい場合に備えてゼロ除算を避けることです。それは些細な答えなので、再帰的方法と反復的方法の両方がゼロによる除算が行われる前に 0 を返します。再帰的解法と反復解法はどちらも、0 と 1 の平方根を見つけるための自明なケースで機能します。
Java では常に int および long 演算を使用して実行する必要がある別の分析があります。Java は int または long オーバーフローについて何もしないため、大きな懸念事項は整数オーバーフローです。オーバーフローは 2 の補数の値になり (他の場所で調べてください)、偽の結果につながる可能性があり、Java は int または long オーバーフローで例外をスローしません。
この場合、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 を試行するためです。 > y であることが保証されている x。x / 2 は、x > 1 のすべての値に対して機能します。x が 0 または 1 の場合、x の平方根は単に 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
再帰的なソリューションをテストして、フレーム スタックで生成されるインスタンスの数を調べることができますが、収束が非常に速いことがわかります。興味深いのは、反復ソリューションが再帰ソリューションよりもはるかに小さくて高速であることです。これは多くの場合そうではなく、スタック リソースが再帰の深さに対して十分であると予測できる場合に再帰が使用される理由です。