ホームページ >Java >&#&チュートリアル >二分探索アルゴリズムを使用して数値の立方根を見つける Java プログラム
Cube root は整数値であり、それ自体を 3 回連続して乗算すると元の値になります。この記事では、二分探索を使用して数値の立方根を見つける Java プログラムを作成します。数値の立方根を求めることは、二分探索アルゴリズムの応用です。この記事では、二分探索を使用して立方根を計算する方法について詳しく説明します。
たとえば、64 の立方根は 4 で、出力は 4 になります。
リーリーたとえば、216 の立方根は 6 で、出力は 6 になります。
二分探索は、要素 (つまり、ソートされた配列内のキー) を見つけるために使用されるアルゴリズムです。バイナリアルゴリズムの動作原理は次のとおりです
配列が「arr」であると仮定します。配列を昇順または降順に並べ替えます。
low = 0、high = n-1 (n = 要素数) を初期化し、mid を middle = low (high-low)/2 として計算します。 arr[middle] == key の場合、配列の中央のインデックスである middle を返します。
キー値が arr[middle] 要素より小さい場合は、高インデックスを中間インデックス -1 に設定します。キー値が中間要素より大きい場合は、低インデックスを中間インデックスに設定します。 1
検索したい要素が見つかるまで二分探索を続けます。
low が high より大きい場合、キー値が配列 'arr' に存在しないため、直接 false を返します。
while ループの最初の反復により、中間インデックスが Mid = low (high-low)/2
中央値 = 0 (5-0)/2 = 2。
arr[mid] の値は 5 で、キー値 7 より小さくなります。したがって、low=mid1=3を更新します。
while ループの 2 回目の反復では、low (high-low)/2 を使用して、中間インデックス Mid = 4 を取得します。
arr[mid] の値は 9 で、キー値 7 より大きくなります。したがって、高 = 3 (中 - 1) を更新します。
while ループの 3 回目の反復により、中間インデックス Mid = 3 が得られます。
arr[mid] は 7 で、キーの値と同じです。したがって、中間のインデックスである 3 を返します。
つまり、指定された配列では、キーワードのインデックスは 7 であり、二分探索アルゴリズムを使用してインデックス 3 が見つかりました。
二分探索を使用して立方根を求めるアルゴリズム
ステップ 2 - 中 = 低 (高-低)/2 を使用して、低値と高値の中央値を見つけます。
ステップ 3 -mid *mid*mid の値を見つけます。mid *mid*mid == n の場合、mid の値を返します。
ステップ 4 - 中央の値が n より小さい場合は、low=mid 1、それ以外の場合は high=mid-1
ステップ 5 - 値が見つかるまでステップ 2 ~ 4 を繰り返します。
Example の中国語訳は次のとおりです: Example
それでは、この記事では、Java の二分探索アルゴリズムを使用して数値の立方根を見つける方法について説明しました。
以上が二分探索アルゴリズムを使用して数値の立方根を見つける Java プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。